CF2037E Kachina's Favorite Binary String 解题报告

~~是可爱的卡齐娜耶！！！~~

题目大意

交互题（不会交互题的可以去做洛谷的板子 P1733），

T

组交互，每次交互库会指定一个长度为

n

的

01

字符串（只由

0

和

1

组成），你最多询问

n

次，每次询问你给出一个区间

[l,r]

，交互库会给出指定字符串的 01 子串的个数（0 和 1 可以不相连，且 0 和 1 只要有其一位置不同都将会认为成不同的 01 子串）。在最多

n

次询问后，确定这个字符串，或者输出 IMPOSSIBLE 代表无论怎样

n

次询问都不能确定这个字符串。

解题思路

考虑字符串中的每个字符都要得到，每次询问至少要确定一个字符。要实现这种询问，考虑询问 $n-1$ 次，第 $i$ 次询问询问区间 $[1,1+i]$ ，当

i

增大时，如果答案变大，说明这一位是 1 且答案的增量

\Delta ans

为当前位之前的 0 的个数。如果答案不变，说明这一位为 0 或者这一位之前 0 的个数为

0

。

假如说在第

i

次询问

[1,i+1]

的答案

ans_i

第一次非零，那么第

i+1

位为 1 并且再次之前一定只有一种可能：

\underbrace{1\dots1}_{i-ans_i\ 个}\underbrace{0\dots0}_{ans_i\ 个}

再之后，0 的个数被确定，记录一下当前零的个数，那么如果之后答案不变，当位就一定是 0，更新当前零的个数，如果答案变大，变大的一定是前面的零的个数，如果不是，那么这个序列不可能存在（不合法），直接输出 IMPOSSIBLE 即可。

进行完这

n-1

次询问后，只有三种情况：

这个序列已经被确定
这个序列不合法，已经输出 IMPOSSIBLE
这个序列从头到尾交互库给出的所有数都是 $0$ ，此时这个序列肯定是由 $k$ 个连续的 1 和 $n-k$ 个连续的 0 拼接而成，其中 $0\le k\le n$ ，此时再进行任何区间的询问得到的答案都肯定是 $0$ ，第 $n$ 次询问可有可无，都无法确定序列，输出 IMPOSSIBLE。

AC Code

CPP

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
using namespace std;
int T,n;
int re()//防止作弊不放快读快写
void wr(int x)
signed main()
{
	T=re();
	while(T--)
	{
		n=re();
		string s="";//当前确定的序列 
		int last=0,zero=0;//前一个的答案和当前 0 的个数 
		for(int i=2;i<=n;i++)
		{
			printf("? 1 %d\n",i);
			fflush(stdout);
			int x=re();
			if(last==0)
			{
				if(x==0)
					continue;//如果 x 不等于 0，则此处为 ans 的第一次非零，此时序列确定 
				for(int j=1;j<=i-1-x;j++)
					s+='1';
				for(int j=1;j<=x;j++)
					s+='0';
				s+='1';
				zero=last=x;
			}
			else
			{
				int cha=x-last;//ans 的增量 
				if(cha==0)
					zero++,s+='0';
				else if(cha==zero)
					s+='1',last=x;
				else//不合法 
					break;
			}
		}
		if(s.length()!=n)//后两种情况 
			puts("! IMPOSSIBLE");
		else
			cout<<"! "<<s<<'\n';
		fflush(stdout);
	}
	return 0;
}

CF2037E Kachina's Favorite Binary String 解题报告

文章操作

题目大意

解题思路

AC Code

相关推荐

评论

CF2037E Kachina's Favorite Binary String 解题报告