[HDU多校2020]第三场 1004 Tokitsukaze and Multiple (贪心/dp)

Tokitsukaze and Multiple

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6794

Problem 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 ≤ $10^5$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$1 ≤ $a_i$ai​ ≤ $10^5$105) is the i-th element of a.

It is guaranteed that the sum of n in all test cases is no larger than $10^6$106
.
Output
For each test case, output in one line the maximum possible number of elements that are multiples of $p$p after doing some operations.

Sample Input

2
5 3
2 1 3 2 1
3 1
123 456 789

Sample Output

3
3

 

题面

思路

题解说的很清楚了，
题意就是你可以选择操作任意次，使得最后这个序列中是 $p$p 倍数的元素个数最大，输出个数。题解给的理解是把序列切分成若干段，然后看看有几段的和是 p 的倍数，更清楚地说明了问题。

这样一看就是经典的贪心。
我们可以试着先把p的倍数的区间都找出来，当成一个个线段，求不相交的线段最多可以选择几条。利用贪心的思想，按照线段的右端点选择，从左到右每次先贪心选择较左的。如果与之前的线段发生了冲突，则必定不选，因为如果选了，至少使得前面的这条线段会删去，而后续可选的线段也有变少的可能性。

贪心+数组解法

对于要求 $p$p 的倍数这样的问题，要是中间一段可以合并成 $p$p 的倍数，那合并完以后肯定不用再管了，即再在后面选就好了。所以我们可以直接维护从左到右的前缀和模 $p$p 的余数来判断即可。

前缀和加上新来的数字，如果加上后这个余数在前面出现过则证明从上次出现改余数的地方的后一位数字到以该数字为结尾的这一段数字相加的和是 $p$p 的倍数，此时答案的个数+1，然后重置和，再重复这个过程即可。

对于如何判断是否存在过一样的余数，如果我们使用数组来进行的话，对于标记余数的数组，如果每次重置标记数组都memset循环置零，那么就会超时。所以我们选择使用map来加速运行，或者如果还是使用数组的话，可以优化一下，在标记数组的值上做处理，判断是否出现过用一个值来判断，然后每次需要重置，就改变这个值，相当于每组一个值来判断。
具体可以见博主wayne_lee_lwc写的https://blog.csdn.net/wayne_lee_lwc/article/details/107660851
这样子可能比用map还快一点点。
代码如下：

#include<iostream>
#include<cstdio>
#define N 100050
using namespace std;
int a[N];
int vis[N];
int p,n,T,cnt = 0,ans;
int main(){
	for(cin >> T;T;T--){
		scanf("%d%d",&n,&p);
		ans = 0;
		for(int i = 1;i <= n;i++){
			scanf("%d",&a[i]);
			a[i] %= p;
		}
		cnt++;
		int sum = 0;
		for(int i = 1;i <= n;i++){
			sum += a[i];
			sum %= p;
			if(vis[sum] == cnt || sum == 0){
				ans++;
				sum = 0;
				cnt++;
				continue;
			}
			vis[sum] = cnt;
		}
		printf("%d\n",ans);
		
	}
}

贪心+map解法

用map来把前缀和模 $p$p 存下来，一旦前面出现过和当前前缀值相同的情况，则可以合并成一个p的倍数，ans++，这时候就清空map，这之前的点都不会再选取，再继续看后面。
需要注意的就是余数为0的情况也是需要ans++。

代码如下：

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int t,n,p,x,now,ans;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&p);
		map<int,int> mp;
		mp[0]=1;  //mp[0]初始化为1，这样余数为0的情况就可以ans++
		now=0;
		ans=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&x);
			now=(now+x)%p;  //当前的前缀和的余数
			if(mp.count(now))//map.count(Key)返回值为1或者0，1返回存在，0返回不存在
			{
				ans++;
				now=0;  //重置前缀和
				mp.clear(); //清空map
				mp[0]=1;
			}
			else mp[now]=1;  //标记此时的前缀和余数now存在
		}
		printf("%d\n",ans);
	}
	return 0;
}

dp解法

我们用 $now$now 表示当前的前缀和的余数。设 $dp[i]$dp[i] 表示 $1\sim i$1∼i 区间内和为 $p$p 的倍数的不相交连续子段的最大数目，即答案。
那么可以得到关系式
$If$If    $last[now]不存在，即前面没有出现过相同的余数$last[now]不存在，即前面没有出现过相同的余数
$dp[i]=dp[i−1]$dp[i]=dp[i−1]
$else 出现过相同的余数，表示在这区间里可以得到一个，那么就比较一下$else出现过相同的余数，表示在这区间里可以得到一个，那么就比较一下
$dp[i]=max(dp[i−1],dp[last[now]]+1)$dp[i]=max(dp[i−1],dp[last[now]]+1)
其中$last[now]$last[now]代表当前前缀和上次出现的位置。

代码如下：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 7;
int dp[maxn],last[maxn];

int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        int x,n,p;
        scanf("%d%d",&n,&p);
        memset(last,-1,sizeof(last));
        int now = 0;
        dp[0] = last[0] = 0;
        for(int i = 1;i <= n;i++) {
            scanf("%d",&x);
            now = (now + x) % p;
            dp[i] = dp[i - 1];
            if(last[now] != -1) {
                dp[i] = max(dp[i],dp[last[now]] + 1);
            }
            last[now] = i;  //更新当前前缀和余数存在的最后一个位置
        }
        printf("%d\n",dp[n]);
    }
    return 0;
}