每日算法打卡:K倍区间 day 10

发布时间:2024年01月10日

原题链接

1230. K倍区间

题目难度:中等

题目来源:第八届蓝桥杯省赛C++ B组,第八届蓝桥杯省赛Java B/C组

题目描述

给定一个长度为 NNN 的数列, A 1 , A 2 , … A N A_1, A_2, … A_N A1?,A2?,AN?,如果其中一段连续的子序列 A i , A i + 1 , … A j A_i, A_{i+1}, … A_j Ai?,Ai+1?,Aj? 之和是 K 的倍数,我们就称这个区间 [ i , j ] [i, j] [i,j] 是 K 倍区间。

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

输入格式

第一行包含两个整数 N 和 K。

以下 NNN 行每行包含一个整数 A i A_i Ai?

输出格式

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

数据范围

1 ≤ N , K ≤ 100000 1 \le N, K \le 100000 1N,K100000,
1 ≤ A i ≤ 100000 1 \le A_i \le 100000 1Ai?100000

输入样例:
5 2
1
2
3
4
5 
输出样例:
6 

题目分析

题目意思十分清楚,就是给一个静态数组,问其中有多少个连续子数组的和是K的倍数

这里我们观察数据范围,大概采用的时间复杂度要小于 O ( n log ? n ) O(n\log n) O(nlogn)

我们如果用最暴力的做法,枚举所有方案,对于枚举来说最重要的就是如何能够不重不漏的枚举出所有方案

对于这个题而言,就是枚举左端点和右端点,这样就可以枚举所有的方案了,然后再判断左右端点之间的和是否是k的倍数,这里的时间复杂度是 O ( n 2 ) O(n^2) O(n2)

这里我们想办法找到优化方法,假设先枚举右端点,再枚举左端点,那么对于每一个右端点,他的目的就是要找到有若干左端点,满足K倍条件

这里我们加入前缀和的思想

K倍条件为 ( p r e [ R ] ? p r e [ L ] ) % K = = 0 (pre[R]-pre[L])\%K == 0 (pre[R]?pre[L])%K==0

经过变换其实可以变成 p r e [ R ] % K = = p r e [ L ] % K pre[R]\%K==pre[L]\%K pre[R]%K==pre[L]%K

那么问题就变成了,有多少个 p r e [ R ] pre[R] pre[R] p r e [ L ] pre[L] pre[L]的余数相同

那我们其实就可以开一个数组,用于存储在前缀和数组中除K的每个余数的个数

在遍历前缀和数组的过程中,每一次遇到目标的余数,就在答案上加上之前的个数,因为新的数字和之前的每一个数字都算一组新的满足条件的情况,因此只需要 O ( n ) O(n) O(n)的时间

示例代码

#include<iostream>
using namespace std;
using ll = long long;

const int N = 1e5+10;
int n,k;
ll pre[N]; // 前缀和数组
ll cnt[N]; // 余数数组

int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) // 前缀和
    {
        cin>>pre[i];
        pre[i]+=pre[i-1];
    }
    
    ll ans = 0;
    cnt[0] = 1;
    for(int i=1;i<=n;i++) // 枚举右端点
    {
        ans += cnt[pre[i]%k]; // 找到相同余数的数字,加上之前的数
        cnt[pre[i]%k]++; // 添加新的数据
    }
    cout<<ans<<'\n';
    return 0;
}

对于cnt[0] = 1的理解

对于余数非0的数而言,他的结果一定是从0加到总数减1,对于余数是0本身的数,他自身就可以作为一个结果,因此要初始化为1

这里简单举个例子

例如

k = 2

序列为:1,2,3,4,5

前缀和为:1,3,6,10,15

余数为0的:6,10 一共两个

余数为1的:1,3,15 一共三个

我们来模拟一下这个过程

假设从余数为0的时候开始,没有初始化cnt[0] = 1

走到6,ans += 0

走到10,ans += 1

这里的含义就是,从6到10算一种情况,因此余数为0的情况就只有一种

如果余数为1

走到1,ans += 0

走到3,ans += 1

走到15,ans += 2

这里的含义就是走到1,只有一个数,不算区间,不算一次,走到3,1和3算一次,记录,走到15,1和15算一次,3和15算一次,因此加2

所以如果不初始化的话,结果应该是4

这里我们会发现一个问题,如果余数是0的话,他本身也可以作为一个区间

这时我们回头,初始化cnt[0] = 1

走到6,ans += 1

走到10,ans += 2

这里的含义就是,6本身是一种,加1,10本身是一种,6到10是一种,加2,一共就是3种

再加上余数是1的3种

答案就是6,这就是正确答案了

文章来源:https://blog.csdn.net/ye_yumo/article/details/135511891
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。