精华内容
下载资源
问答
  • k倍区间c++
    2022-03-18 20:39:39

    资源限制

    时间限制:1.0s 内存限制:256.0MB

      给定一个长度为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 <xxx>
      不能通过工程设置而省略常用头文件。

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

    当时看到这题时的第一反应是用枚举,将这一串数的每一个区间都遍历一遍,于是有了如下的代码

    #include <bits/stdc++.h>
    using namespace std;
    long long a[100000];
    int main()
    {
    	int n,k;
    	int sum=0,cnt=0;
    	cin>>n>>k;
    	for(int i=0;i<n;i++)
    	{
    		cin>>a[i];
    	}
    	for(int i=0;i<n;i++)
    	{
    		sum=0;
    		for(int j=i;j<n;j++)
    		{
    			sum+=a[j];
    			if(sum%k==0)
    			{
    				cnt++;
    			}
    		}
    	}
    	cout<<cnt;
    	return 0;
    }
    

    提交后直接超时,过了两个测试点(后面的测试点全部超时),只有28分。

    于是参考了其它博客,发现了一种更好的方法,使用前缀和取模。

    我们假设n=5;k=2;

    输入的5个数为1,2,3,4,5的话

    程序输出6 这6种情况分别是123  1234  2345  345  2  4;

    若我们将前i项和的模存到一个数组mod[i]中,mod[1]表示前一项的和的模,mod[2]表示前两项的和的模,以此类推,再将mod[i]相同的个数用一个数组add[mod[i]]存起来,只需要计算C 2 add[i](高中数学的排列组合,2在上面,add[i]在下面)再加上add[0]的所有结果,便可求得正确答案,极大简化了运算时间。

    还是上面那个例子:1 2 3 4 5  假如是输入这5个数

    可得mod[1]=1(1%2=1)  mod[2]=1((1+2)%2=1)  mod[3]=0  mod[4]=0  mod[5]=1

    mod=1的个数有3个,mod=0的个数有2个,所以add[0]=2,add[1]=3;

    我们先看mod=0的时候,所对应的数是3,4,在(3,4]区间中(注意是左开右闭),4%2=0满足条件,

    mod=1的时候,所对应的数是1,2,5,在(1,2]区间中,2%2=0满足条件,(1,5]区间中,2345满足条件(2+3+4+5)%2=0,在(2,5]区间中,345满足条件。

    所以可以得出结论,从每一种前缀和(所选两个数的中间的数的和)的情况中任意选择两个数组成的区间都满足是k倍区间,其计算方法其实就是排列组合,上面的例子即可表示为C2 2加上C2 3结果为1+3=4,但实际结果有6种,是由于区间是左开右闭的,加上add[0]的所有结果也就是2和4两种,相当于区间左闭右闭,这两个数本身构成一个k倍区间,4+2=6,刚好是正确答案。

    于是可得如下代码:

    #include <bits/stdc++.h>
    using namespace std;
    long long mod[100010]={0},add[100010]={0};
    int main()
    {
    	int n,k,a;
    	long long cnt=0;
    	cin>>n>>k;
    	for(int i=1;i<=n;i++)
    	{
    		cin>>a;
    		mod[i]=(mod[i-1]+a)%k;
    		add[mod[i]]++;
    	}
    	for(int i=0;i<n;i++)
    	{
    		cnt+=add[i]*(add[i]-1)/2;//排列组合
    	}
    	cout<<cnt+add[0];
    	return 0;
    }
    

    提交后也是直接100分过了,当然要是第一次接触这类题,感觉这种做法还是很难想的,害,算法之路还是十分漫长啊~

    更多相关内容
  • C++K倍区间

    2022-07-26 20:39:08
    C++K倍区间

    题目

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

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

    输入格式
    第一行包含两个整数 N 和 K。

    以下 N 行每行包含一个整数 Ai。

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

    数据范围

    1≤N,K≤100000,
    1≤Ai≤100000
    

    输入样例:

    5 2
    1
    2
    3
    4
    5
    

    输出样例:

    6
    

    思路分析

    在这里插入图片描述

    在这里插入图片描述

    题解

    #include<iostream>
    #include<cstdio>
    
    using namespace std;
    
    const int N = 100010;
    typedef long long LL;
    int n , k ;
    
    LL s[N],cnt[N]; //s[N]是前缀和数组,cnt[N]为余数为i的数有多少个
    
    int main(){
        scanf("%d%d",&n,&k);
        //读入n个数
        for(int i = 1; i <= n; i ++){
            scanf("%lld",&s[i]);
            s[i] += s[i - 1];
        }
        
        //答案
        LL res = 0;
        cnt[0] = 1; //余数为0的数有 0 一个
        for(int i = 1; i <= n ; i++){
            res += cnt[s[i] % k];
            cnt[s[i] % k ] ++;
        }
        
        printf("%lld\n",res);
        return 0;
    }
    

    在这里插入图片描述

    展开全文
  • K倍区间c++

    2022-05-13 00:24:53
    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倍区间的数目。

    二.出现的问题

            1.审题

            倍数而不是固定的数,所以不能用二分法固定区间然后向右平移依次查找。

    三.问题分析

            可以硬计算前几项和,然后看余数,如果当前余数与之前出现过的余数相等,那么中间的差项区间一定是倍数区间。比如,1-5之和求余是1,1-10之和求余也是1,那么6-10之和一定是倍数。

    四.代码展示(不知道为什么仍无法提交,还是报错答案错误,但编译器上完美运行)

            有了上面分析,代码就简单多了。

    #include<iostream>
    using namespace std;
    int main()
    {
        int sum=0;
        int N,K;
        cin>>N>>K;
        int *number=new int[N+1];
        int *table=new int[K];
        for(int i=0;i<K;i++)
    		table[i]=0;
        table[0]=1;
        number[0]=0;
        for(int i=1;i<=N;i++)
        {
            cin>>number[i];
            number[i]+=number[i-1];
            sum+=table[number[i]%K];
            table[number[i]%K]++;
        }
        cout<<sum;
        return 0;
    }
    展开全文
  • 给定一个长度为 N 的数列,A1, A2, ···AN,如果其中一段连续的子序列 Ai,Ai+1, ···Aj( i≤j ) 之和是 K 的倍数,我们就称这个区间 [i, j] 是 K 倍区间。 你能求出数列中总共有多少个 K 倍区间吗? 输入描述 第...

    题目描述

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

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

    输入描述

    第一行包含两个整数 N 和 K( 1≤N,K≤105)。

    以下 N 行每行包含一个整数 Ai( 1 ≤Ai≤105)

    输出描述

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

    输入输出样例

    示例

    输入
    5 2
    1
    2
    3
    4
    5
    输出
    6

    运行限制

    最大运行时间:2s
    最大运行内存: 256M

    代码

    #include <iostream>
    using namespace std;
    int main()
    {
    	int x, y;
    	long long num;//k倍区间个数可能很多,所以使用long long数据类型
    	cin >> x >> y;
    	long long arr[100010] = { 0 };//保存序列的每个数的余数
    	long long ans[100010] = { 0 };//保存相同余数的数字的个数
    	num = 0;
    	for (int i = 1; i <= x; i++)
    	{
    		cin >> arr[i];
    		arr[i] += arr[i - 1];
    		arr[i] = arr[i] % y;
    		num += ans[arr[i]];
    		ans[arr[i]]++;
    	}
    	cout << num + ans[0];//由于num没有加上[0,x]区间上的个数,所以要加上ans[0]
    	return 0;
    }
    

    思路

    由于要找的序列一定是连续的,所以不妨将序列的前i项和记为数组的第i个元素,从而某区间[m,n]的区间和即为arr[n]-arr[m],若此区间为k倍区间,则(arr[n]-arr[m])%k=0成立,分析该式子得arr[n]%k=arr[m]%k。所以只需要将序列的前i项的和对k取余的余数存起来,计算相同的余数的和有多少个即可算出k倍区间的个数。

    展开全文
  • = j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。 你能求出数列中总共有多少个K倍区间吗? 输入格式: 第一行包含两个整数N和K。(1 <= N, K <= 100000) 以下N行每行包含一个整数Ai。(1 <= Ai <= ...
  • C++k倍区间(前缀和)

    2020-09-26 21:53:24
    给定一个长度为 N 的数列,A1,A2,…AN,如果其中一段连续的子序列 Ai,Ai+1,…Aj 之和是 K 的倍数,我们就称这个区间 [i,j] 是 K倍区间。 你能求出数列中总共有多少个 K倍区间吗? 输入格式 第一行包含两个整数 N和 K...
  • 蓝桥杯-k倍区间(C++)

    2021-04-14 20:21:15
    蓝桥杯--k倍区间题目描述我的思路代码展示 题目描述 给定一个长度为N的数列,A1, A2, … AN,如果其中一段连续的子序列Ai, Ai+1, … Aj(i <= j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。 你能求出数列...
  • = j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。  你能求出数列中总共有多少个K倍区间吗? 输入格式  第一行包含两个整数N和K。(1 <= N, K <= 100000)  以下N行每行包含一个整数Ai。(1 <= Ai &l...
  • = j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。 你能求出数列中总共有多少个K倍区间吗? 输入 ----- 第一行包含两个整数N和K。(1 <= N, K <= 100000) 以下N行每行包含一个整数Ai。(1 <= Ai <= ...
  • = j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。 你能求出数列中总共有多少个K倍区间吗? 输入 第一行包含两个整数N和K。(1 <= N, K <= 100000) 以下N行每行包含一个整数Ai。(1 <= Ai <= ...
  • 【蓝桥杯C++k倍区间

    2022-03-02 18:26:17
    本题为,巧用前缀和+数学表达式转换 优化为O(N), 代码思路 #include <iostream> #include <cstdio>...int n , k; int main() { scanf("%d%d" , &n , &k ); for( int i ..
  • 【蓝桥杯】历届试题 k倍区间C++)问题描述解题思路具体代码 问题描述 题目链接:k倍区间. 资源限制:时间限制:2.0s 内存限制:256.0MB 问题描述:  给定一个长度为N的数列,A1, A2, … AN,如果其中一段连续的子...
  • k倍区间 题目大意 简单来说,给你一个数组和一个数k,让你满足数组中连续区间和为k的倍数的区间有几个 思路 看到题目的连续区间的时候,就知道这题使用前缀和来写的,然后我喜闻乐见的TLE了 ,咳咳,看了题目100000...
  • 前缀和对 K 取模,统计答案的时候就是前面有多少个前缀和与该位置前缀和 % K 下相等,这样相减之后这些区间和 % K 下等于 0,也就是 K 的倍数了,我用分块来维护(数据结构学傻了,其实只需要开一个桶统计一个位置...
  • 试题 历届试题 k倍区间                              &...
  • k倍区间 蓝桥杯 C/C++

    2020-05-06 14:21:07
    标题: k倍区间 给定一个长度为N的数列,A1, A2, … AN,如果其中一段连续的子序列Ai, Ai+1, … Aj(i <= j)之和是K的倍数, 我们就称这个区间[i, j]是K倍区间。 你能求出数列中总共有多少个K倍区间吗? 输入 第一...
  • K倍区间h

    2021-11-18 20:43:48
    K倍区间 题目 给定一个长度为 N 的数列,A1,A2,…A ,如果其中一段连续的子序列 Ai,Ai+1,…A 之和是 K 的倍数,我们就称这个区间 [ i , j ] 是 K 倍区间。 你能求出数列中总共有多少个 K 倍区间吗? 输入格式 第一...
  • = j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。 你能求出数列中总共有多少个K倍区间吗? 输入格式  第一行包含两个整数N和K。(1 &lt;= N, K &lt;= 100000)  以下N行每行包含一个整数Ai。(1 &...
  • 算法-k倍区间

    2022-08-26 13:38:52
    k倍区间
  • 给定一个长度为 NN 的数列,A1,A2,…AN,如果其中一段连续的子序列 Ai,Ai+1,…Aj之和是 K 的倍数,我们就称这个区间 [i,j] 是 K 倍区间。 你能求出数列中总共有多少个 K 倍区间吗? 输入格式 第一行包含两个整数 ...
  • 给定一个长度为 N 的数列,A1,A2,…AN,如果其中一段连续的子序列 Ai,Ai+1,…Aj 之和是 K 的倍数,我们就称这个区间 [i,j] 是 K 倍区间。 你能求出数列中总共有多少个 K 倍区间吗? 输入格式 第一行包含两个整数 N ...
  • 这个很明显,只要整数取余为0,那必然是符合k区间条件的,这里ans++应该不难理解,因为sum中存储的全是余数,必然不会全是0,有人会有疑惑,假如有多个不为0的余数存在,那么sum[i] == 0这个条件还能成立吗?...
  • K倍区间题目来源:第八届蓝桥杯省赛Java/C++大学B组时间限制:\(1000ms\) 内存限制:\(64mb\)题目描述给定一个长度为 \(N\) 的数列,\(A_1,A_2,…,A_N\),如果其中一段连续的子序列 \(A_i,A_{i+1},…,A_j\) 之和是 \...
  • 看大佬的代码看了半天,终于算是懂了标题: k倍区间给定一个长度为N的数列,A1, A2, … AN,如果其中一段连续的子序列Ai, Ai+1, … Aj(i <= j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。你能求出数列中...
  • 蓝桥杯第八届省赛-k倍区间给定一个长度为N的数列,A1, A2, … AN,如果其中一段连续的子序列Ai, Ai+1, … Aj(i <= j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。 你能求出数列中总共有多少个K倍区间吗? ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,970
精华内容 2,388
关键字:

k倍区间c++