题解 CF1117E【Decypher the String】

_sys · 2019-02-19 15:01:17 · 题解

本来都AFO了不想写题解了，但是这道题实在是太妙了，忍不住写几句。 Luogu现在还没搬，所以先写成非分类文章。

题意是现在有一个长度\leq10000的字符串和一个位置上的双射f，使得字符串i上的字符走到f(i)上来。

你有三次交互机会，每次给一个长度与原串相等的字符串，返回经过f后的字符串。

现在给你f(原串)，求原串

我们考虑一下，3,10000,26有什么关系

发现26^2<10000<26^3

就考虑如何一次交互如何扩大26倍

我们可以通过以下方式

第一次:

我们称26*26个为一个大块

第二次:

我们称26个为一个小块

第三次:

这样，对于一个位置i，第一次我们可以知道f(i)属于哪一个大块，第二次可以知道属于哪一个小块，第三次便可以知道属于哪里

当然还有另外一种方法，第一次使用26个字母循环，第二次使用25个，第三次23个，这样就可以知道f(i) \mod 26/25/23的值，再使用CRT合并即可

不过26*25*23 < 15000 < 26^3

所以，如果n=15000第二个方法就不行

代码我只写了第一种方法的：

#include <bits/stdc++.h>
using namespace std;
const int Maxn=10005;
int bel[Maxn],n;
string str,res,print;
char ans[Maxn];
int main()
{
    cin>>res;
    int siz=res.size();
    print="? ";
    char ch='a';
    for(int i=0;i<siz;i++)
    {
        print+=ch;
        if((i+1)%(26*26)==0) ch++;
    }
    cout<<print<<endl;
    cin>>str;
    for(int i=0;i<siz;i++)
        bel[i]+=(str[i]-'a')*26*26;
    ch='a';
    print="? ";
    for(int i=0;i<siz;i++)
    {
        print+=ch;
        if((i+1)%26==0) ch++;
        if(ch=='z'+1) ch='a';
    }
    cout<<print<<endl;
    cin>>str;
    for(int i=0;i<siz;i++)
        bel[i]+=(str[i]-'a')*26;
    ch='a';
    print="? ";
    for(int i=0;i<siz;i++)
    {
        print+=ch;
        ch++;
        if(ch=='z'+1) ch='a';
    }
    cout<<print<<endl;
    cin>>str;
    for(int i=0;i<siz;i++)
        bel[i]+=str[i]-'a';
    for(int i=0;i<siz;i++)
        ans[bel[i]]=res[i];
    printf("! %s",ans);
    fflush(stdout); 
    return 0;
}