洛谷$P5329\ [SNOI2019]$字符串 字符串
2024-10-08 02:13:42
正解:字符串
解题报告:
有两个很妙的方法,分别港下$QwQ$
首先为了表示方便,这里和题面一样设$s_i$表示去掉第$i$个字母得到的字符串.另设$lcp(i,j)$表示$suf_i,suf_j$的最长公共前缀
考虑现在如果要比较$s_i$和$s_j$.不妨设$i<j$
首先显然的是$i$之前和$j$之后的字符串都是一样的,于是现在就只要比较$[i,j]$这一段了.
考虑先求出$lcp(i,i+1)$,若$lcp(i,i+1)$的前缀长度大于等于$[i,j]$这一段的长度了,就说明两个字符串相等.
否则就比较$i+lcp(i,i+1)$和$i+1+lcp(i,i+1)$的大小就成.
于是就魔改下$cmp$直接$sort$就成$QwQ$
法二直接一个个考虑.
先从相邻字母不相同的部分分开始想趴$QwQ$.从$s_1$开始考虑,发现$s_1$和其他字母的首位一定不同,所以$s_1$一定要么放开头要么放末尾,放好之后考虑$s_2$,发现是一样的,于是一直这么做下去就完事$QwQ$
欧克现在考虑相邻字母相同?发现如果相邻字母相同也就说这两个删去的效果是一样的,于是考虑缩点($bushi$,把相邻相同的字母删去,就变成了上一个问题,排好序后把缩起来的放回来就好$QwQ$.
这样就可以直接$O(n)$把这题做掉了$QwQ$
$over$
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define gc getchar()
#define ri register int
#define rc register char
#define rb register bool
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i) const int N=1e6+;
int n,len,rl[N];
char str[N]; il int read()
{
rc ch=gc;ri x=;rb y=;
while(ch!='-' && (ch>'' || ch<''))ch=gc;
if(ch=='-')ch=gc,y=;
while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;
return y?x:-x;
}
void dfs(ri nw)
{
if(nw==len){rp(i,rl[nw],n)printf("%d ",i);return;}
if(str[rl[nw]]<str[rl[nw+]]){dfs(nw+);rp(i,rl[nw],rl[nw+]-)printf("%d ",i);return;}
rp(i,rl[nw],rl[nw+]-)printf("%d ",i);dfs(nw+);
} int main()
{
//freopen("5329.in","r",stdin);freopen("5329.out","w",stdout);
n=read();scanf("%s",str+);rl[++len]=;rp(i,,n)if(str[i]!=str[i-])rl[++len]=i;dfs();
return ;
}
最新文章
- varsh4.1 安装清除cache
- struts2视频学习笔记 09-10(struts2处理流程,指定多个struts配置文件)
- [Bhatia.Matrix Analysis.Solutions to Exercises and Problems]ExI.4.5
- 路由器WAN口和LAN口详解
- 使用Interface创建的装饰者实现了必需的方法
- ubuntu 搭建python2.x 抓取环境
- VS2008中C#开发webservice简单实例
- Servlet--HttpServlet实现doGet和doPost请求的原理
- Json数据和对象互转
- byte转bit
- 浅谈Java泛型中的? extends E和?super E
- VTK计算网格模型上的最短路径
- JAVA随机数之多种方法从给定范围内随机N个不重复数
- 004.SMB之guest级别配置
- 华为手机使用objectAnimation异常
- 解决国内经常无法访问Google的方法
- CFGym 100198G 题解
- 读取Properties文件的六种方法
- 015.1 Lock接口
- 贯通Spark Streaming JobScheduler内幕实现和深入思考