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

https://www.lydsy.com/JudgeOnline/problem.php?id=4104

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

#include<cmath>

#include<stack>

#include<queue>

#include<cstdio>

#include<cctype>

#include<vector>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N=2e5+;

inline int read(){

    int X=,w=;char ch=;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),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<b.rk:a.a<b.a;

}

int main(){

    n=read(),m=read();

    for(int i=;i<=n;i++){

    a[i].a=read();a[i].rk=i;

    }

    sort(a,a+n+,cmp);

    int t=a[].rk;

    for(int i=;i<=n;i++){

    printf("%d ",a[t].a);

    t=a[t].rk;

    }

    return ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

巴特西

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

最新文章

热门文章