洛谷 P1124 文件压缩
2024-10-01 08:39:03
题目背景
提高文件的压缩率一直是人们追求的目标。近几年有人提出了这样一种算法,它虽然只是单纯地对文件进行重排,本身并不压缩文件,但是经这种算法调整后的文件在大多数情况下都能获得比原来更大的压缩率。
题目描述
该算法具体如下:对一个长度为n的字符串S,首先根据它构造n个字符串,其中第i个字符串由将S的前i-1个字符置于末尾得到。然后把这n个字符串按照首字符从小到大排序,如果两个字符串的首字符相等,则按照它们在S中的位置从小到大排序。排序后的字符串的尾字符可以组成一个新的字符串S’,它的长度也是n,并且包含了S中的每一个字符。最后输出S’以及S的首字符在S’中的位置p。举例:
S:example
1、构造n个字符串
example
xamplee
ampleex
mpleexa
pleexam
leexamp
eexampl
2、将字符串排序
ampleex
example
eexampl
leexamp
mpleexa
pleexam
xamplee
3、压缩结果
xelpame S’
7 p
由于英语单词构造的特殊性,某些字母对出现的频率很高,因此在S’中相同的字母有很大几率排在一起,从而提高S’的压缩率。虽然这种算法利用了英语单词的特性,然而在实践的过程中,人们发现它几乎适用于所有的文件压缩。
请你编一个程序,读入S’和p,输出字符串S。
输入输出格式
输入格式:
输入文件共有三行,第1行是一个整数n(1<=n<=10000),代表S’的长度,第2行是字符串S’,第3行是整数p。
输出格式:
仅包含一行S。
输入输出样例
输入样例#1:
7
xelpame
7
输出样例#1:
example
思路:见大佬博客。
#include<iostream>
#include<map>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s[],ans[];
int n,p,tot,num[],l[],r[];
int main(){
scanf("%d",&n);
scanf("%s",s+);
scanf("%d",&p);
for(int i=;i<=n;i++) num[s[i]-'a']++;
for(int i=;i<;i++){
l[i]=r[i-]+;
r[i]=l[i]+num[i]-;
}
int now=l[s[p]-'a'];
while(tot<n){
ans[tot]=s[now];
now=r[s[now]-'a']--;
tot++;
}
for(int i=n-;i>=;i--) cout<<ans[i];
}
最新文章
- Openstack api 学习文档 &; restclient使用文档
- Alpha版本测试报告
- 获取屏幕分辨率(C/C++)
- glassfish 日志输出配置
- android检查自动升级
- C#获取网页内容 (WebClient、WebBrowser和HttpWebRequest/HttpWebResponse)
- 关于EF第一次加载慢或过一段时间不访问时再次访问加载慢问题的总结
- CloneZilla + Parkomat 实现网络备份
- 百度资深架构师带你深入浅出一致性Hash原理
- caffe安装教程(Ubuntu14+GPU+pycaffe+anaconda2)
- [UWP]为什么ContentControl的ControlTemplate里放两个ContentPresenter会出问题(绕口)
- kafka-producer partitioner.class的使用
- 运行scrapy crawl (文件名)时显示invalid syntax和no modle &#39;win32api&#39;解决方案
- Hbase Shell 数据操作说明
- php+js的 authcode 混淆加密和解密,php和js可以通用加密和解密
- HTML语义化简介思维导图
- AngularJS自定义Directive初体验
- 剑指offer四十三之左旋转字符串
- 使用 script 命令记录用户操作行为
- CCF CSP 201403-2 窗口