CF1282D Enchanted Artifact 做题记录

本题为交互题。

有一个字符串 $s$，只由字符 a 和 b 组成。每次你可以询问一个字符串，它会返回这两个字符串的编辑距离。编辑距离定义为一个字符串经过修改，删除或插入单个字符操作得到另一个字符串，两个字符串编辑距离的定义为最小的操作次数。

你需要在 $|s| + 2$ 次操作内求出字符串 $s$。

$1\le |s|\le 300$。

首先可以通过询问一个 a 和一个 b 来获得字符串的长度 $n$，这需要两次操作。，然后字符串一定是若干个 a，每个 a 前面和字符串的最后面都插入了若干个 b 这样的，记 $A$ 为 a 的数量，$B$ 为 b 的数量，若已知 $A$ 则可以在 $A+B=n$ 次操作中得到整个字符串。

接下来的问题变为怎么求 $A$，自己想一直只会暴力用 $A$ 次操作尝试，看了题解才发现可以通过询问一次全 a 串来求。

这样做是 $n+3$ 次的，考虑优化，受到询问全 a 求 $A$ 的启发，不难想到可以询问一次长 $300$ 的全 a 串和一次长为 $300$ 的全 b 串来获得 $A$、$B$ 和 $n$，这样询问次数就是 $n+2$ 了。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=305;

char a[S],ans[S];

inline int que(int n)
{
	a[n+1]=0;
	printf("%s\n",a+1);
	fflush(stdout);
	int res;
	scanf("%d",&res);
	return res;
}

int main()
{
	int A,B;
	for(int i=1;i<=300;i++) a[i]='a';
	A=300-que(300);
	for(int i=1;i<=300;i++) a[i]='b';
	B=300-que(300);
	if(A==0)
	{
		for(int i=1;i<=B;i++) ans[i]='b';
		ans[B+1]=0;
		printf("%s\n",ans+1);
		fflush(stdout);
		return 0;
	}
	int pre=B,tot=0;
	for(int i=1;i<=A;i++)
	{
		while(pre!=0)
		{
			ans[++tot]='b';
			for(int j=1;j<=tot;j++) a[j]=ans[j];
			for(int j=i;j<=A;j++) a[tot+j-i+1]='a';
			int re=que(tot+A-i+1);
			if(re<pre) pre=re;
			else
			{
				tot--;
				break;
			}
		}
		ans[++tot]='a';
	}
	for(int i=tot+1;i<=A+B;i++) ans[i]='b';
	ans[A+B+1]=0;
	printf("%s\n",ans+1);
	fflush(stdout);
	return 0;
}