蓝桥杯每日一题2023.11.11

朱雀 2024-02-18 09:02 34阅读 0赞

### 题目描述 ###

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

![4ef899a93197493aa5c46db23ed79c0f.png][]

### 题目分析 ###

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

非满分暴力写法：

#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;
    }

[_lanqiao.cn]: http://lx.lanqiao.cn/problem.page?gpid=T2830
[4ef899a93197493aa5c46db23ed79c0f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/6df475d65f3044ae9c516f42235ba9a3.png