蓝桥杯练习题八 - k倍区间（c++）

r囧r小猫 2024-05-31 04:03 83阅读 0赞

> 题目如下

**问题描述**

给定一个长度为N的数列，A1, A2, … AN，如果其中一段连续的子序列Ai, Ai+1, … Aj(i <= j)之和是K的倍数，我们就称这个区间\[i, j\]是K倍区间。

你能求出数列中总共有多少个K倍区间吗？

**输入格式**

第一行包含两个整数N和K。(1 <= N, K <= 100000)

以下N行每行包含一个整数Ai。(1 <= Ai <= 100000)

**输出格式**

输出一个整数，代表K倍区间的数目。

**样例输入**

5 2
    1
    2
    3
    4
    5

**样例输出**

以下程序实现了该功能，请你补全空白处代码：

#include <bits/stdc++.h>
    using namespace std;
    
    int main()
    {
        long long n, k, ans = 0, son[100000], sum[100000], b[100000] = {0};
        cin >> n >> k;
        for (int i = 0; i < n; i++)
        {
            cin >> son[i];
            if (i != 0)
                __________________;
            else
                sum[i] = son[i] % k;
            b[sum[i]]++;
            ans += b[sum[i]] - 1;
            if (sum[i] == 0)
                ans++;
        }
        cout << ans;
        return 0;
    }

> 预防针

兄弟们，不得不说，这道题是真难啊，看了一共5个小时左右，才把上面这种代码的思路看懂，外加另一种简单但却耗时的思路，网上也查了很多种解析，实在不敢恭维，很多人可能自己都没搞明白思路。除此之外，还有另一种解法，其实和本题给出的部分代码思路是一样的，不再单独列出，所以这里给出两种方法来解题。

> 代码解析一：以时间换空间（比较耗时的解法）

代码如下：

#include <iostream>
     
    using namespace std;
     
    int main(int argc, char *argv[])
    {
        int numMax,kVal,cnt,sumBuff;
        int numArray[100] = {0};
        
        cnt = 0;
        
        cin >> numMax >> kVal;
        for(int i = 0;i < numMax;i++) 
            cin >> numArray[i]; 
        
        for(int i = 0;i < numMax - 1;i++)
        {
            
            sumBuff = 0;
            for(int j = i;j < numMax;j++)
            {
                sumBuff += numArray[j];
                if(sumBuff % kVal == 0) cnt++;
            }
        }
        
        cout << cnt << endl;
        
        return 0;
    }

**1.将数字提前存入数组**

for(int i = 0;i < numMax;i++) 
            cin >> numArray[i];

**2.循环累加**

for(int i = 0;i < numMax - 1;i++)
        {
            
            sumBuff = 0;
            for(int j = i;j < numMax;j++)
            {
                sumBuff += numArray[j];
                if(sumBuff % kVal == 0) cnt++;
            }
        }

**i=0时，j所在的for循环：**

**j=0**

第0次循环，sumBuff=numArray\[0\]，整除取余为0，cnt++；

第1次循环，sumBuff=numArray\[0\]+numArray\[1\],整除取余为0，cnt++；

.......

第numMax-1次循环，sumBuff=numArray\[0\]+......+numArray\[numMax-1\],整除取余后为0，cnt++。

**i=1时，j所在的for循环：**

**j=1**

第1次循环，sumBuff=numArray\[1\]，整除取余为0，cnt++；

.......

第numMax-1次循环，sumBuff=numArray\[1\]+......+numArray\[numMax-1\],整除取余后为0，cnt++。

**......**

**i=numMax-2**

**j=numMax-2**

第numMax-2次循环，sumBuff=numArray\[numMax-2\]，整除取余为0，cnt++；

第numMax-1次循环，sumBuff=numArray\[numMax-2\]+numArray\[numMax-1\],整除取余后为0，cnt++。

--------------------

这种方式完全把numArray中任意块计算进去，不存在任何的遗漏，也是比较传统思维的一种解决方式，但是由于一个个的进行尝试，导致时间上会存在比较大的消耗，在实际应用中，可能会存在数量巨大的情况，所以这种方式并不被推崇。

> 代码解析二：以空间换时间（效率高）

代码如下：

#include <bits/stdc++.h>
    using namespace std;
    
    int main()
    {
        long long n, k, ans = 0, son[100000], sum[100000], b[100000] = {0};
        cin >> n >> k;
        for (int i = 0; i < n; i++)
        {
            cin >> son[i];
            if (i != 0)
                sum[i] = (sum[i - 1] + son[i]) % k;
            else
                sum[i] = son[i] % k;
            b[sum[i]]++;
            ans += b[sum[i]] - 1;
            if (sum[i] == 0)
                ans++;
        }
        cout << ans;
        return 0;
    }

刚看懂时：这个方法还真不是人能看懂的；

又看了一会：这理念自叹不如；

开始写博客后：我怕我解释完大家还是没看懂，\[手动笑哭\]。

**1.实时读取数据**

cin >> son[i];

**2.获取sum\[i\]**

if (i != 0)
                sum[i] = (sum[i - 1] + son[i]) % k;
            else
                sum[i] = son[i] % k;

sum\[i\]我们都能理解，就是累加和嘛，可这里偏偏要%k是什么鬼意思？这里要当心了，一步看不懂，后面的全都看不懂了，我们把sum当做一个存储累加和余数的数组，我再强调一遍，“累加和余数”！！！！

所以:

当i == 0时，sum\[i\] = son\[i\] % k，即sum\[0\] = son\[0\] % k;

当i == 1时，sum\[i\] = (sum\[i - 1\] + son\[i\])% k，即sum\[1\] = (sum\[0\] + son\[1\]) % k;

记住我说的，sum是余数和，后面你就忘掉那个“和”字，只记住“余数”，然后来展开下上面的公式：

sum[1] = (sum[0] + son[1]) % k;
    sum[1] = sum[0] % k + son[1] % k;
    sum[1] = sum[0] + son[1] % k; 
    //sum[0]已经是余数了，所以%k没有意义，是本身

第一种解法，sumArray存储的是每一项从0开始的当前项的累加和；

这里sum存储的就是sumArray存储的是每一项从0开始的当前项余数的累加和；

**3.先说sum\[i\] == 0的情况**

if (sum[i] == 0)
                ans++;

这个很明显，只要整数取余为0，那必然是符合k区间条件的，这里ans++应该不难理解，因为sum中存储的全是余数，必然不会全是0，有人会有疑惑，假如有多个不为0的余数存在，那么sum\[i\] == 0这个条件还能成立吗?答案是肯定的，这就是为什么余数也要进行相加的原因：

sum[i] = (sum[i - 1] + son[i]) % k;

余数（被忽略的部分必然被整除了）+余数（被忽略的部分必然被整除了）能被整除就是0，不能被整除就是另一个余数，也有可能和当前余数相等，相等怎么办？看下面：

**4.区间计算的重头戏**

b[sum[i]]++;
    ans += b[sum[i]] - 1;

能不能看得懂就全看这里了！！！

b是什么？

b是用来存储相等的余数出现的次数的！！！

如果余数相等，则对应的i，j相减就把余数减去了，剩下的必定可以整除，这就是一个新的区间！！！

我们从0开始模拟下b：

假设余数为3:

余数3出现1次时：

b\[3\]++ = 1，说明余数为3的累加和出现1次，这时候没有成对出现，无法用j-i判断是否存在k倍区间；

余数3出现2次时：

b\[3\]++ = 2，说明余数为3的累加和出现2次，这时候存在1个k倍区间，为什么是1个呢？假设这2个累加和下表分别是i，j，那么有，j-i这个一个区间；

余数3出现3次时：

b\[3\]++ = 3，说明余数为3的累加和出现3次，这时候存在2个k倍区间，为什么是2个呢？假设这3个累加和下表分别是i，j，k，那么有，k-i，k-j，有人说，不是还有个j-i吗？没错，但是j-i已经在余数出现第2次的时候存在了，不能计算在内；

余数3出现4次时：

b\[3\]++ = 4，说明余数为3的累加和出现4次，这时候存在3个k倍区间，为什么是3个呢？假设这4个累加和下表分别是i，j，k，l那么有，l-i，l-j，l-k有人说，不是还有个j-i和k-i，k-j吗？没错！你抬头看看余数出现第2，3次的里面有没有没列出来的这三个？所以不能计算在内；

所以，你发现规律了吗？像不像选择排序法里面那样？用最后一个和前面的所有项比较，这还真是选择排序法里德运用。

**ans += b\[sum\[i\]\] - 1;**

这时候，你已经明白了**b\[sum\[i\]\]** 的含义，你可能还需要再消化下......

已经看懂的同学我们继续下一个问题，为什么要减1？

一个余数的时候，区间不成立；

两个相等余数的时候，两两比较，只能有1个；

三个相等余数的时候，最后一位和前两个比较，只有2个，

......

n个相等余数的时候，最后一位和前n-1个比较，只有n-1个.

因为始终有一个要作为参照系，所以只能存在n-1个，上面的举例已经清楚说明了原因。

--------------------

> 总结

到这里，今天的学习就要结束了，说实话，这个题真TM难，就这，还被列入了简单之类，?但是你要是听懂了，你会发现其实也不难，就是一个理念问题，可问题是，这样的理念不是一般人想的出来的。

另外，博主在查找的时候看到有些人的解析里面用到了c(m,n)，这是什么呢？

从n个不同的元素中，任取m（m≤n）个元素为一组，叫作从n个不同元素中取出m个元素的一个组合。所以它叫排列组合，记得大学里面高数里讲概率的时候有讲过，相信很多人都忘了。根据这种理论，会有一种新的写法，但思路和第二种是一样的，我们是直接通过从n个余数中找出有几种组合的方式，c(m,n)是根据数学的思维通过公式计算sumArray中存在余数的组合方式：

1 2 3 4 5

son\[\]

1 2 3 4 5

1 0 1 0 1 每一项整除取余

这里是2个

sum\[\]

1 3 6 10 15

1 1 0 0 1 累加和整除取余

这里1是c(3,2)=3;

这里0是c(2,2)=1;

2 + 3 + 1 = 6

感兴趣的可以去了解下这种方式，不再赘述，有问题欢迎评论区留言讨论。