CF1765G 题解

cmk666 · 2022-12-13 08:52:35 · 题解

题目传送门

观察到询问次数上界和 n 差的并不远，比例大约在 1.26 左右，启示我们要用一个询问来获得两个字符的关系。

先用一次询问问出 p_2 来推断 s_2 的值。

考虑当前所有 [1,i-2] 的字符已经确定，询问 p_i：

若 p_i\ge2，则有 s[i-1,i]=s[p_i-1,p_i]；
若 p_i=1，则当 s_2=\texttt{0} 时可推出 s[i-1,i]=\texttt{10}，否则无法确定；
若 p_i=0，则当 s_2=\texttt{1} 时可推出 s[i-1,i]=\texttt{11}，否则无法确定。

询问 q_i 同理：

若 q_i\ge2，则有 s[i-1,i]=s[q_i-1,q_i] 的每个字符取反；
若 q_i=1，则当 s_2=\texttt{0} 时可推出 s[i-1,i]=\texttt{01}，否则无法确定；
若 q_i=0，则当 s_2=\texttt{1} 时可推出 s[i-1,i]=\texttt{00}，否则无法确定。

观察到询问 p_i 和 q_i 之后，必定会走到某一个分支里（p_i 和 q_i 不可能同时为 0 或 1），所以只要至多两次询问就能确定相邻的两个字符。

虽然但是，这个做法在最坏情况下，一次询问平均还是只能问出一个字符，而且出题人有点脑子都会把你卡掉，所以还是过不去。

然而，如果我们每次询问，不是固定询问 p_i 或 q_i，而是随机一个，这样没法构造数据来卡，期望就降到了平均 1.5 次询问能问出两个字符，整个字符串期望问 750 次左右，可以通过。

核心代码如下：

int n, p[1009], q[1009], op, a, pos; char s[1009];
inline int query_p(int x) { /* 询问 p_x 的值 */ }
inline int query_q(int x) { /* 询问 q_x 的值 */ }
inline void ans() { /* 输出答案 s */ }
inline char qwq(char c) { return '0' + '1' - c; } // 取反
inline bool f(int op, int x, int y)
{       // 对于询问的分类讨论，返回 true 表示确定，反之不确定
    if ( op == 0 && y > 1 ) { s[x - 1] = s[y - 1], s[x] = s[y]; return true; }
    if ( op == 0 && !y && s[2] == '1' ) { s[x - 1] = s[x] = '1'; return true; }
    if ( op == 0 && y && s[2] == '0' ) { s[x - 1] = '1', s[x] = '0'; return true; }
    if ( op == 1 && y > 1 ) { s[x - 1] = qwq(s[y - 1]), s[x] = qwq(s[y]); return true; }
    if ( op == 1 && !y && s[2] == '1' ) { s[x - 1] = s[x] = '0'; return true; }
    if ( op == 1 && y && s[2] == '0' ) { s[x - 1] = '0', s[x] = '1'; return true; }
    return false;
}
mt19937 rnd(time(nullptr));
inline void work()
{
    memset(p, -1, sizeof(p)), memset(q, -1, sizeof(q));
    read(n), s[n + 1] = '\0', s[1] = '0', s[2] = query_p(2) ? '0' : '1';
    for ( int i = 3 ; i <= n ; i += 2 )
    {
        op = rnd() & 1, pos = i + ( i + 1 <= n ), a = op ? query_q(pos) : query_p(pos);
        // 随机问一个，如果能推断出来就不用再问第二次了
        if ( f(op, pos, a) ) continue;
        op = !op, f(op, pos, op ? query_q(pos) : query_p(pos));
        // 问第二次，可以证明这次 f 的返回值一定是 true，即一定可以确定这两位
    }
    ans();
}
int main() { int t; read(t); For(tt, 1, t) work(); return 0; }