HDU6794 Tokitsukaze and Multiple（贪心+前缀和）
Description
Tokitsukaze has a sequence of length n, denoted by a.
Tokitsukaze can merge two consecutive elements of a as many times as she wants. After each operation, a new element that equals to the sum of the two old elements will replace them, and thus the length of a will be reduced by 1.
Tokitsukaze wants to know the maximum possible number of elements that are multiples of p she can get after doing some operations (or doing nothing) on the sequence a.
Input
There are several test cases.
The first line contains an integer T (1≤T≤20), denoting the number of test cases. Then follow all the test cases.
For each test case, the first line contains two integers n and p (1≤n,p≤105), denoting the length of the sequence and the special number, respectively.
The second line contains n integers, where the i-th integer ai (1≤ai≤105) is the i-th element of a.
It is guaranteed that the sum of n in all test cases is no larger than 106.
Output
For each test case, output in one line the maximum possible number of elements that are multiples of p after doing some operations.
Sample Input
2
5 3
2 1 3 2 1
3 1
123 456 789
Sample Output
3
3
题意
给一串有n个数的数组和一个数p，将该数组分割，最多可以分割为多少段，每一段的和都是p的倍数。
计算前缀和模p，如果当前的前缀和模p的值，与前面某位置的前缀和模p的值相等，说明这一段的和是p的倍数（第一次知道，尴尬了），用map来标记出现过的前缀和模p的值。因为要将其尽可能多分割，所以找到相等的模的时候就要将mp数组清空并且++ans。若某一段的前缀和模p恰巧等于0，那说明这一段数的和能直接被p整除，所以我们要事先将mp[0]=true。
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
#include<functional>
#include<map>
#include<set>
#include<unordered_map>
#define lowbit(x) ((x)&-(x))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll N=1e6+10,NN=2e3+10,INF=0x3f3f3f3f,LEN=20;
const ll MOD=1e9+7;
const ull seed=31;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
}
int sum[N];
void init(){}
int main(){int t;t=read();while(t--){map<int,bool>mp;int n,p,ans=0;n=read();p=read();sum[0]=0;mp[0]=true;for(int i=1;i<=n;i++){int x,temp;x=read();sum[i]=(sum[i-1]+x)%p;if(mp[sum[i]]){//如果匹配到了，++ans，清空mp（贪心）++ans;mp.clear();}mp[sum[i]]=true;//将这一段的模在mp中标记为true}printf("%d\n",ans);}
}