本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
说我们IIS7站长博客，有一篇博文用了他们的图片。
要求我们给他们一张图片6000元。要不然法院告我们
为避免不必要的麻烦，IIS7站长博客，全站内容图片下架、并积极应诉
博文内容全部不再显示，请需要相关资讯的站长朋友到必应搜索。谢谢！
另祝：版权碰瓷诈骗团伙，早日弃暗投明。
相关新闻：借版权之名、行诈骗之实，周某因犯诈骗罪被判处有期徒刑十一年六个月
叹！百花齐放的时代,渐行渐远!
http://acm.hdu.edu.cn/showproblem.php?pid=6794
给定一个序列，每次可以将序列相邻的两个元素相加生成一个新元素替代这两个元素，求最终序列里为 $p$ 的倍数的元素最多可能为多少。
签到题，处理前缀和然后对所有前缀和 $sum$ 模 $p$ ，于是原题的合并 $[l,r]$ 使得元素可以被 $p$ 整除就变成了查看 $sum[l-1]$ 是否等于 $sum[r]$ 。
接着考虑dp，设 $f[i]$ 表示序列$1 \sim i$ 的答案为多少，显然如果要合并第 $i$ 个元素的话那么直到合出符合条件的元素才停（不然没必要合），那么就有 $f[i]=max(f[i-1],f[pre[i]]+1)$， 其中 $pre[i]$表示与第$i$个前缀和相等的前一个的前缀和的位置，当然如果没有 $pre[i]$ 的话 $f[i]=f[i-1]$ 即可。
时间复杂度 $O(Tn)$ 。
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int N=1e5+5;
inline int read(){
int X=0,w=0;char ch=0;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
return w?-X:X;
}
int n,p,a[N];
int pre[N],f[N],lst[N];
void init(){
for(int i=0;i<p;i++)lst[i]=-1;
}
int main(){
int T=read();
while(T--){
n=read(),p=read();
init();
for(int i=1;i<=n;i++)a[i]=(a[i-1]+read())%p;
for(int i=0;i<=n;i++){
pre[i]=lst[a[i]];
lst[a[i]]=i;
}
for(int i=1;i<=n;i++){
if(pre[i]!=-1)
f[i]=max(f[i-1],f[pre[i]]+1);
else f[i]=f[i-1];
}
printf("%d\n",f[n]);
}
return 0;
}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++
