FZOJβ #31.字符串
2024-08-29 10:21:03
http://1572m36l09.iask.in:30808/problem/31
首先转化为保留尽量少的段使得字典序最大。考虑逐字符确定,
显然我们可以将相同的连续字符缩在一起。注意到字典序最大的
字符一定会在前缀中保留尽量多次,我们可以将字符相同的连续
段按照出现次数排序,并逐一确定。在确定最后一段时,我们需
要考虑剩余部分后缀对串的大小的影响。使用后缀数组处理,时
间复杂度为 O(|s| log |s|)
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> using namespace std; ; struct node { int l,r; }a[N]; vector<node> vct[]; int t,K,n,m,i,j,k,l,x,y,sa[N],rk[N],Y[N],c[N],len; char s[N],ans[N]; bool cmp(node a,node b) { return a.l<b.l; } bool cmq(node a,node b) { if(a.r-a.l!=b.r-b.l) return a.r-a.l>b.r-b.l; return a.l<b.l; } void add(char c,int x) { while(x--) ans[++len]=c; } int main() { freopen("string.in","r",stdin); freopen("string.out","w",stdout); scanf("%d",&t); while(t--) { scanf(); )//注意K==0时要特判 { puts(s+); continue; } n=strlen(s+); m=; len=; ;i<=n;++i) rk[i]=s[i]; ;i<=m;++i) c[i]=; ;i<=n;++i) c[rk[i]]++; ;i<=m;++i) c[i]+=c[i-]; ;i<=n;++i) sa[c[rk[i]]--]=i; ;k<=n;k<<=) { ,l=;i<=n;++i) Y[++l]=i; ;i<=n;++i) if(sa[i]>k) Y[++l]=sa[i]-k; ;i<=m;++i) c[i]=; ;i<=n;++i) c[rk[i]]++; ;i<=m;++i) c[i]+=c[i-]; ;--i) sa[c[rk[Y[i]]]--]=Y[i]; ;i<=n;++i) Y[i]=rk[i]; rk[sa[]]=m=; ;i<=n;++i) rk[sa[i]]=(Y[sa[i]]==Y[sa[i-]]&&(sa[i]+k>n?:Y[sa[i]+k])==(sa[i-]+k>n?:Y[sa[i-]+k])?m:++m); if(rk[sa[n]]==n)//SA的一个优化 break; } rk[n+]=;//注意细节!! ;i<;++i) vct[i].clear(); ;i<=n;i=j) { for(j=i;j<=n&&s[i]==s[j];++j); vct[s[i]-}); } ,j=k=;i>=;--i) { l=vct[i].size(); if(!l) continue; sort(vct[i].begin(),vct[i].end(),cmp); ;x<l&&vct[i][x].l<=j;++x); if(x>=l) continue; ) { add(i+); j=vct[i][x++].r; } if(l-x+k<K) { j=vct[i][l-].r; k+=l-x; for(;x<l;++x) add(i+); continue; } sort(vct[i].begin()+x,vct[i].end(),cmq); ;++x) { add(i+); ++k; j=max(j,vct[i][x].r); } k=vct[i][x].r-vct[i][x].l+; add(i+'a',k); ;x<l&&vct[i][x].r-vct[i][x].l+==k;++x) ||rk[max(j+,vct[i][x].r+)]>rk[y]) y=max(j+,vct[i][x].r+); for(;y<=n;++y) add(s[y],); j=n; break; } ans[len+]=; puts(ans+); } ; }
最新文章
- Adaboost 算法
- .htaccess更改目录下的默认主页
- cocos2d-x 2.2 移植wp8遇到的坑
- jquery mobile基本结构搭建
- 转:LESS CSS 框架简介
- Lua 字符串函数小结
- 在sqlite中使用索引
- 解决KVM中鼠标不同步问题
- 是什么让C#成为最值得学习的编程语言
- 35.app后端搜索入门
- Windows下Pytesser安装
- vivo怎么录屏 手机录制屏幕详细教程
- springmvc mybatis shiro ios android构建cms系统
- Luogu P2661 信息传递
- 初学html的单词笔记
- asm 32 /64
- Golang 获取MD5的方法
- (KMP扩展 利用循环节来计算) Cyclic Nacklace -- hdu -- 3746
- idea在debug模式启动非常慢,日志正常debug模式一直在启动中状态
- hdoj-1251-统计难题【map】
热门文章
- AtCoder Beginner Contest 052
- 纯CSS,多个半圆以中心点旋转
- 洛谷P2759 奇怪的函数
- uoj#36. 【清华集训2014】玛里苟斯(线性基+概率期望)
- js原型和构造函数
- pyinstaller打包多个py文件仍报错ModuleNotFoundError: No module named &#39;xxx&#39;
- EF下使用自定义的connectionString避免数据库密码泄露
- [Java]LinkedHashMap实现原理
- ASP .NET Core 2.1 HTTP Error 502.5 – Process Failure
- 关于AQS——独占锁特性+共享锁实现(二)