Codeforces 1697 D题解

D.Guess The String

题意

交互题。评测机生成一个长度为 N 的字符串 S，有两种操作：

• 1 i，询问第 i 位字母是什么。
• 2 l r，询问区间 [l, r] 的子字符串字符集大小。

只允许提出至多26次操作1，至多6000次操作2，确定后输出生成的字符串S。

Sample Input

5
4
u
2
g
e
s
1

Sample Ouput

? 2 1 5
? 1 2
? 2 1 2
? 1 1
? 1 3
? 1 4
? 2 4 5
! guess

思路

首先可以猜到26个操作对应26个字母，发起操作1的时刻应当是第一次或者最后一次出现某个字母时，在这个交互题中，比较显然的是：如果从左到右构造字符串，第一次出现某字母，就发起操作1。那么顺其自然的就会需要解决一个问题：怎么知道当前字母是第一次出现？

先定义f(x,y)代表[x, y]区间的子字符串的字符集大小。

解决这个问题的方式肯定是通过操作2，而操作2对应的询问得到的答案为字符集的大小。由于我们是顺序依次构造，因此当f(1,x)>f(1,x - 1)的字符集大小大时，就意味着x这个位置出现的字母，从未出现在1~x中，因此就可以发起操作1去询问这个s[x]。通过这样的方式，我们就可以先确定每个字母出现的第一个位置。

以上的方式已经决定了，接下来要确定其他位置的字母，只能够通过操作2的询问。

假设最极端的情况，s[1] ~ s[26]都是不一样的字母，那么我们在最开头就花费了所有的操作1次数，同时也意味着s[27]一定是重复字母。 实际剩下的问题也是这样：当f(1,y) == f(y - 1) (y > 1)时，如何确定s[y]。

实际上从题目所给出的限制可以得出：s[y]的询问次数，只能最多6次(6*1000)。此时只能通过操作2进行询问，操作2的反馈仅有字符集大小，而我们在此时是知道s[1] ~ s[y - 1]的所有字符。

字符集大小最大为26，而确定s[y]的操作次数上限为6次，比较容易想到的就是二分。问题中隐含的单调性则是：从左到右，字符串越长，字符集大小单调递增。因此我们可以二分字符集大小，来确定，s[y]处在二分区间的左半还是右半。我们可以计算得出的是：f(mid, y - 1)，通过询问得出f(mid, y)，如果f(mid, y - 1) == f(mid, y)，就意味着s[y]出现在了mid的左半边。

那么要符合这个等式得出的结论，需要先计算出f(mid, y - 1)，字符如果出现在[mid, y - 1]区间内，则最后一次出现的位置一定在[mid, y - 1]中（废话）。因此记录下每个字符出现的最后一个位置，然后计算[mid, y - 1]中多少个字符最后一次出现，就知道了f(mid, y -1)。

代码

void solveD(){
	int n;
	scanf("%d", &n);
	char s[n + 5];

	s[n + 1] = '\0';
	printf("? 1 1\n");
	fflush(stdout);
	scanf(" %c", &s[1]);
	PIC lastPos[26];
	int tot = 1;
	lastPos[tot] = PIC(1, s[1]);

	for(int i = 2; i <= n; ++i){
		printf("? 2 1 %d\n", i);
		fflush(stdout);
		int sz;
		scanf(" %d", &sz);
		if(sz != tot) {
			printf("? 1 %d\n", i);
			fflush(stdout);
			scanf(" %c", &s[i]);
			lastPos[++tot] = PIC(i, s[i]);
			continue;
		}
		sort(lastPos + 1, lastPos + tot + 1);
		int l = 1, r = tot;
		int ans = 0;
		while(l <= r){
			int mid = l + r >> 1;
			printf("? 2 %d %d\n", lastPos[mid].first, i);
			fflush(stdout);
			scanf(" %d", &sz);
			if(sz == tot - mid + 1) ans = mid, l = mid + 1;
			else r = mid - 1;
		}
		s[i] = lastPos[ans].second;
		lastPos[ans].first = i;
	}
	printf("! %s\n", s + 1);
	fflush(stdout);
}