BZOJ4104：[Thu Summer Camp 2015]解密运算—

BZOJ4104：[Thu Summer Camp 2015]解密运算——题解

阅读量：6278 次

发布时间：2019-06-22

本文共 1256 字，大约阅读时间需要 4 分钟。

对于一个长度为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”。

请通过加密后的密文求出加密前的字符串。

很神奇的问题……我的智商果然不够用……

我们知道了每个数是什么，还知道了每个数为结尾时第一个数的排名为多少。

那么我们从0开始查排名我们就能得到第一位数的排名，将这个数作为最后一位，则第二位数就成了第一位，于是查询此时的排名就能知道第二位的排名了……以此类推。

我们有了第x位数的排名，于是我们把所有的字符排个序我们不就知道第x位数是什么了吗。

于是这题我们就做完了。

#include#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                using namespace std;typedef long long ll;const int N=2e5+5;inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}struct node{ int a,rk;}a[N];int n,m;inline int cmp(node a,node b){ return a.a==b.a?a.rk