Educational Codeforces Round 60 (Rated for Div. 2) E. Decypher the String

题目大意：这是一道交互题。给你一个长度为n的字符串，这个字符串是经过规则变换的，题目不告诉你变换规则，但是允许你提问3次：每次提问你给出一个长度为n的字符串，程序会返回按变换规则变换后的字符串，提问3次后你需要猜出这个字符串。解法是学习https://blog.csdn.net/baiyifeifei/article/details/87807822 这个博主的，借用了进制的思想非常巧妙。

解法：对于某个位置的来源位置我们设为x，因为26*26*26>10000，那么x可以唯一表示为x=a*26*26+b*26+c。那么我们只要想办法求出a，b，c就能得到它的来源位置。

那么怎么利用三次询问求a，b，c？我们首先构造（26*26个a) (26*26个b) (26*26个c)......(26*26个z)，设此位置变换后的字符为c[0],那么a=c[0]-'a'（可以理解为a=x/(26*26)=c[0]-'a'）。道理类似的我们下一次构造（26个a) (26个b) (26个c) ......(26个d）的字符串让程序变换，此时变换后的字符为c[1]，那么b=c[1]-'a'（可以理解为b=x%(26*26) /26=(b*26+c)/26=c[1]-'a'），这里的b可能有点儿难理解，为什么是这样得到的c[1]就是(b*26+c)/26？因为前一个询问我们已经确定x在a这一个(26*26)的大块里面了，那么我们只需要考虑这个大块，把这个大块再细分为26块看看返回什么值就能知道x在a这个大块的哪一个小块b里面。道理类似的最后构造(abc..z)(abc..z)...(abc..z)得到c=c[2]-'a'。

那么我们就得到该位置的来源是a*26*26+b*26+c，问题得到解决。

如果还是感觉难以理解，可以看看代码再仔细想想：

#include<bits/stdc++.h>

using namespace std;

const int N=+;

int n;

char s[N],q[][N],g[][N],ans[N];

int main()

{

    scanf("%s",s);

    n=strlen(s);

    for (int i=;i<n;i++) {

        q[][i]=(i/(*)%+'a');

        q[][i]=(i/%+'a');

        q[][i]=(i%+'a');

    } 

    for (int i=;i<;i++) {

        printf("? %s\n",q[i]);

        fflush(stdout);

        scanf("%s",g[i]);

    }

    for (int i=;i<n;i++) {

        int tmp=(g[][i]-'a')**+(g[][i]-'a')*+(g[][i]-'a');

        ans[tmp]=s[i];

    }

    printf("! %s",ans);

    return ;

}

巴特西

Educational Codeforces Round 60 (Rated for Div. 2) E. Decypher the String

最新文章

热门文章