专栏文章

题解：B4105 [CSP-X2024 山东] 消灭怪兽

UUNDERTALE_RS
B4105题解参与者 4已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@miqmw2hx
此快照首次捕获于
2025/12/04 07:24
3 个月前
此快照最后确认于
2025/12/04 07:24
3 个月前
查看原文

B4105 [CSP-X2024 山东] 消灭怪兽 题解

题目传送门

前置知识

如果两个正整数 aa，bb 除以同一个正整数 kk 的余数相等，则这两个数同余。记作：
a≡b(modk)a \equiv b \pmod k
同时两数之差能被 kk 整除。即：
k∣(a−b)k \mid (a - b)

题目分析

看到题目，我们思考一下，题目简化后就是问 nn 个数中有多少个区间和是 kk 的倍数。
题目中说到：
1≤n≤1061 \le n \le 10^6
所以即使是前缀和也需要用优化的方法。

前缀和

提到区间和离不开的就是前缀和。那么我们就对输入的数进行前缀和的处理。

计算个数

我们知道区间和的计算方法，就是在前缀和数组中的右端点位置的数减去左端点位置的前一个数。
根据前置知识，要求以 nn 个数中的某个数为结尾的区间和为 kk 的倍数的区间个数，
就是在前缀和数组里找其之前与它的前缀和关于 kk 同余的数的个数。
这样我们就可以用一个计数数组来存储每一个前缀和模 kk 的情况。
代码如下：
CPP
long long a[1000005],qzh[1000005],cnt[1000005];
for(int i = 1;i <= n;i++){
	cin >> a[i];
	qzh[i] = qzh[i-1] + a[i]; //前缀和数组
	ans += cnt[qzh[i] % k]; //以现在为结尾的区间个数
	cnt[qzh[i] % k]++; //将模k的情况记录，不可调换顺序！
}

答案输出

输出答案前我们仔细想就会发现，最终的 ansans 没有记录到单个数的情况，所以最后输出还要补上。
最终代码如下：
CPP
#include <iostream>
using namespace std;
long long n,a[1000005],qzh[1000005],cnt[1000005],ans,k;

int main(){
	cin >> n >> k;
	for(int i = 1;i <= n;i++){
		cin >> a[i];
		qzh[i] = qzh[i-1] + a[i];
		ans += cnt[qzh[i] % k];
		cnt[qzh[i] % k]++;
	}
	cout << ans+cnt[0]; //cnt[0]为单个数的情况
	return 0;
}

总结

是一道基础的题，考察数学能力，需要对余数有相关认识，适合初学者练习。
感谢您的阅读！

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...