CF1765G Guess the String

Semsue · 2023-02-19 23:13:21 · 题解

就是说已经知道 s_1=0，那么一次操作其实必然会知道至少一个位置。

假设你已经知道 s_{1\sim i-2} 了，考虑询问 p_i 或者 q_i。

如果 p_i,q_i 其中一个 \ge 2 就直接确定了。

假设

同理对 q_i 分类讨论。

直接做显然有可能被卡，但是每次随一个 p,q 询问，期望只用问 1.5 次，就不会被卡了。

#include <bits/stdc++.h>
int s[1005];
int x, p[1005], q[1005];
std :: mt19937 rnd(time(0));
int ask_p(int y) {
    std :: cout << "1 " << y << "\n";
    fflush(stdout);
    std :: cin >> x;
    return x;
}
int ask_q(int y) {
    std :: cout << "2 " << y << "\n";
    fflush(stdout);
    std :: cin >> x;
    return x;
}
int main() {
    int T;
    std :: cin >> T;
    for (int t = 1; t <= T; t++) {
        int n;
        std :: cin >> n;
        memset(p, -1, sizeof(p));
        memset(q, -1, sizeof(p));
        s[0] = 0;
        p[1] = ask_p(2);
        if (p[1] == 1) s[1] = 0;
        else s[1] = 1;
        for (int i = 2; i + 1 < n; i += 2) {
            int k = rnd() % 2;
            if (k) {
                p[i + 1] = ask_p(i + 2);
                if (p[i + 1] >= 2) {
                    s[i] = s[p[i + 1] - 2];
                    s[i + 1] = s[p[i + 1] - 1];
                } else if (p[i + 1] == 1) {
                    s[i + 1] = 0;
                    if (s[1] == 0) s[i] = 1;
                    else {
                        p[i] = ask_p(i + 1);
                        if (p[i] == 0) s[i] = 1;
                        else {
                            s[i] = s[p[i] - 1];
                        }
                    }
                } else {
                    s[i + 1] = 1;
                    if (s[1] == 1) s[i] = 1;
                    else {
                        p[i] = ask_p(i + 1);
                        if (p[i] == 0) s[i] = 1;
                        else {
                            s[i] = s[p[i] - 1];
                        }
                    }
                }
            } else {
                q[i + 1] = ask_q(i + 2);
                if (q[i + 1] >= 2) {
                    s[i] = !s[q[i + 1] - 2];
                    s[i + 1] = !s[q[i + 1] - 1];
                } else if (q[i + 1] == 1) {
                    s[i + 1] = 1;
                    if (s[1] == 0) s[i] = 0;
                    else {
                        p[i] = ask_p(i + 1);
                        if (p[i] == 0) s[i] = 1;
                        else {
                            s[i] = s[p[i] - 1];
                        }
                    }
                } else {
                    s[i + 1] = 0;
                    if (s[1] == 1) s[i] = 0;
                    else {
                        p[i] = ask_p(i + 1);
                        if (p[i] == 0) s[i] = 1;
                        else {
                            s[i] = s[p[i] - 1];
                        }
                    }
                }
            }
        }
        if (n & 1) {
            p[n - 1] = ask_p(n);
            if (p[n - 1] == 0) s[n - 1] = 1;
            else s[n - 1] = s[p[n - 1] - 1];
        }
        std :: cout << "0 ";
        for (int i = 0; i < n; i++) std :: cout << s[i];
        puts("");
        fflush(stdout);
        int tmp;
        std :: cin >> tmp;
    }

    return 0;
}