题目描述

“蓝桥杯”练习系统 (lanqiao.cn)

题目分析

对于此题首先想到的是暴力分析，使用前缀和，这样方便算出每一区间的大小，枚举长度和其实位置，循环计算出所有区间的和进行判断，输出答案。

非满分暴力写法：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;
ll a[N], s[N], n, k, ans;
int main()
{cin >> n >> k;for(int i = 1; i <= n; i ++){cin >> a[i];s[i] = s[i - 1] + a[i];}for(int i = 1; i <= n; i ++)//长度 {for(int j = 1; j <= n; j ++)//起始位置 {int r = j + i - 1;if(r <= n){int q = s[r] - s[j - 1];if(q % k == 0)ans ++;} } }cout << ans;return 0;
}

以上两重循环超时，我们把其改为一重循环

由s[r] - s[l - r] % k == 0 推出 s[r] % k == s[l - 1] % k

故我们需要固定循环右端点，确定下与此点对应相同的之前点的个数，有多少个一样的点就说明出现了多少个k倍区间，将个数加入答案即可

此点对应的值 + 1,故为cnt[s[i] % k] ++

满分代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;
ll a[N], s[N], cnt[N], n, k, ans;
int main()
{cin >> n >> k;for(int i = 1; i <= n; i ++){cin >> a[i];s[i] = s[i - 1] + a[i];}cnt[0] = 1;//注：s[0] % k == 0,故循环之前为0的数已经有一个 for(int i = 1; i <= n; i ++){ans += cnt[s[i] % k];cnt[s[i] % k] ++;}cout << ans;return 0;
}