CF2037E 题解

Melo_qwq · 2024-11-20 23:25:32 · 题解

不错的题。

首先，不能这么做：

• 尝试把原来的序列分成若干个小序列。

• 尝试对小序列进行大分讨。

这样做的不足之处：

• 分类讨论情况太多了，询问次数会超。

• 断成若干个小序列，等于忽略了不同序列之间的条件，导致答案错误。

我们发现最多询问 n 次，那么整体就是线性的，我们不妨考虑如何 \Theta(n) 地进行推导。接下来设 f(l,r) 表示对 [l,r] 的询问。

可以发现如果 f(1,i)=0 但是 f(1,i + 1)=k,k>0 的话，我们可以得到如下结论：

• 由于 f(1,i + 1)\ne 0，所以 [1,i] 中一定存在 0。
• 由于 f(1,i)=0，那么这一段一定没有任何一个 0 在 1 的前面。

综上，我们可以得出：此时 [1,i] 一定是由一段前缀的 1 和一段后缀的 0 组成，可以没有 1。

那么后缀的 0 的长度是多少呢？可以发现，如果 i+1 仍然是 0，那么 f(1,i+1)=0，所以位置 i+1 一定是 1；由于 f(1,i+1)=k，那么意味着（注意到只有这个 1 才有机会和前面的 0 匹配）这个 1 和 k 个 0 匹配了，所以后缀的 0 的长度是 k，然后顺便直接把前面的 1 填进去就好了。

之后该怎么办呢？注意到另一件事，就是左端点不动，右端点单增时，答案不可能变小，那么我们找到第一个满足上述条件的位置 i，之后对于 i 后面的位置 j：

• 如果 f(1,j)=f(1,j-1)，那么说明 j 这个位置一定无法和前面配对，由于我们的 i 符合刚才说的条件，那么此时 j 前面一定有 0 存在，如果它没有配成，说明这个位置一定是 0（要是是 1 一定可以和前面的 0 做出贡献）。

• 反之则为 1。

那么我们直接再扫一遍就可以了。

什么时候没有唯一解呢？就是没有找到 i 的时候，很好理解。

代码：

#include <bits/stdc++.h>
#define f(i ,m ,n ,x) for (int i = (m) ; i <= (n) ; i += (x))
using std :: cin ; using std :: cout ; using std :: endl ;
int t ,n ,ch[10007] ; 
int main () {
    cin >> t ;
    while (t --) {
        cin >> n ;
        int ans = 0 ; bool flag (0) ;
        cout << "? " << 1 << ' ' << 2 << endl ;
        cin >> ans ;
        if (ans == 1) { ch[1] = 0 , ch[2] = 1 ,flag = true ;}
        f (i ,3 ,n ,1) {
            cout << "? " << 1 << ' ' << i << endl ;
            int res ; cin >> res ;
            if (flag == false) {
                if (res ^ 0) {
                    f (j ,1 ,i - 1 - res ,1) ch[j] = 1 ;
                    f (j ,i - res ,i - 1 ,1) ch[j] = 0 ;
                    ch[i] = 1 , flag = true ;
                } 
                ans = res ;
            } else {
                if (res == ans) ch[i] = 0 ;
                else ch[i] = 1 ;
                ans = res ;
            }
        }
        if (ans == 0) cout << "! IMPOSSIBLE" << endl ;
        else {
            cout << "! " ;
            f (i ,1 ,n ,1) cout << ch[i] ; cout << endl ;
        }
    }
    return 0 ;
}