Codeforces 1705F Mark and the Online Exam

先问全 \(\texttt{T}\)，记得到的数为 \(a\)。
接下来问 \(len\) 个位置为 \(\texttt{T}\) ，得到的数为 \(b\)。
因为剩下 \(n - len\) 个位置肯定都会被刚好算上一次，对于这 \(len\) 个数里的 \(\texttt{T}\) 的个数 \(x\) 就有式子 \((n - len) + 2x = a + b\)，可以解得 \(x = \frac{a + b - (n - len)}{2}\)。

考虑对于还未确定的下标里选 \(4\) 个然后去询问，记为 \(x\)。
如果 \(x = 0\) 或 \(x = 4\) 就可以直接确定了这 \(4\) 个位了。
否则考虑问其中的 \(2\) 个下标为 \(\texttt{T}\)，记为 \(y\)。
如果 \(y = 0\) 或 \(y = 2\)，可以直接确定这 \(2\) 个位。
否则可以知道这 \(2\) 位上的值不同，又因为只有 \(\texttt{T}\) 和 \(\texttt{F}\)，考虑只留下一个下标，另一个下标待得知了这个下标的值取反即可。
直到最后 \(< 4\) 个下标，直接暴力即可。

然后这样子肯定是能卡的，于是考虑随机选择下标。
考虑通过 \(1\) 次操作就能问出 \(4\) 个下标的概率 \(\frac{1}{8}\)。
\(2\) 次操作问出 \(4\) 个下标的概率 \(\frac{1}{8}\)。
\(2\) 次操作问出 \(3\) 个下标的概率 \(\frac{1}{2}\)。
\(2\) 此操作问出 \(2\) 个下标的概率 \(\frac{1}{4}\)。
记 \(f_n\) 为问出 \(n\) 个下标的期望，有 \(f_i = i(i\le 3), f_i = \frac{1}{8}(1 + f_{i - 4}) + \frac{1}{8}(2 + f_{i - 4}) + \frac{1}{2}(2 + f_{i - 3}) + \frac{1}{4}(2 + f_{i - 2})\)。
可以得到 \(f_{1000} = 625.71875\)，在加上一开始的 \(1\) 次，期望询问次数 \(626.71875\) 次。

#include<bits/stdc++.h>
std::mt19937 Rand(time(0));
const int maxn = 1e3 + 10;
std::vector<int> son[maxn];
char s[maxn];
char ans[maxn];
bool vis[maxn];
int main() {
    int n; scanf("%d", &n);
    std::vector<int> P;
    auto ins = [&](int x) {P.push_back(x);};
    auto val = [&]() {
        int w = Rand() % P.size(), x = P[w];
        for (int i = w; i + 1 < P.size(); i++) P[i] = P[i + 1];
        P.pop_back();
        return x;
    };
    auto qry = [&]() {
        printf("%s\n", s), fflush(stdout);
        int x; scanf("%d", &x);
        if (x == n) exit(0);
        return x;
    };
    for (int i = 0; i < n; i++) s[i] = 'T';
    int all = qry();
    auto calc = [&](int x, int len) {return ((all + x) - (n - len)) / 2;};
    auto add = [&](int u, int v) {son[u].push_back(v), vis[v] = 1;};
    for (int i = 0; i < n; i++) ins(i);
    while (P.size() >= 4) {
        std::vector<int> id(4);
        for (int &x : id) x = val();
        for (int i = 0; i < n; i++) s[i] = 'F';
        for (int x : id) s[x] = 'T';
        int tot = calc(qry(), 4);
        if (tot == 4) {
            for (int x : id) ans[x] = 'T';
            continue; 
        }
        if (tot == 0) {
            for (int x : id) ans[x] = 'F';
            continue;
        }
        for (int i = 0; i < n; i++) s[i] = 'F';
        s[id[0]] = s[id[1]] = 'T';
        int tmp = calc(qry(), 2);
        if (tmp == 2) ans[id[0]] = ans[id[1]] = 'T';
        else if (tmp == 0) ans[id[0]] = ans[id[1]] = 'F';
        else add(id[0], id[1]), ins(id[0]);
        tmp = tot - tmp;
        if (tmp == 2) ans[id[2]] = ans[id[3]] = 'T';
        else if (tmp == 0) ans[id[2]] = ans[id[3]] = 'F';
        else add(id[2], id[3]), ins(id[2]);
    }
    for (int x : P) {
        for (int i = 0; i < n; i++) s[i] = 'F';
        s[x] = 'T';
        int tot = calc(qry(), 1);
        ans[x] = tot ? 'T' : 'F';
    }
    std::queue<int> Q;
    for (int i = 0; i < n; i++) if (! vis[i]) Q.push(i);
    while (! Q.empty()) {
        int u = Q.front(); Q.pop();
        for (int v : son[u]) {
            ans[v] = ans[u] ^ 'T' ^ 'F';
            Q.push(v);
        }
    }
    for (int i = 0; i < n; i++) s[i] = ans[i];
    qry();
    return 0;
}