本题为交互题。
有一个字符串 ,只由字符
a
和b
组成。每次你可以询问一个字符串,它会返回这两个字符串的编辑距离。编辑距离定义为一个字符串经过修改,删除或插入单个字符操作得到另一个字符串,两个字符串编辑距离的定义为最小的操作次数。你需要在 次操作内求出字符串 。
。
首先可以通过询问一个 a
和一个 b
来获得字符串的长度 ,这需要两次操作。,然后字符串一定是若干个 a
,每个 a
前面和字符串的最后面都插入了若干个 b
这样的,记 为 a
的数量, 为 b
的数量,若已知 则可以在 次操作中得到整个字符串。
接下来的问题变为怎么求 ,自己想一直只会暴力用 次操作尝试,看了题解才发现可以通过询问一次全 a
串来求。
这样做是 次的,考虑优化,受到询问全 a
求 的启发,不难想到可以询问一次长 的全 a
串和一次长为 的全 b
串来获得 、 和 ,这样询问次数就是 了。
代码如下:
#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;
}