2020 Multi-University Training Contest 3 H / HDU 6794 - Tokitsukaze and Multipl

题目：Tokitsukaze and Multipl

知识点：1.贪心。2.map维护前缀和。3.dp

分析(map维护前缀和)：题目要求的是如果将序列a进行划分，问最多有多少段划分后序列元素和为p的倍数。我们这样考虑，我们用map来维护一段前缀和，如果当前的前缀和在这之前出现过，意味着这两段相等前缀和之间的元素和为p的倍数，这时我们让cnt++,同时把map.clear()掉。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
int main(){
	
	int t;
	scanf("%d",&t);
	while(t--){
		
		int n,p,a[maxn],cnt=0,sum=0;
		map<int,int> M;
		scanf("%d %d",&n,&p);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			a[i]=a[i]%p;
		}
		
		for(int i=1;i<=n;i++){
			
			sum=(sum+a[i])%p;
			if(M.count(sum)==1||a[i]==0||sum==0){  //如果之前出现过相等的sum,或a[i]本身就是p的倍数或sum是p的倍数 
				cnt++;        //个数加一 
				M.clear();   //将map清空 
				sum=0;       //将前缀和清零 
			}
			else M[sum]++;  //否则记录这个sum 
		}
		printf("%d\n",cnt);
		
		
	}
	
	
	
	
	return 0;
}
/* 2 5 3 2 1 3 2 1 3 1 123 456 789 */

分析(dp)：dp[i]=max(dp[i-1],dp[last[cur]]+1),dp[i]表示的是前i个数最多有dp[i]段满足条件，last数组记录的是前缀和cur最近出现的位置。dp[i]要么等于dp[i-1],要么等于dp[last[cur]]+1(last[cur]到i之间的元素和为p的倍数)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
int main(){
	
	int t;
	scanf("%d",&t);
	while(t--){
		
		int m,p,a[maxn],last[maxn],dp[maxn],cur=0;
		fill(last,last+maxn,-1);
		fill(dp,dp+maxn,0);
		last[0]=0;
		scanf("%d %d",&m,&p);
		for(int i=1;i<=m;i++)
		   scanf("%d",&a[i]);
		for(int i=1;i<=m;i++){
			cur=(cur+a[i])%p;
			if(last[cur]!=-1)   //如果之前出现过cur了
			  dp[i]=max(dp[i-1],dp[last[cur]]+1);
			else 
			  dp[i]=dp[i-1];
			last[cur]=i;   //更新last数组 
			
		}
		
		printf("%d\n",dp[m]); 
		
	}
	
	
	
	
	return 0;
}