【BZOJ 4104】 4104: [Thu Summer Camp 2015]解密运算 (智商)
2024-10-21 05:08:09
4104: [Thu Summer Camp 2015]解密运算
Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 370 Solved: 237Description
对于一个长度为N的字符串,我们在字符串的末尾添加一个特殊的字符"."。之后将字符串视为一个环,从位置1,2,3,...,N+1为起点读出N+1个字符,就能得到N+1个字符串。
比如对于字符串“ABCAAA”,我们可以得到这N+1个串:ABCAAA.BCAAA.ACAAA.ABAAA.ABCAA.ABCAA.ABCAA.ABCAAA接着我们对得到的这N+1个串按字典序从小到大进行排序(注意特殊字符“.”的字典序小于任何其他的字符)结果如下:.ABCAAAA.ABCAAAA.ABCAAAA.ABCABCAAA.BCAAA.ACAAA.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 2Sample Output
1 2 3 1 1 1HINT
#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<=200000Source
【分析】
其实是好分析的,我太蠢了。
看样例:【图画得我好辛苦啊】
你知道最后一列的,就知道了元素的组成,还有*的位置你就知道第一个数排第几,你可以得出第一位是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
最新文章
- 我的emacs配置
- mysql数据去除重复及相关优化(转)
- Android中JNI的使用方法
- android .apk安装时遇到NSTALL_FAILED_CONTAINER_ERROR错误
- Redis学习笔记三:多机数据库的实现
- 微软2017校招笔试题2 composition
- page cache 与 page buffer 转
- android退出登陆后,清空之前所有的activity,进入登陆主界面
- c++ 虚继承
- 【idea】移动下载站
- ASP.NET笔记之 ListView 与 DropDownList的使用(解决杨中科视频中的问题)
- C++中的智能指针(auto_ptr)
- c语言计算过程中的过程转换
- Floyd-Warshall算法计算有向图的传递闭包
- LINUX介绍
- Linux下Zookeeper的安装
- Webpack按需加载一切皆模块
- OSI 7层 TCP/IP 4层
- B+/-Tree原理
- python装饰器三种装饰模式的简单理解