首页 > 其他分享 >CF825F - String Compression

CF825F - String Compression

时间:2023-02-23 19:45:38浏览次数:56  
标签:P1 String 复杂度 循环 CF825F 长度 8005 dp Compression

题意:压缩字符串,把字符串分成若干个子串,每个子串可以被压缩成“循环次数 \(+\) 循环节”的形式,求最小长度。

dp 求 lcp

先 \(O(n^2)\) dp 求出所有后缀对的 \(lcp_{x,y}\),(也可以 \(\text{SA}\) \(O(\log n)\) 求,但是本题 \(n=8000\) 还有 \(\dfrac{1}{2}\) 的常数,没必要这么做。

然后我们设 \(dp_{i}\) 表示当前 \(i-1\) 前面的位置都已经压缩完成的最小长度。枚举最小循环节长度 \(j\),一直往后 \(dp\),直到 \(lcp_{i,r}\lt j\) 为止。

对其中所有的 \(i+kj\),将 \([i,i+kj-1]\) 压缩成一个子串进行转移,转移到 \(i+kj\)。提前预处理出每个循环次数和字符串长度的对应关系 \(O(1)\) 转移到 \(i+kj\),转移复杂度 \(O(n\log n)\),总的复杂度是 \(O(n^2\log n)\) 的,但是常数较小,可过。

双模哈希

首先,显而易见的贪心,如果当前确定了要把 \([l,r]\) 压缩成一个子串,则一定选择最小的循环节。因为选择更大的循环节,循环节的长度增加是循环次数长度减少的 \(10\) 倍。

然后,考虑如何计算 \([l,r]\) 中的最小循环节。

我们考虑计算 \(f_{l,r}\) 表示以 \([l,r]\) 为第一个循环节,最多往后循环次数。我们可以从后往前枚举左端点,然后只考虑 \(f_{r+1,r+(r-l+1)}\),因为这是我们从 \(f_{l,r}\) 往后拓展的必经之路。我们可以用字符串哈希 \(O(1)\) 判断两个区间是否相等,从而判断能否从后面进行转移,如果可以,\(f_{l,r}=f_{r+1,r+(r-l+1)}+1\),否则,\(f_{l,r}=1\)。

接下来有一个假做法,就是枚举 \(i\) 之后的最小循环节长度,然后贪心选取尽可能多的循环次数。但是这样会 WA,因为我们可能要留一点字符给后面的循环节。

我们考虑计算 \(g_{l,r}\) 表示 \([l,r]\) 的最小循环节。我们的思路是从小到大枚举,然后使用 \(f_{l,r}\) 往后延申直到超出 \(f_{l,r}\) 的次数。这样就是对每个 \([l,r]\) 都循环 \(f_{l,r}\) 次对 \(g_{l,l+k\times len}\) 进行贡献。复杂度是 \(O(n^2\log n)\),和前面的做法没什么区别。

但是我们如果使用一些线性筛的思想,使得每个 \(g_{l,r}\) 只被自己的最小循环节贡献,如果当前的循环节已经存在循环节,就不往更大的区间进行贡献。我们发现这是正确的。

首先,如果一个长度 \(n\) 的区间存在两种循环节,长度分别是 \(x\) 和 \(y\),那么一定存在 \(\gcd(x,y)\) 长度的循环节。我们假设 \(x<y\),考虑所有长度为 \(y\) 的循环节将所有长为 \(\gcd(x,y)\) 的单元分成 \(n/y\) 段,每段都有 \(y\) 个不同的,而划分出 \(y\) 个剩余类,例如 0 1 2 0 1 2 0 1 ... 。然后考虑 \(x\) 对 \(y\) 的覆盖,因为 \(x'=\dfrac{x}{\gcd(x,y)}\) 和 \(y'=\dfrac{y}{\gcd(x,y)}\) 是互质的,所以其唯一重合的地方是 \(n'=\dfrac{n}{\gcd(x,y)}\)。那么从 \(0\) 开始每次跳 \(x'\) 遍历可以遍历 \(y'\) 的整个剩余系。

或者说,对 \(y'\) 的剩余系而言,因为 \(x'\) 和 \(y'\) 互质,所以设 \(S\) 是模 \(y\) 的剩余系,则 \(xS=S\),即\(0,x',2x',3x',\cdots,(y'-1)x'\) 模 \(y'\) 两两不同余。则所有模 \(x'\) 意义下的等价类 \(0\) 都两两不同的对应了模 \(y\) 意义下的所有等价类恰好一次,得到所有 \(\gcd(x,y)\) 长的单元都是相同的,则存在长度 \(\gcd(x,y)\) 的循环节。

那么,任何的区间 \([l,r]\) 都存在唯一最小的循环节 \(s\),使得任意其他循环节 \(t\),都存在 \(k|s|=|t|\)。那么在 \(s\) 贡献到 \([l,r]\) 的同时,其其他循环节也都被贡献到了,由于先枚举小的区间,我们就不会调用 \([l,r]\) 的任意其他循环节覆盖别人,所以计算 \(g_{l,r}\) 的过程中,每个\([l,r]\) 只被扫到一次,总复杂度 \(O(n^2)\)。

最后,设 \(dp_i\) 表示 \(i-1\) 以前都成功配对,然后枚举当前压缩的大区间右端点 \(r\),使用其最小循环节进行贡献,预处理每个数字对应的长度,就可以做到 \(O(1)\) 计算单个转移,总的转移是 \(O(n)\) 的,这一环节的复杂度也是 \(O(n^2)\)。

从而,整个算法的复杂度是 \(O(n^2)\)。注意哈希和匹配的常数较大,可能成为算法瓶颈(大常数 \(O(n^2)\))

const ll P1=998244353,P2=1000000007,S1=114,S2=191;
ll h1[8005],h2[8005],pw1[8005],pw2[8005],ipw1[8005],ipw2[8005];
int cnt[8005][8005],bit[8005],dp[8005];
int f[8005][8005];
st s;int n;
inline pll hsh(int l,int r){
	ll r1=(h1[r]-h1[l-1]*pw1[r-l+1]%P1+P1)%P1;
	ll r2=(h2[r]-h2[l-1]*pw2[r-l+1]%P2+P2)%P2;
	return pll(r1,r2);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>s;n=s.size();s='$'+s;
	rp(i,n)h1[i]=(h1[i-1]*S1+s[i]-'a')%P1;
	rp(i,n)h2[i]=(h2[i-1]*S2+s[i]-'a')%P2;
	pw1[0]=pw2[0]=ipw1[0]=ipw2[0]=1;
	rp(i,n)pw1[i]=pw1[i-1]*S1%P1;
	rp(i,n)pw2[i]=pw2[i-1]*S2%P2;
	rep(i,1,9)bit[i]=1;
	rep(i,10,99)bit[i]=2;
	rep(i,100,999)bit[i]=3;
	rep(i,1000,8000)bit[i]=4;
	per(l,1,n)rep(r,l,n){
		int len=r-l+1;cnt[l][r]=1;
		if(r+len<=n&&hsh(l,r)==hsh(r+1,r+len))cnt[l][r]=cnt[r+1][r+len]+1;
	}
	dp[1]=0;
	rep(i,2,n+1)dp[i]=1e9;
	rep(l,1,n)rep(r,l,n)if(f[l][r]==0){
		int len=r-l+1;
		for(int i=1;l+i*len-1<=n&&i<=cnt[l][r];i++){
			f[l][l+i*len-1]=i;
		}
	}
	rep(l,1,n)rep(r,l,n)
		dp[r+1]=min(dp[r+1],dp[l]+bit[f[l][r]]+(r-l+1)/f[l][r]);
	cout<<dp[n+1]<<endl;
	return 0;
}
//Crayan_r

标签:P1,String,复杂度,循环,CF825F,长度,8005,dp,Compression
From: https://www.cnblogs.com/jucason-xu/p/17149171.html

相关文章

  • String集合拼多个or,模糊查询。mybatis-plus-构造器的写法
    List<String>list=newArrayList<>();QueryWrapper<Object>queryWrapper=newQueryWrapper<>();queryWrapper.and(CollUtil.isNotEmpty(list),qw->{list.fo......
  • Typecho——Argument 1 passed to Typecho\Router::get() must be of the type strin
    前言开发EasyBe主题的置顶功能时候,测试的时候出现了Typecho\Router::get()报错,根据对应的报错信息查看了下源码后解决了该问题;内容查询SQL//获取全部文章functionge......
  • LZ4 - Extremely fast compression
      zephyrproject-rtos/lz4:ExtremelyFastCompressionalgorithm(github.com) LZ4-ExtremelyfastcompressionLZ4islosslesscompressionalgorithm,prov......
  • Java 截取字符串 split 方法与 substring 方法简单比较
    Java截取字符串split方法与substring方法简单比较文章目录​​Java截取字符串`split`方法与`substring`方法简单比较​​​​0、结论​​​​1、截取目标​​​​......
  • const char* 与string
    string是c++标准库里面其中一个,封装了对字符串的操作,实际操作过程我们可以用constchar*给string类初始化a)string转constchar*strings=“abc”;constcha......
  • C++面对对象:实现string类
    1//string.h2#pragmaonce3classString{4public:5String(constchar*cstr=0);6String(constString&str);7~String();89......
  • 黑马stringbuilder
    StringBuilder作用:提高string的操作效率ctrl+alt+m可以快速的抽取方法使用的stringbuilder所花的时间连一秒都花不了packagecom.itheima.api.stringbuilder;publ......
  • C#的string是一种糟糕的设计吗?
    前言    最近有人在某平台提问“C#的string是一种糟糕的设计吗?”,他认为官方为字符串做了很多内部优化处理,这种处理增加了理解成本,为什么不能提供char[]指针处理方案呢......
  • JSON.toJSONString(object, SerializerFeature.WriteMapNullValue);第二个参数作用
      这里箭头指向的位置,因为sent-1中的value为空,所以并未打印出来。第二个使用:JSON.toJSONString(map,SerializerFeature.WriteMapNullValue)指定序列化方式就打印出......
  • CF623A Graph and String
    个人思路:显然,和其他所有点连边的点都是b。我们接下来不考虑这些点。剩余a和c必然自己形成一个连通块,每个点与块内其他所有点连边。超过\(2\)个连通块,或存在点没......