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

作者: wjyyy 分类: 字符串,快速排序,枚举,模拟,解题报告 发布时间: 2018-06-21 16:17

点击量:12

 

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

 

题目描述

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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */