AcWing 1230. K倍区间
原题链接
中等
作者:
MyPower
,
2023-03-29 22:00:15
,
所有人可见
,
阅读 116
算法1:两重循环,找到(s[j] - s[i - 1]) % k == 0 统计次数
蓝桥杯只能过两个数据,很惨
想也想不出来,看题解
算法2:
根据s[j] - s[i - 1]) % k == 0 => s[j] - s[i - 1] = k * m => s[j] % k = s[i - 1] % k
通过等价变换(怎么想到的 可能和做题经验有关吧 我没想到 hh)
现在变成了
1)单个区间 [1, r] % k == 0;这种情况个数就是cnt[0]
2)[l, r] 两个前缀和余数相等 构成的k倍区间
1) res += cnt[ s[i] % k ];//记录k倍区间的总数
2)cnt[ s[i] % k] ++; //表示在当前位置前缀和取余后值相等的次数
为什么1要在2之前
I 当cnt[i] = 0 (i > 0) 时, 这时只有一个余数,不能构成一个k倍区间
II 便于更新下个答案
//代码
#include <iostream>
using namespace std;
const int N = 100010;
typedef long long LL;
int a[N], s[N], cnt[N];
int main()
{
// 请在此输入您的代码
int n, k;
scanf("%d %d", &n, &k);
LL res = 0;
for(int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
s[i] = s[i - 1] + a[i];
s[i] %= k;
res += cnt[s[i]];
cnt[s[i]]++;
}
printf("%lld", res + cnt[0]);
return 0;
}
(14 - 8)% 3 = 0
14 % 3 = 2 8 % 3 = 2 那么(14 - 8)% 3 = 0
chatgpt:
这个算法的核心思想是利用前缀和的性质,即一个区间的和可以通过两个前缀和的差来计算。我们假设前i个元素的前缀和为sum[i],那么第j个到第i个元素的区间和为sum[i]-sum[j-1]。我们可以将sum[i]-sum[j-1]除以K得到一个余数r,如果存在一个位置k使得sum[k-1]除以K的余数也为r,那么从k到i的子数组的和就可以被K整除。
为了快速查找是否存在这样的位置k,我们可以使用哈希表来记录每个余数出现的最后一个位置。具体来说,我们可以遍历一遍数组,对于每个位置i,我们计算sum[i]除以K的余数r,然后在哈希表中查找是否存在一个位置k,使得sum[k-1]除以K的余数也为r。如果存在这样的位置k,那么我们就找到了一个K倍区间。否则,我们就将当前位置i的余数r插入到哈希表中。
这个算法的时间复杂度是O(n),因为我们只需要遍历一遍数组,并且哈希表的查找和插入操作的时间复杂度都是O(1)的。因此,这个算法可以快速地解决K倍区间问题。