【BZOJ 4104】 4104: [Thu Summer Camp 2015]解密运算 （智商）

【分析】

　　其实是好分析的，我太蠢了。

　　看样例：【图画得我好辛苦啊】

　　

　　你知道最后一列的，就知道了元素的组成，还有*的位置你就知道第一个数排第几，你可以得出第一位是A。

　　但是是哪个A呢？给出的序列有4个A，前4个字符串的第一位都是A，而这个A排在第四位，说明他后面的字符串跟前面的比是最大的。

　　

　　而对于后面的字符串的比较其实序列也已经给出，看上图，红框的是一样的，他其实已经给你排好序了。

　　所以，这个A就是加密序列中的第四个A！

　　以此类推，可以知道第二个字符排第几，可以求出整个序列了。

　　

　　具体做法看代码，真心短。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 #define Maxn 200010

 struct node{int x,id;}t[Maxn];

 bool cmp(node x,node y) {return x.x==y.x?x.id<y.id:x.x<y.x;}

 int main()

 {

     int n,m;

     scanf("%d%d",&n,&m);

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

     {

         scanf("%d",&t[i].x);

         t[i].id=i;

     }

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

     int nw=t[].id;

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

     {

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

         nw=t[nw].id;

     }

     return ;

 }

2017-04-08 15:47:56