首页 > 代码库 > [Thu Summer Camp 2015]解密运算
[Thu Summer Camp 2015]解密运算
4104: [Thu Summer Camp 2015]解密运算
Time Limit: 10 Sec Memory Limit: 512 MBDescription
对于一个长度为N的字符串，我们在字符串的末尾添加一个特殊的字符"."。之后将字符串视为一个环，从位置1,2,3,...,N+1为起点读出N+1个字符，就能得到N+1个字符串。
比如对于字符串“ABCAAA”，我们可以得到这N+1个串：
ABCAAA.
BCAAA.A
CAAA.AB
AAA.ABC
AA.ABCA
A.ABCAA
.ABCAAA
接着我们对得到的这N+1个串按字典序从小到大进行排序（注意特殊字符“.”的字典序小于任何其他的字符）结果如下：
.ABCAAA
A.ABCAA
AA.ABCA
AAA.ABC
ABCAAA.
BCAAA.A
CAAA.AB
最后，将排序好的N+1个串的最后一个字符取出，按照顺序排成一个新的字符串，也就是上面这个表的最后一列，就是加密后的密文“AAAC.AB”。
请通过加密后的密文求出加密前的字符串。
Input
第一行有两个整数N,M，分别表示加密前的字符串长度和字符集大小，其中字符用整数1,2,3,...,M编号，添加的特殊字符“."用0编号。
第二行为N+1个整数，表示加密后的字符串。
Output
输出仅一行，包含N个整数，用空格隔开，依次表示加密前字符串中每个字符的编号。
Sample Input
6 3
1 1 1 3 0 1 2
1 1 1 3 0 1 2
Sample Output
1 2 3 1 1 1
HINT
#i (i=1~4) N=5*(i+1) M<=3
#5~6 N,M<=50 字符串中字符互不相同
#7~8 N,M<=1000 字符串中字符互不相同
#9~12 N,M<=1000
#13~#20 N,M<=200000
对密文以字母为第一关键字，位置为第二关键字，排序
#include<cstdio>#include<algorithm>#define N 200011using namespace std;struct node{ int ch; int id;}e[N];int n,m;bool cmp(node p,node q){ if(p.ch!=q.ch) return p.ch<q.ch; return p.id<q.id;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n+1;i++) scanf("%d",&e[i].ch),e[i].id=i; sort(e+1,e+n+2,cmp); int now=e[1].id; while(now!=1) { printf("%d ",e[now].ch); now=e[now].id; }}
[Thu Summer Camp 2015]解密运算
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。