NOIP模拟题 秘密信息 题解【字符串】【快速排序】【贪心】

点击量：154

   这个题主要是手玩找规律吧（不过最近怎么老看到手玩这个名词

目录

题目描述

Irene想用一下的方法加密一条信息(这是她从密码学书上自学来的)：

假定这条信息可以用一个字符串S表示，其中S=BCAAD.（其中’.’代表字符串结尾）。Irene首先把S的所有循环同构串写下来(所谓循环同构即是不断地把字符串开头的字符移动到尾端)：

BCAAD.

CAAD.B

AAD.BC

AD.BCA

D.BCAA

.BCAAD

接下来她会把这些字符串都排序:

.BCAAD

AAD.BC

AD.BCA

BCAAD.

CAAD.B

D.BCAA

接下来她会把这些字符串的最后一位按照顺序写下来得到加密串。

 

T=DCA.BA

 

现在Irene发现在密码学的书上写着一条来历不明的加密串T。她迫切地想知道，如果信息是按照这种方式加密的，那么原串是什么？

 

输入输出格式

输入格式：

一行一个由大写字母构成，长度为N的字符串(但字符串有且只有一个’.’）。

 

输出格式：

输出一行，输出原串。数据保证有唯一解。

 

输入输出样例

输入样例#1：

PH.EL

输出样例#1：

HELP.

输入样例#2：

BBA.AAA

输出样例#2：

ABAAB.

说明

对于20%的数据，2<=N<=10；

 

对于50%的数据，2<=N<=27,字符串内部的字母互不相同。

 

对于100%的数据，2<=N<=30000。

   首先我们以样例1为例，如果加密后的文字是这样的

????P
????H
????.
????E
????L

   由每行第一个字符是顺序排列，可以把第一行写出来：

.???P
E???H
H???.
L???E
P???L

   因为所有字符串都是“循环同构”的，所以这时我们就知道了各字符串之间的关系——在没有重复字母的情况下，N-1组关系是充要的。可以看出P->. , H->E , .->H , E->L , L->P .把.放在最后，就得出了这个字符串。（50pts）

   当字符串有重复的时候，就不能用这样的方法了，因为每个字符串可能连接多个不同的/相同的字符，这种做法得出的答案就不唯一了。

   我们来手玩一下样例2：

?????B
?????B
?????A
?????.
?????A
?????A

   如果第一列是顺序排列：

.????B
A????B
A????A
A????.
B????A
B????A

   这时候，关系就比较麻烦了，我们如果简单找规律是找不到的。我们试着把这个方阵进一步填充（根据已知的6种关系和字典序大小）：

.A???B
AA???B
AB???A
AB???.
B.???A
BA???A

   因为字母在字符串中的位置不同，字母可以有一个特征值，就是第几个在字符串中出现，我们可能会发现，只要把这些字母区分开就可以了。如何区分，我们再来观察一下：

.ABAAB
AAB.AB
AB.ABA
ABAAB.
B.ABAA
BAAB.A

   可以看出，在最后一列第i次出现的A，和在第一列第i次出现的A总是等价的。我们多试几次，得出了一致的结论，我们把出现在不同的位置的相同字母定义为不同的字母（字典序相接），和50pts的做法一样做，这个题就解决了。

   我用了pair，代码可能看上去不是很整齐。

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using std::pair;
char c[30500];
char c1[30500];

int cnt1[30],cnt2[30];
pair<int,int> nxt[30200][30];//将'.'的信息定义为28
int main()
{
    memset(cnt1,0,sizeof(cnt1));
    memset(cnt2,0,sizeof(cnt2));
    scanf("%s",c);
    int len=strlen(c);
    for(int i=0;i<=len;i++)
        c1[i]=c[i];
    std::sort(c1,c1+len);
    //c1是前面顺序 c是后面原序
    for(int i=0;i<len;i++)
        if(c[i]=='.')
        {
            nxt[1][28].first=c1[i]-'A';
            nxt[1][28].second=++cnt1[c1[i]-'A'];
        }
        else
        {
            nxt[++cnt2[c[i]-'A']][c[i]-'A'].first=(c1[i]=='.')?28:(c1[i]-'A');
            nxt[cnt2[c[i]-'A']][c[i]-'A'].second=++cnt1[(c1[i]=='.')?28:(c1[i]-'A')];
        }

    int i=1,j=28;
    while(nxt[i][j].first!=28)
    {
        printf("%c",nxt[i][j].first+'A');
        int a=nxt[i][j].first,b=nxt[i][j].second;
        i=b,j=a;
    }
    printf(".\n");
    return 0;
}