【BZOJ4104】解密运算 [暴力]
2024-10-20 17:23:35
解密运算
Time Limit: 10 Sec Memory Limit: 512 MB
[Submit][Status][Discuss]
Description
对于一个长度为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”。
请通过加密后的密文求出加密前的字符串。
Input
第一行有两个整数N,M,分别表示加密前的字符串长度和字符集大小,其中字符用整数1,2,3,...,M编号,添加的特殊字符“."用0编号。
第二行为N+1个整数,表示加密后的字符串。
Output
输出仅一行,包含N个整数,用空格隔开,依次表示加密前字符串中每个字符的编号。
Sample Input
6 3
1 1 1 3 0 1 2
1 1 1 3 0 1 2
Sample Output
1 2 3 1 1 1
HINT
N,M<=200000
Solution
显然,按照权值(即这个字符串首字母)为第一关键字,位置(即这个字符后面的串的排名)为第二关键字排序。
然后这时候权值就是矩阵的第一列。
形如:
*ABCD
-----
-----
这时第一行后面ABCD的排名,显然就是读入中*的位置,因为*作为ABCD*的最后一个字符。
比如ABCD*排名为x,那么这时候 A 显然在矩阵第一列中的第x个,输出即可。
Code
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<queue>
using namespace std;
typedef long long s64; const int ONE = 2e6 + ;
const s64 INF = 1e18; int n, m;
struct power
{
int val, pos;
}a[ONE]; int get()
{
int res=,Q=;char c;
while( (c=getchar())< || c> )
if(c=='-')Q=-;
res=c-;
while( (c=getchar())>= && c<= )
res=res*+c-;
return res*Q;
} int cmp(const power &a, const power &b)
{
if(a.val != b.val) return a.val < b.val;
return a.pos < b.pos;
} int main()
{
n = get(); m = get();
for(int i = ; i <= n + ; i++)
a[i] = (power){get(), i};
sort(a + , a + n + + , cmp); int pos = ;
for(int i = ; i <= n; i++)
{
pos = a[pos].pos;
printf("%d ", a[pos].val);
}
}
最新文章
- winhttp demo
- java笔记——Java关键字static、final使用小结
- Sublime Text 使用介绍、全套快捷键及插件推荐
- 【转】yahoo前端优化军规
- new一个数组,delete释放内存
- 每日一练(写不出心得体会了!毕竟哪有那么多心得好写。然后看github上有很多不错的题目。分享一下!)
- MVC学习系列——记一次失败面试后,感想。
- OJ题目分类
- nopCommerce 3.3正式发布及新增功能改进
- Padding Borders Outlines Margins
- cookie跨域和js跨域问题
- Linux 中改变默认文件打开方式的位置
- winform界面特效470多例
- Netty原理剖析
- PHP 错误解决锦集
- python的Socket网络编程 使用模板
- 搭建一个SpringBoot项目
- linux系统中,tee命令的使用
- Array.prototype.forEach数组遍历
- WebStorm keyboard shortcuts
热门文章
- Notes of the scrum meeting before publishing2(12.18)
- error : Web 项目“RealEstate.Web”的 URL“http://localhost:20000”已配置为将 IIS 用作 Web 服务器,但是当前在 IIS Express W
- c#中语句的先后顺序对结果的影响
- 简单java死锁设计002
- linux 装redmine
- 【ASP.NET Core】ASP.NET Core API 版本控制
- poj 1469 COURSES (二分匹配)
- [CQOI2012]交换棋子 网络流
- BZOJ1208:[HNOI2004]宠物收养所——题解
- HDOJ(HDU).1059 Dividing(DP 多重背包+二进制优化)