欢迎访问 如意编程网!

如意编程网

当前位置: 首页 > 编程资源 > 编程问答 >内容正文

编程问答

CF1129D Isolation(分块+DP)

发布时间:2024/7/5 编程问答 3 豆豆
如意编程网 收集整理的这篇文章主要介绍了 CF1129D Isolation(分块+DP) 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

一个很显然的DP方程式:f[i]=Σf[j],其中j<i且在[j+1,i]中出现1次的数不超过k个

乍一看挺神仙的,只会O(n^2),就是对于每个位置从后向前扫一遍,边扫边统计出现1次的数的个数。不难发现,同一个数第一次出现时cnt++,第二次出现时cnt--,后面没有变化这不是废话吗?!

于是可以考虑记录一个后缀和,s[i]表示cnt的大小,然后从当前位置开始从右向左第一次出现的值为1,第二次出现的值为-1,之后为0。修改记录lst数组表示该数上次的位置即可。然后每次走一步只对一个数产生影响,就是只对两段的s值产生影响,线段树显然不能够维护一段某个值出现的次数(实际可能能够用高级数据结构但我不会),于是可以采用暴力美学:分块!

对每一块打个标记delta[i]表示块i的变化量(整体增减才计入),cnt[i]表示位置i进行单独修改后的值,sum[i][j]表示第i个块为值为j的f值之和。暴力修改,复杂度O(n^1.5),可以通过。

#include<bits/stdc++.h> using namespace std; const int N=1e5+7,mod=998244353; int n,m,B,a[N],pos[N],bel[N],lst[N],f[N],cnt[N],delta[440],ans[440],sum[440][N]; void update(int u,int v) {int t=bel[u];sum[t][cnt[u]]=(sum[t][cnt[u]]-f[u]+mod)%mod;if(cnt[u]+delta[t]<=m)ans[t]=(ans[t]-f[u]+mod)%mod;cnt[u]+=v;sum[t][cnt[u]]=(sum[t][cnt[u]]+f[u])%mod;if(cnt[u]+delta[t]<=m)ans[t]=(ans[t]+f[u])%mod; } void add(int u,int v,int w) {if(u>v)return;int p=bel[u],q=bel[v];if(p+1>=q){for(int i=u;i<=v;i++)update(i,w);return;}for(int i=u;bel[i]==p;i++)update(i,w);for(int i=v;bel[i]==q;i--)update(i,w);for(int i=p+1;i<q;i++){if(w>0)if(m-delta[i]>=0)ans[i]=(ans[i]-sum[i][m-delta[i]]+mod)%mod;delta[i]+=w;if(w<0)if(m-delta[i]>=0)ans[i]=(ans[i]+sum[i][m-delta[i]])%mod;} }int main() {scanf("%d%d",&n,&m);B=sqrt(n);bel[0]=1;for(int i=1;i<=n;i++)scanf("%d",&a[i]),bel[i]=i/B+1;f[0]=sum[1][0]=ans[1]=1;for(int i=1;i<=n;i++){lst[i]=pos[a[i]];add(lst[lst[i]],lst[i]-1,-1);add(lst[i],i-1,1);int j=i-1;for(int j=i-1;j>=0&&bel[i]==bel[j];j--)if(cnt[j]+delta[bel[i]]<=m)f[i]=(f[i]+f[j])%mod;for(int j=bel[i]-1;j;j--)f[i]=(f[i]+ans[j])%mod;sum[bel[i]][0]=(sum[bel[i]][0]+f[i])%mod;if(delta[bel[i]]<=m)ans[bel[i]]=(ans[bel[i]]+f[i])%mod;pos[a[i]]=i;}printf("%d",f[n]); }

  

转载于:https://www.cnblogs.com/hfctf0210/p/10475116.html

总结

以上是如意编程网为你收集整理的CF1129D Isolation(分块+DP)的全部内容,希望文章能够帮你解决所遇到的问题。

如果觉得如意编程网网站内容还不错,欢迎将如意编程网推荐给好友。