题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6794
题意：找到最多的不相交的子段使得子段和为p的倍数
解题思路：
按照序列顺序依次遍历加上各个点cur=(cur+a[i])%mod，如果cur的值在之前j点处出现过，那么说明j到i点之间的数为p的倍数
两种处理方式，第一种是贪心，从前往后，遇到能够拼凑出p的倍数的情况直接拼凑，因为如果就算不在当前情况i拼凑，在后面的j进行拼凑，结果仍然是ans++,而且还会影响后面的拼凑。使用map来记录，使用map.count()函数来寻找cur点是否出现过，如果出现过，那么ans++,map.clear(),cur=0,mp[0]=1来初始化map，因为一旦当前的点可以取到那么之间的所有点都不能再被取了
第二种是使用dp，last[i]数组记录最后i出现的位置
dp[i]=max(dp[i-1],dp[last[cur]]+1);
#include<iostream>
#include<cstdio>
#include<string.h>
#include<map>
using namespace std;
#define maxn 100100
int t;
int n,p;
int a[maxn];
int ans;
map<int,int > mp;
int main(){cin>>t;while(t--){ans=0;mp.clear();scanf("%d%d",&n,&p);int cur=0;mp[0]=1;for(int i=1;i<=n;i++){int tmp;scanf("%d",&tmp);cur+=tmp;cur%=p;if(mp.count(cur)){ans++;cur=0;mp.clear();mp[0]=1;}elsemp[cur]=1;}cout<<ans<<endl;}return 0;
}
#include<iostream>
#include<cstdio>
#include<string.h>
#include<map>
using namespace std;
#define maxn 100100
int t;
int n,p;
int a[maxn];
int last[maxn]; //记录i最后一次出现的位置
int dp[maxn];
int ans;
int main(){cin>>t;while(t--){cin>>n>>p;for(int i=1;i<=n;i++){scanf("%d",&a[i]);a[i]%=p;}memset(last,-1,sizeof(last));memset(dp,0,sizeof(dp));int cur=0;last[0]=0;for(int i=1;i<=n;i++){cur=(cur+a[i])%p;if(last[cur]!=-1)dp[i]=max(dp[i-1],dp[last[cur]]+1);elsedp[i]=dp[i-1];last[cur]=i;}cout<<dp[n]<<endl;}return 0;
}