杭电多校第三场 1004 Tokitsukaze and Multiple 题解

题目大意

给你一串数字，你可以让任意两个相邻的数字合在一起，使串的个数减一，求串中最多有多少个数是p的倍数。

解题思路

这个应该是这一场的签到了吧。

但是我没想出来。

好丢人啊。

刚开始以为是dp，想了半天，不知道咋进行状态转移。

就放弃了。

其实之后仔细想想，当时以为是没有重叠的子问题，以为就不是dp了。

（后面题解也提供了dp的做法。。尴尬

其实这个题目想到了就很简单。

可以用set或者map来维护前缀和。

在求前缀和的同时不断的对p取余。

如果这个前缀和在之前没出现过就记录一下。

出现了，则说明必然中间加了一个p的倍数，所以ans++。

之后清空set或者map。

注意，0是必须要在里面的，因为0就是刚好是p的倍数。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int N = 1e5 + 5;
int a[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int t;
	cin >> t;
	while (t--) {
		int n, p;
		cin >> n >> p;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
		}
		int t = 0,ans = 0;
		set<int> s;
		s.clear(), s.insert(0);
		for (int i = 1; i <= n; i++) {
			t += a[i] % p, t %= p;
			if (s.count(t)) {
				ans++;
				t = 0;
				s.clear();
			}
			s.insert(t);
		}
		cout << ans << endl;
	}
	return 0;
}