CF2037E 题解

不错的题。

首先，不能这么做：

尝试把原来的序列分成若干个小序列。
尝试对小序列进行大分讨。

这样做的不足之处：

分类讨论情况太多了，询问次数会超。
断成若干个小序列，等于忽略了不同序列之间的条件，导致答案错误。

我们发现最多询问

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

的时候，很好理解。

代码：

CPP

#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 ;
}

文章操作

相关推荐

评论

CF2037E 题解