CF1286C1 Madhouse (Easy version) 题解
考虑问两次，一次 \([1,n]\)，一次 \([2,n]\)，能够得到什么信息：长度为 \(1\) 的串，第一次询问多出来的串就是 \(s_1\)；同理，长度为 \(2\) 的串多出来的两个字符，去掉 \(s_1\) 就是 \(s_2\)；依此类推之后，发现可以直接求出所有位置的字符，并且字串总长度也没有超。
点击查看代码
const int N=100+13;
char s[N],t[N];
std::vector a[N][N],b[N][N];
int lena[N],lenb[N];
bool vis[N];
inline bool check(std::vector a,std::vector b){
for(int i=0;i<26;++i)
if(a[i]!=b[i]) return 0;
return 1;
}
int n;
int main(){
scanf("%d",&n);
print('?'),print(' '),print(1),print(' '),println(n);flush();fflush(stdout);
if(n==1){scanf("%s",s+1);print('!'),print(' '),println(s[1]);flush(),fflush(stdout);return 0;}
int tt=n*(n+1)/2;
while(tt--){
scanf("%s",s+1);int l=strlen(s+1);
std::vector bb;bb.resize(26);
for(int i=1;i<=l;++i) bb[s[i]-'a']++;
a[l][++lena[l]]=bb;
}
print('?'),print(' '),print(2),print(' '),println(n);flush(),fflush(stdout);
tt=(n-1)*n/2;
while(tt--){
scanf("%s",s+1);int l=strlen(s+1);
std::vector bb;bb.resize(26);
for(int i=1;i<=l;++i) bb[s[i]-'a']++;
b[l][++lenb[l]]=bb;
}
std::vector ans;ans.resize(26);
for(int i=1;i<=n;++i){
memset(vis,0,sizeof vis);
for(int j=1;j<=lena[i];++j){
bool ok=0;
for(int k=1;k<=lenb[i];++k)
if(!vis[k]&&check(a[i][j],b[i][k])){vis[k]=1,ok=1;break;}
if(!ok){
std::vector now=a[i][j];int c=0;
for(int k=0;k<26;++k)
if(now[k]>ans[k]){c=k;break;}
ans[c]++;
t[i]=(char)(c+'a');
break;
}
}
}
print('!'),print(' ');
for(int i=1;i<=n;++i) print(t[i]);flush();fflush(stdout);
return 0;
}