题目思路:
1.暴力做法
(1)题目要求求解:
长度为 N 的数列,A1,A2,…AN ,如果其中一段连续的子序列 Ai,Ai+1,…Aj
之和是 K 的倍数,我们就称这个区间 [i,j] 是 K 倍区间。
(2)做法:录入a[N]数组,随后初始化前缀和s[N]数组,双指针遍历s[],查找
在 [i, j] 区间有几个数的和是 K 的倍数,进行统计后输出
(3)测试结果:通过6/12测试用例
(4)时间复杂度:O(N*N)
2.算法优化
(1)通过观察可以发现,我们要找的是:
当 R固定 的时候,在 L~R 找出有几个 L 满足 (S(R)-S(L-1)) % K == 0
将这句话稍作修改可以发现:
当 R固定 的时候,在 0~R-1 找出有几个 L 满足 (S(R)-S(L)) % K == 0
即:S(R) % K == S(L) % K ——数学理论同余定理
(2)再经过模拟可以发现:
A1 ~ A5: 1 2 3 4 5
S[N]: 1 3 6 10 15
S[N] % 2的cnt[1~5]: 1 1 0 0 1
那么观察前缀和对2取模的数组:如果cnt[i]和cnt[j]相等,那么A(i + 1)~A(j)就是一个2倍区间
比如:cnt[1] == cnt[2],那么A2~A2就是一个K倍区间;
cnt[1] == cnt[5],那么A2~A5就是一个K倍区间。
(3)程序优化:
cnt[0] = 1; //s[0] = 0,我们并没有计算 0%k==0 这一项,所以需要给他统计一次
LL cnt[N]; //统计当前的s[i]%k的 余数是i的个数
LL res; //存放结果
for(int i = 1; i <= n; i)
{
res += cnt[s[i] % k];
cnt[s[i] % k] ; //由于上面计算了一次,就给他统计多一次
}
我们每次拿到一个cnts[i] % k,将他赋值给res之后都需要对其加1,
因为本次的余数已经统计。
每当我们在后面的循环的时候再次拿到这个cnt[1]的时候,此时就满足了cnt[i] == cnt[j]
res统计下这个K倍区间
(4)测试结果:AC
(5)时间复杂度:O(N)
前缀和优化(6/12测试用例)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, k;
int a[N], s[N];
int main()
{
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
//初始化前缀和数组s[]
for(int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
int cnt = 0;
for(int i = 1; i <= n; i++)
for(int j = i; j <= n; j++)
{
int res = s[j] - s[i - 1];
if(res % k == 0) cnt ++;
}
printf("%d", cnt);
return 0;
}
优化版(AC)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, k;
int a[N];
LL s[N];
LL cnt[N]; //统计当前的s[i]%k的 余数是i的个数
LL res; //存放结果
int main()
{
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
s[i] = s[i - 1] + a[i]; //初始化前缀和数组s[]
}
cnt[0] = 1; //s[0] = 0,我们并没有计算 0%k==0 这一项,所以需要给他统计一次
for(int i = 1; i <= n; i++)
{
res += cnt[s[i] % k];
cnt[s[i] % k] ++; //由于上面计算了一次,就给他统计多一次
}
printf("%lld", res);
return 0;
}