zjh

用户名：speaksoftly

访问量：24718

签　名：

搞spring去了...不能愉快的刷题了...

等　　级
排　　名	172
经　　验	6955
参赛次数	10
文章发表	37
年　　龄	0
在职情况	学生
学　　校	海南
专　　业

　　自我简介：

TA的其他文章

逆序数（C++代码）正解：线段树(nlogn)单点查询区间更新
浏览：363

信息学奥赛一本通T1242-网线主管（C++代码）二分
浏览：1468

你可能喜欢

C语言程序设计教程（第三版）课后习题6.11 （C++代码）

蓝桥杯2017年第八届真题-k倍区间（C++代码）前缀和O(n)算法

　　作者: zjh　　　　发表时间：2019-08-24 20:57:47 浏览：863　|　评论：0　

原题链接：蓝桥杯2017年第八届真题-k倍区间

```
求区间和，可以通过前缀和来得到各个区间的和。A[i]表示第 1 个元素到第 i 个元素的和。那么 A[r] - A[l - 1] 就是区间 [l, r] 的和。区间 [l, r] 的和如果是 k 的倍数，那么(A[r] - A[l - 1]) % k == 0 即 A[r] % k == A[l - 1] % k
    那么可以求出每个前缀和，在求的过程中取模，两个相等的前缀和就能组成一个k倍区间。我们可以在计算完前缀和以后，使用两层for循环枚举所有区间和。但是n <= 1e5，时间复杂度为O(n^2)，肯定会TLE。
    这时候我们就需要一些比较巧妙的方式来减小时间复杂度，这里提供一种思路，在求前缀和的过程中，A数组只保存 1 - i 区间和 % k 的值，然后用一个 vis 数组来做一个计数，表示A[i] % k 的余数的个数，如果vis[A[i]] >= 2，则说明有至少一对区间是k的倍数
    比如vis[A[i]] = 4，则有6对区间和是 k 的倍数
    a->b
    a->c
    a->d
    b->c
    b->d
    c->d
    特殊情况：A[i] % k 余数为0的时候，不论它是否 >= 2，它本身都是可以单独组成k倍区间的
    知道这些之后，我们只需要求前缀和A[i] % k，并且vis[A[i]]++做计数就行了，最后枚举vis中 0～k - 1 的个数，再加上vis[0]的个数
    时间复杂度O(n)
ps：vis的计算关系实际上是1～vis[i] - 1 的累加
#include "cstdio"
#include "cstdlib"
#include "iostream"
#include "cstring"
#include "cmath"
#include "algorithm"
#include "queue"
#include "map"
#include "vector"
#include "stack"
#include "set"
#include "climits"
using namespace std;
typedef long long ll;
typedef unsigned long long LL;
const int inf = 0x3f3f3f3f;
const int maxn = 100010;
//快读
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
int A[maxn], vis[maxn];
int n, k;
int main() {
    n = read(); k = read();
    ll res = 0;
    for(int i = 1; i <= n; ++i) {
        int x = read();        //快读
        A[i] = (x + A[i - 1]) % k;    //求1～i的前缀和%k的余数
        vis[A[i]]++;    //计数
    }
    for(int i = 0; i < k; ++i)    //枚举k的所有余数，当vis[i] >= 2时进行累1 ～ vis[i] - 1的累加
        for(int j = 1; j < vis[i] && vis[i] >= 2; ++j) res += j;
    printf("%lld\n", res + vis[0]);    //最后要加上余数为0的个数，前面说了，余数为0则说明有区间 1～i 本身就是k的倍数
    return 0;
}
更优code：
    因为是求每个余数的 1 ～ vis[i] - 1 累加，所以可以在输入时直接计算，详情请看代码
int main() {
    n = read(); k = read();
    ll res = 0;
    for(int i = 1; i <= n; ++i) {
        int x = read();
        A[i] = (x + A[i - 1]) % k;
        res += vis[A[i]];    //因为vis[A[i]]在下面的会++，所以这时候把它之前的结果加上就相当于是做了一次累加，省去了不必要的两个for
        vis[A[i]]++;
    }
    printf("%lld\n", res + vis[0]);
    return 0;
}
```

0.0分

4 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

zjh

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C++代码）

点我有惊喜！你懂得！

母牛的故事（C语言代码）

点我有惊喜！你懂得！

蓝桥杯2017年第八届真题-k倍区间（C++代码）前缀和O(n)算法

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

C语言训练-大、小写问题（C语言代码）

回文数(一) （C语言代码）

上车人数（C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

【简单计算】（C语言代码）

【金明的预算方案】（C++代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

zjh

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C++代码）

点我有惊喜！你懂得！

母牛的故事 （C语言代码）

点我有惊喜！你懂得！

蓝桥杯2017年第八届真题-k倍区间 （C++代码）前缀和O(n)算法

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

C语言训练-大、小写问题 （C语言代码）

回文数(一) （C语言代码）

上车人数 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

【简单计算】 （C语言代码）

【金明的预算方案】 （C++代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

母牛的故事（C语言代码）

蓝桥杯2017年第八届真题-k倍区间（C++代码）前缀和O(n)算法

　　评论区

C语言训练-大、小写问题（C语言代码）

上车人数（C语言代码）

【简单计算】（C语言代码）

【金明的预算方案】（C++代码）