精华内容
下载资源
问答
  • k倍区间
    2018-03-08 20:58:54
    /**
     * 
     */
    import java.util.Scanner;
    /**
     * @author Administrator 2018年3月8日
     * @功能说明:第十题:k倍区间 标题: 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
     * @version:

     * 分析:这道题就是求一个区间[i,j]和是K的倍数(sum[j] -sum[i-1])%k =0;在经过恒等变换则sum[j]%k==sum[i-1]%k

     */
    public class NO_10 {
    	
    	
    	public static void main(String[] args) {
    		int n,k;
    		int i,j;
    		Scanner sc = new Scanner(System.in);
    		n = sc.nextInt();
    		k = sc.nextInt();
    		int[] bk = new int[k];
    		int[] temp = new int[n+1];
    		bk[0] = 0;
    		//初始化
    		for(i = 0; i < n; i++) {
    			temp[i] = sc.nextInt();
    			
    		} 
    		temp[0] %= k;
    //		求每次前缀和模k的值
    		for(j = 1; j < n; j++) {
    			temp[j] = (temp[j] + temp[j-1])%k;
    		}
    //		如果temp中有两个数据经过取余过后值相同方案+1
    		int ans = 0;
    		for(j = 0; j < n; j++) {
    			ans+=(bk[temp[j]]++);
    		}
    		//这个位置参考别人的结果要加上,但是自己分析感觉有问题
    		System.out.println(ans + bk[0]);
    		
    		sc.close();
    		
    	}
    }


    更多相关内容
  • 试题 历届试题 k倍区间 资源限制 时间限制:2.0s 内存限制:256.0MB 问题描述  给定一个长度为N的数列,A1, A2, … AN,如果其中一段连续的子序列Ai, Ai+1, … Aj(i <= j)之和是K的倍数,我们就称这个区间[i, j]...
  • k倍区间

    2021-04-09 22:51:23
    = j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。 你能求出数列中总共有多少个K倍区间吗? 输入格式  第一行包含两个整数N和K。(1 <= N, K <= 100000)  以下N行每行包含一个整数Ai。(1 <= Ai <=...

    资源限制
    时间限制:2.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
      不能通过工程设置而省略常用头文件。

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

    思想:两个前缀和模k的值相同的区间,可以产生一个k倍区间。

    #include<bits/stdc++.h>
    using namespace std;
    int main() {
    	int pre_sum[100001];
    	int cnt[100001] = {0};
    	int n, k;
    	cin >> n >> k;
    	pre_sum[0] = 0;
    	int num,res = 0;
    	for (int i = 1; i <= n; i++) {
    		cin >> num;
    		pre_sum[i] = (pre_sum[i - 1] + num)%k;
    		res += cnt[pre_sum[i]];
    		cnt[pre_sum[i]]++;
    	}
    	res = res + cnt[0];
    	cout << res << endl;
    	return 0;
    }
    
    展开全文
  • = j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。  你能求出数列中总共有多少个K倍区间吗? 输入格式  -----  第一行包含两个整数N和K。(1 <= N, K <= 100000)  以下N行每行包含一个整数Ai。(1 &...

    资源限制

    时间限制: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分过了,当然要是第一次接触这类题,感觉这种做法还是很难想的,害,算法之路还是十分漫长啊~

    展开全文
  • K倍区间h

    2021-11-18 20:43:48
    K倍区间 题目 给定一个长度为 N 的数列,A1,A2,…A ,如果其中一段连续的子序列 Ai,Ai+1,…A 之和是 K 的倍数,我们就称这个区间 [ i , j ] 是 K 倍区间。 你能求出数列中总共有多少个 K 倍区间吗? 输入格式 第一...

    K倍区间

    题目

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

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

    输入格式

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

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

    输出格式

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

    数据范围

    1 ≤ N , K ≤ 100000 ,
    1 ≤ A~i ~≤ 100000

    输入样例:

    5 2
    1
    2
    3
    4
    5c
    

    输出样例:

    6
    

    题意
    给定一段数列和一个整数K,假若其中的一段数之和是K的倍数,则称这段区间为K倍区间,问这段数列有多少个K倍区间

    思路
    前缀和
    摘抄一位大佬的题解(我好菜)
    在这里插入图片描述
    AC代码

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    
    using namespace std;
    
    typedef long long LL;
    
    const int N = 100010;
    
    int n, k;
    LL s[N], cnt[N];
    
    int main()
    {
        scanf("%d%d", &n, &k);
        for (int i = 1; i <= n; i ++ )
        {
            scanf("%lld", &s[i]);
            s[i] += s[i - 1];
        }
    
        LL res = 0;
        cnt[0] = 1;
        for (int i = 1; i <= n; i ++ )
        {
            res += cnt[s[i] % k];
            cnt[s[i] % k] ++ ;
        }
    
        printf("%lld\n", res);
    
        return 0;
    }
    
    
    展开全文
  • 题目: 这个题想还是挺好想的,区间问题嘛,一看...(1)如果a[i] % k == 0 这个不用说 ans++ 即可 (2)除去第一种情况,剩下就是要减的了,就是要算2个区间的差值了,这里我们可以来看我们需要找的是 (a[i] - a[...
  • 蓝桥杯 K倍区间

    2022-01-22 11:57:44
    题目传送门: K倍区间 给定一个长度为 N 的数列,A1,A2,…AN,如果其中一段连续的子序列 Ai,Ai+1,…Aj 之和是 K 的倍数,我们就称这个区间 [i,j] 是 K 倍区间。 你能求出数列中总共有多少个 K 倍区间吗? 输入格式 ...
  • K倍区间 -- 蓝桥杯

    2022-03-31 22:19:50
    K倍区间 – 蓝桥杯 题目描述: 给定一个长度为 N 的数列,A1,A2,…AN,如果其中一段连续的子序列 Ai,Ai+1,…Aj 之和是 K 的倍数,我们就称这个区间 [i,j] 是 K 倍区间。 你能求出数列中总共有多少个 K 倍区间吗? ...
  • python蓝桥杯 k倍区间

    2022-03-31 00:21:29
    = j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。  你能求出数列中总共有多少个K倍区间吗? 输入格式  5 2  1  2  3  4  5  程序应该输出:  6 首先第一想法肯定是暴力,显然超时。 n,k=map...
  • Java实现蓝桥杯 历届试题 k倍区间

    千次阅读 2019-06-14 19:23:00
    历届试题 k倍区间 时间限制:2.0s 内存限制:256.0MB 问题描述  给定一个长度为N的数列,A1, A2, ...
  • 第十题: k倍区间 给定一个长度为N的数列,A1, A2, … AN,如果其中一段连续的子序列Ai, Ai+1, … Aj(i &lt;= j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。 你能求出数列中总共有多少个K倍区间吗? ...
  • = j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。 你能求出数列中总共有多少个K倍区间吗? 输入 ----- 第一行包含两个整数N和K。(1 <= N, K <= 100000) 以下N行每行包含一个整数Ai。(1 <= Ai <= ...
  • 看大佬的代码看了半天,终于算是懂了标题: 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 &...
  • k倍区间(思维)

    千次阅读 多人点赞 2019-03-21 23:34:43
    k倍区间 给定一个长度为N的数列,A1, A2, … AN,如果其中一段连续的子序列Ai, Ai+1, … Aj(i <= j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。 你能求出数列中总共有多少个K倍区间吗? 输入 第一行包...
  • 蓝桥杯 k倍区间

    2018-03-30 15:04:59
    = j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。 你能求出数列中总共有多少个K倍区间吗? 输入-----第一行包含两个整数N和K。(1 &lt;= N, K &lt;= 100000) 以下N行每行包含一个整数Ai。(1 &lt;= ...
  • 1230. K倍区间

    2022-03-23 11:02:14
    Acwing 1230. K倍区间
  • 资源限制 时间限制:2.0s 内存限制:256...= j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。 你能求出数列中总共有多少个K倍区间吗? 输入格式  第一行包含两个整数N和K。(1 <= N, K <= 100000)  以下...
  • 标题: k倍区间 给定一个长度为N的数列,A1, A2, … AN,如果其中一段连续的子序列Ai, Ai+1, … Aj(i &lt;= j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。 你能求出数列中总共有多少个K倍区间吗? ...
  • k倍区间题目描述思路分析三级目录 题目描述 给定一个长度为N的数列,A1, A2, … AN,如果其中一段连续的子序列Ai, Ai+1, … Aj(i <= j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。  你能求出数列中总共有...
  • 第八届真题-第十题:K倍区间

    千次阅读 2018-03-25 21:40:09
    = j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。你能求出数列中总共有多少个K倍区间吗?输入第一行包含两个整数N和K。(1 &lt;= N, K &lt;= 100000) 以下N行每行包含一个整数Ai。(1 &lt;= Ai &...
  • k倍区间(蓝桥杯)

    千次阅读 2019-02-19 11:31:33
    = j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。 你能求出数列中总共有多少个K倍区间吗? 输入 ----- 第一行包含两个整数N和K。(1 &lt;= N, K &lt;= 100000) 以下N行每行包含一个整数Ai。(1 &...
  • k倍区间-蓝桥杯

    2022-01-18 16:18:35
    2017省赛蓝桥杯k倍区间python 最近在准备蓝桥杯,有个寒假刷题,自己写了个超时了,然后又找了找,终于找到一个没超时的。改成python代码后,看了半天没看懂,然后又去翻了翻,看了别人的评论终于弄懂了。写个博客...
  • 给定一个长度为 N 的数列,A1,A2,…AN,如果其中一段连续的子序列 Ai,Ai+1,…Aj 之和是 K 的倍数,我们就称这个区间 [i,j] 是 K 倍区间。 你能求出数列中总共有多少个 K 倍区间吗? 输入格式 第一行包含两个整数 N ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 30,576
精华内容 12,230
关键字:

k倍区间