2017蓝桥杯:k倍区间(前缀和)

比眉伴天荒 2022-07-03 12:55 172阅读 0赞

标题： k倍区间

给定一个长度为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

程序应该输出：  
6

资源约定：  
峰值内存消耗（含虚拟机） < 256M  
CPU消耗 < 2000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

注意：  
main函数需要返回0;  
只使用ANSI C/ANSI C++ 标准;  
不要调用依赖于编译环境或操作系统的特殊函数。  
所有依赖的函数必须明确地在源文件中 \#include  
不能通过工程设置而省略常用头文件。

提交程序时，注意选择所期望的语言类型和编译器类型。

分析;  
不知道为什么是最后一题 我的时间复杂度可能太高了

#include <iostream>
    using namespace std;
    int main()
    {   
        int n,k;
        int a[100010];
        int sum; 
        cin >> n >> k;
        for(int i = 0; i < n; i++) {
            cin >> a[i];
        }   
        int count = 0;
        for(int i = 0; i < n; i++) {
            sum = 0; 
            for(int j = i; j < n; j++) {
                sum += a[j]; 
                if(sum%k == 0){
                    count++;
                }
            }   
        }   
        cout <<count;   
        return 0;
     }

改后:

转自大佬:[http://blog.csdn.net/y1196645376/article/details/69718192][http_blog.csdn.net_y1196645376_article_details_69718192]  
感谢提醒:[http://blog.csdn.net/viscu/article/details/70159338][http_blog.csdn.net_viscu_article_details_70159338]

通过前缀和的方法,把O(n方)的复杂度降低到了O(n),虽然学了挺久,看了挺久,但也算是学会了

主要思想:是使要加和的数据完全储存，并且在下一次计算中直接调用,线性递推.

分析:  
统计前缀和  
sum\[1\] = a1;  
sum\[2\] = a1+a2;  
sum\[i\] = a1+a2+…+ai;  
对于任意一段区间\[l,r\]的和就是sum\[r\]-sum\[l-1\].  
(sum\[r\]-sum\[l-1\])%k 保证了\[l,r\]这段区间要么%k等于0 要么比k小 等于0这表示了正好是k的倍数 然后通过前缀和相同的数据来判断出剩下的k的倍数:(sum\[r\]-sum\[l-1\])%k == 0.变形后就是：sum\[r\]%k==sum\[l-1\]%k .

程序分析样例:  
输入: 1 2 3 4 5  
%k后前缀和: 1 1 0 0 1

当i = 0, sum=0,bk[1]=1;
    当i = 1, sum=1,bk[1]=2; //因为当bk[1]之前为1时 可得相减=0为k的倍数
    当i = 2, sum=1,bk[0]=1;
    当i = 3, sum=2,bk[0]=2; //同上理,当0-0时还是0
    当i = 4, sum=4,bk[1]=3; //之前bk[1]有2个  所以有2种-法 所以sum加上2
    最后统计bk[0]有几个 sum+=bk[0]  //因为之前只考虑了相减的情况 没有考虑到本身
    sum = 6;

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll bk[100010] = {
       0};
    ll arr[1000010];
    int main()
    {   
        int n,k;
        scanf("%d%d",&n,&k);
        for(int i = 0; i < n; i++)
            scanf("%lld",&arr[i]);
    
        arr[0] %= k;
        ll sum = 0;
    
        for(int i = 1; i < n; i++)
            arr[i] = (arr[i]+arr[i-1])%k;
    
        for(int i = 0; i < n; i++)
            sum += (bk[ arr[i] ]++);
    
        printf("%lld",sum+bk[0]);
        return 0;
    }

[http_blog.csdn.net_y1196645376_article_details_69718192]: http://blog.csdn.net/y1196645376/article/details/69718192
[http_blog.csdn.net_viscu_article_details_70159338]: http://blog.csdn.net/viscu/article/details/70159338