YZOJ P2163 [THUSC2015]解密运算
时间限制：1000MS 内存限制：131072KB
难度：\(7.0\) （自评）
-
题目描述
对于一个长度为 \(N\) 的字符串，我们在字符串的末尾添加一个特殊的字符 “.” 。之后将字符串视为一个环，从位置 \(1,2,3,\cdots,N+1\) 为起点读出 \(N+1\) 个字符，就能得到 \(N+1\) 个字符串。
比如对于字符串 “ABCAAA”，我们可以得到这 \(N+1\) 个串：
|
1 2 3 4 5 6 7 |
ABCAAA. BCAAA.A CAAA.AB AAA.ABC AA.ABCA A.ABCAA .ABCAAA |
接着我们对得到的这 \(N+1\) 个串按字典序从小到大进行排序（注意特殊字符 “.” 的字典序小于任何其他的字符）结果如下：
|
1 2 3 4 5 6 7 |
.ABCAAA A.ABCAA AA.ABCA AAA.ABC ABCAAA. BCAAA.A CAAA.AB |
最后，将排序好的 \(N+1\) 个串的最后一个字符取出，按照顺序排成一个新的字符串，也就是上面这个表的最后一列，就是加密后的密文 “AAAC.AB” 。
请通过加密后的密文求出加密前的字符串。
-
输入格式
第一行有两个整数 \(N, M\)，分别表示加密前的字符串长度和字符集大小，其中字符用整数 \(1,2,3,\cdots,M\) 编号，添加的特殊字符 “.” 用 \(0\) 编号。
第二行为 \(N+1\) 个整数，表示加密后的字符串。
-
输出格式
输出仅一行，包含 \(N\) 个整数，用空格隔开，依次表示加密前字符串中每个字符的编号。
-
样例输入
|
1 2 |
6 3 1 1 1 3 0 1 2 |
-
样例输出
|
1 |
1 2 3 1 1 1 |
-
数据规模与约定
\(N,M \leq 200000\) 。
Source: BZOJ 4104
挺神仙的一道题目，看得懂的人都看得懂，看不懂的人就看不懂。
注意到加密后的字符串其实还是原来字符串里的那几个字符，就是顺序变了一下而已。
由于字符串是循环的，所以知道了当前串中最后一个字符的排名，也相当于知道了这个字符在原串中下一个字符的排名。
所以把加密串拿去排序，这样就知道了某一个字符在原串中的排名。
问题是相同的字符，但是幸好的是输入的数据就已经帮我们排好序了，所以以下标为第二关键字排序即可。
这样就可以根据最小的 ‘.’ ，跳第二关键字，在排好序的序列里找到原串了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #include <algorithm> inline int getnum() { register char c=0; while(!(c>='0' && c<='9')) c=getchar(); register int a=0; while(c>='0' && c<='9') a=a*10+c-'0',c=getchar(); return a; } std::pair<int,int>a[205050]; int main() { register int N=getnum(),M=getnum(); for(register int i=1;i<=N+1;i++) a[i]=std::make_pair(getnum(),i); std::sort(&a[1],&a[N+2]); for(register int i=1,t=a[1].second;i<=N;i++) printf("%d ",a[t].first),t=a[t].second; return 0; } |