信服2018春招聘-研究開発巻プログラミング問題-題解

これまで通りの「怠け者」と信じていた2018秋招の5つのプログラミング問題が今回の春招で3つ登場し、新しいプログラミング問題が追加された.来年のプログラミング問題はやはりそうだろうと信じて、損をしないのは自分だと思います.
今回の問題解は新しく追加されたプログラミング問題の解析とコードのみを与え、同時に2018キャンパス招聘C++エンジニアプログラミング問題-問題解の第5題:囲碁の気のコード(問題の意味を理解し間違えた)を修正し、4つのプログラミング問題をすべて通過した.
第一題:
詳細は、2018キャンパス招聘C++エンジニアプログラミング問題-問題解の第3題を参照してください.
2番目の問題:
詳細は、2018キャンパス招聘C++エンジニアプログラミング問題-問題解の第4題を参照してください.
第三題:
まず、2018キャンパス招聘C++エンジニアのプログラミング問題-問題解の第5題囲碁の本当の気はどのように求めるべきかを深く信じることができます.
次に、この問題は囲碁の気を簡略化して、前に問題を理解し間違えて、駒がそれと同じ駒に出会って行けないと思っていましたが、実はそうではありません.駒は自分と同じ駒に出会っても前進し続けることができますが、結果に貢献していないだけです.
従って,ここではbfs b fsを用いることで問題を解決できる.
コード:

int calc(struct weiqi *wq, int y, int x)
{
    //TODO:
    if (wq->board[x][y] == NONE)
        return -1;
    const int MAXSIZE = 100000;
    const int n = 19;
    const int dirx[] = {0, 0, 1, -1};
    const int diry[] = {1, -1, 0, 0};
    const int theChess = wq->board[x][y] == 1 ? 2 : 1;
    int que[MAXSIZE];
    int head = 0, tail = 0;
    int used[n * n];
    memset(used, 0, sizeof(used));
    que[tail++] = x * n + y;
    tail %= MAXSIZE;
    used[x * n + y] = 1;
    int ret = 0;
    while (head < tail) {
        int node = que[head++];
        head %= MAXSIZE;
        int nowx = node / n;
        int nowy = node % n;

        for (int i = 0; i < 4; i++) {
            int tx = nowx + dirx[i];
            int ty = nowy + diry[i];
            if (tx >= 0 && tx < 19 && ty >= 0 && ty < 19 && !used[tx * n + ty] && wq->board[tx][ty] != theChess) {
                if (wq->board[tx][ty] == NONE)
                    ++ret;
                used[tx * n + ty] = 1;
                que[tail++] = tx * n + ty;
                tail %= MAXSIZE;
            }
        }
    }
    return ret;
}

第四題:
タイトル:
あるシーケンスを知っていて、シーケンスの中のアルファベットを出現の順序で1つのスタックに押し込んで、スタックに入る任意の過程の中で、スタックの中のアルファベットがスタックから出ることを許可して、すべての可能なスタックの順序を求めます.
サンプル入力:

abc

サンプル出力:

abc
acb
bac
bca
cba

解析:
すべての合法的なスタックシーケンスの個数は1つのカトラン数であるため、与えられたシーケンスの長さは大きくないので、このプロセスを直接再帰的にシミュレートする.
遍歴シーケンスのすべてのアルファベットは、まず現在のアルファベットをスタックに入れます.この時、スタックには必ずアルファベットがあります.あなたは遍歴シーケンスを続けることを選択することができます.この時、スタックの中のアルファベットを1つずつスタックから出すことができます.最後に、シーケンスを遍歴した後、スタックの中のすべての字母を順番にスタックから出すことができます.このようにして、すべての合法的なシーケンスを得ることができます.
なお、このようにして得られたシーケンスは重複するので、setで重量を落とすとともに、サンプルを観察すると、合法的なシーケンスの辞書シーケンスで出力され、ちょうどsetの要素が秩序正しく、牛客網にはSpecialJudge S p e c i a l J u d g eがなく、辞書シーケンスで出力しなければ通じないことが分かった.
コード:

#include 

using namespace std;

void dfs(string &str, int i, string st, string tmp, set<string> &ret)
{
    if (i == (int)str.size()) {
        reverse(st.begin(), st.end());
        ret.insert(tmp.append(st));
        return ;
    }
    st.push_back(str[i]);
    dfs(str, i + 1, st, tmp, ret);
    for (; !st.empty(); ) {
        tmp.push_back(st.back());
        st.pop_back();
        dfs(str, i + 1, st, tmp, ret);
    }
}

int main()
{
    for (string str; cin >> str; ) {
        set<string> ret;
        dfs(str, 0, "", "", ret);
        for (auto it = ret.begin(); it != ret.end(); ++it)
            cout << *it << endl;
    }
    return 0;
}