CF1282D Enchanted Artifact 做题记录

本题为交互题。

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

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

1s3001\le |s|\le 300

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

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

这样做是 n+3n+3 次的,考虑优化,受到询问全 aAA 的启发,不难想到可以询问一次长 300300 的全 a 串和一次长为 300300 的全 b 串来获得 AABBnn,这样询问次数就是 n+2n+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;
}