[交互题] Codeforces 1282D Enchanted Artifact

题目大意

本题为交互题。有一个字符串s，只由字符'a'和'b'组成。每次你可以询问一个非空的字符串，它会返回这两个字符串的编辑距离。为一个字符串经过修改，删除或插入操作得到另一个字符串，两个字符串编辑距离的定义为最小的操作次数，若返回值为0，那么就是字符串s。让你在n + 2操作内得出字符串s（n为字符串s的长度，未知）,且每次询问的字符串长度不得超过300。

题解

首先我们当然得去知道这个字符串有多长。
第一次去询问("a")，设回答是(Len)。若(Len=300)，显然答案是(300)个(b)，直接输出即可。否则，(++Len)，再去询问(Len)个(a)，设回答为(CountB)，若(CountB=0)，则已经找到了。若(CountB=Len)，则说明答案是(Len-1)个(b)。否则(Len)就是答案字符串的长度，且(CountB)就是答案字符串中(b)的个数。我们依次去询问(Len-1)次("baa...aa")，("aba...aa")，("aab...aa")，(...)，(aaa...ba)，即可知道每个位置上是否是b，因为我们已经知道(b)的个数，所以只需询问(Len-1)次即可判断最后一位是否是(b)，加上开始时用了2步，最后给出答案还需1步，总共用了(Len+2)步，满足要求。

Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

#define RG register int
#define LL long long

int CountB=0,Dis,Len;

int main(){
    ios::sync_with_stdio(false);
    cout<<"a"<<endl;
    cin>>Len;++Len;
    if(Len>300){
        for(RG i=1;i<Len;++i)
            cout<<'b';
        cout<<endl;
        int x;cin>>x;
        return 0;
    }
    string S(Len,'a');
    string Ans(Len,'a');
    cout<<S<<endl;
    cin>>CountB;
    if(CountB==0) return 0;
    if(CountB==Len){
        for(RG i=1;i<Len;++i)
            cout<<'b';
        cout<<endl;
        int x;cin>>x;
        return 0;
    }
    int Count=0;
    for(RG i=0;i<Len-1;++i){
        S[i]='b';cout<<S<<endl;
        int x;cin>>x;
        if(x<CountB){Ans[i]='b';++Count;}
        S[i]='a';
    }
    if(Count<CountB) Ans[Len-1]='b';
    cout<<Ans<<endl;
    int x;cin>>x;
    return 0;
}