本文最后更新于：35 分钟前
[蓝桥杯 2017 省 B] k 倍区间
题目描述
给定一个长度为 N 的数列，A1,A2,A3,…AN，如果其中一段连续的子序列Ai,Ai+1,…Aj(i≤j) 之和是 K 的倍数，我们就称这个区间 [i,j] 是 K 倍区间。
你能求出数列中总共有多少个 K 倍区间吗？
输入格式
第一行包含两个整数 N 和 K(1≤N,K≤105)。
以下 N 行每行包含一个整数Ai*(1≤Ai*≤105)。
输出格式
输出一个整数，代表 K 倍区间的数目。
样例 #1
样例输入 #1
样例输出 #1
理解
记录一下前缀和，再用一个cnt来记录每个前缀和的余数的个数，两个余数相等的相减为0，0本来就满足，所以初始化时，cnt[0]=1;
代码
两重循环
过了40分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include <iostream>
#include<cstdio>
#include <sstream>
#include<algorithm>
#include<cmath>
#include<string>
using namespace std;
int n,k;
const int N=1e5+1e4;
int arr[N];
long long sum[N];
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
scanf("%d",&arr[i]);
sum[i]=sum[i-1]+arr[i];
}
long long res=0;
for(int i=0;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if((sum[j]-sum[i])%k==0)res++;
}
}
cout<<res<<endl;
return 0;
}
|
满分 这里用余数的概念，任意两个余数相减等于0；
只用一层for循环即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include <iostream>
#include<cstdio>
#include <sstream>
#include<algorithm>
#include<cmath>
#include<string>
using namespace std;
int n,k;
const int N=1e5+1e4;
int arr[N];
long long sum[N];
int cnt[N];
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
scanf("%d",&arr[i]);
sum[i]=sum[i-1]+arr[i];
}
long long res=0;
cnt[0]=1;
for(int i=1;i<=n;i++)
{
res+=cnt[sum[i]%k];
cnt[sum[i]%k]++;
}
cout<<res<<endl;
return 0;
}
|