题目描述
输入描述
输出描述
输出一个整数。
样例输入
6 3
1 1 4 5 1 4
样例输出
2
思路分析
先看一个样例
k = 6
1 4 1 2 3 5 1 4 3 1
前三个数1 4 1满足条件,那么这就算一个方案了,后续的2没有必要再放进这个方案了
如果将这个2放到后面可能还会有所贡献,满足条件方案直接删除
数组变为 2 3 5 1 4 3 1
后面的 5 1 也是一种方案,但我们发现上一种方案1 4 1是前缀和,5 1不是前缀和,怎么找到呢?
我们发现 3位置上前缀和模k余数为5,第一个1位置上前缀和模k余数也是5,这就代表它们中间这部分的和刚好可以被k整除
因此,我们只需要找到余数为0或者余数之前出现过的方案即可
注意:
本题不可以直接用前缀和预处理,因为我们找到一个方案后前面数会删除
前缀和这时需要及时更新,因此我们边做边求
代码实现
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
const int N = 2e5 + 10;
int main()
{
cin.tie(0);
ios::sync_with_stdio(0);
int n, k;
cin >> n >> k;
// res记录答案,sum记录当前数组前缀和
int res = 0, sum = 0;
set<int> s = {0}; //先把0加入,便于出现余数为0时答案加1
for(int i = 0; i < n; i ++)
{
int a;
cin >> a;
sum = (sum + a) % k;
if(s.count(sum))
{
res ++;
s.clear();
sum = 0; // 和初始化加入0原理相同
}
s.insert(sum);
}
cout << res << endl;
return 0;
}
类似题目
第八届蓝桥杯c++ B组 K倍区间