CF1117E Decypher the String

是个汉子 · 2020-10-09 20:20:11 · 题解

交互题。

这题需要一个很精妙的构造，所以写一篇题解来加深自己的理解。

Solution

如果直接看见 3 次机会和 10000 的 |s| 可能会很迷茫，但是还有一个 26 ，那我们就可以瞎写一个 26^2<10000<26^3 ，然后就到了精妙的构造了。

第一次机会：

每一个 26*26 是大块

第二次机会：

每一个 26 是小块

第三次机会：

这样对于变化后的串 s’ 的每一位都可以找到大块中的小块中的准确位置，即整个原串。

（或者这样理解：将 s' 拆开，三次操作相当于找到位置 i 所对应的26进制数）

代码

#include<bits/stdc++.h>

using namespace std;
const int N=10005;
int pos[N];
string s,print,res;
char ans[N];

int main(){
    cin>>res;
    int len=res.size();
    print="? ";
    char ch='a';
    //先分成26*26的大块，确定在大块的位置
    for(int i=0;i<len;i++){
        print+=ch;
        if((i+1)%(26*26)==0) ch++;
    }
    cout<<print<<endl;
    cin>>s;
    for(int i=0;i<len;i++) pos[i]+=(s[i]-'a')*26*26;
    ch='a';
    print="? ";
    //分成26的小块，确定在小块的位置
    for(int i=0;i<len;i++){
        print+=ch;
        if((i+1)%26==0) ch++;
        if(ch=='z'+1) ch='a';
    }
    cout<<print<<endl;
    cin>>s;
    for(int i=0;i<len;i++) pos[i]+=(s[i]-'a')*26;
    ch='a';
    print="? ";
    //分成1，确定最终的位置
    for(int i=0;i<len;i++){
        print+=ch;
        ch++;
        if(ch=='z'+1) ch='a'; 
    }
    cout<<print<<endl;
    cin>>s;
    for(int i=0;i<len;i++) pos[i]+=(s[i]-'a');
    for(int i=0;i<len;i++)
        ans[pos[i]]=res[i];
    printf("! %s",ans);
    fflush(stdout);
    return 0;
}