51Nod1103 N的倍数前缀和+抽屉定理

女爷i 2022-05-15 05:27 139阅读 0赞

题目链接：[这里写链接内容][Link 1]  
一个长度为N的数组A，从A中选出若干个数，使得这些数的和是N的倍数。  
例如：N = 8，数组A包括：2 5 6 3 18 7 11 19，可以选2 6，因为2 + 6 = 8，是8的倍数。  
Input  
第1行：1个数N，N为数组的长度，同时也是要求的倍数。(2 <= N <= 50000)  
第2 - N + 1行：数组A的元素。(0 < A\[i\] <= 10^9)  
Output  
如果没有符合条件的组合，输出No Solution。  
第1行：1个数S表示你所选择的数的数量。  
第2 - S + 1行：每行1个数，对应你所选择的数。  
Input示例  
8  
2  
5  
6  
3  
18  
7  
11  
19  
Output示例  
2  
2  
6

前缀和+抽屉定理

#include<iostream>
    #include<cstdio>
    
    using namespace std;
    typedef long long ll;
    const int maxn=50000+10;
    int sum;
    int a[maxn];
    int vis[maxn];
    int main() {
    	int n;
    	scanf("%d",&n);
    	for(int i=0; i<n; i++) {
    		scanf("%d",&a[i]);
    	}
    	for(int i=0; i<n; i++) {
    		sum=(sum+a[i])%n;
    		if(!sum) {
    			printf("%d\n",i+1);
    			for(int j=0; j<=i; j++) {
    				printf("%d\n",a[j]);
    			}
    			break;
    		} else if(vis[sum]) {
    			printf("%d\n",i-vis[sum]);
    			for(int j=vis[sum]+1; j<=i; j++) {
    				printf("%d\n",a[j]);
    			}
    			break;
    		}
    		vis[sum]=i;
    	}
    
    }

[Link 1]: https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1103

发表评论取消回复

表情：

评论列表（有 0 条评论，139人围观）

还没有评论，来说两句吧...

相关阅读

相关 51nod1296 有限制的排列递推+前缀和优化

[1296 有限制的排列][1296] ![ok.png][] 题目来源： [HackerRank][] [1296]: http://www.51nod.com/onl

朴灿烈づ我的快乐病毒、/ 2024年02月18日 18:12/ 0 赞/ 32 阅读

相关 51nod 1079 中国剩余定理

[1079 中国剩余定理][1079] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB 分值: 0 [1079]: http://www.51

逃离我推掉我的手/ 2024年02月17日 19:36/ 0 赞/ 10 阅读

相关 51nod 1043

题意：求在2\n位的数字中，前n位的和等于后n位的和的个数，比喻n=1的时候，11,22,33...99等数字都是的，还有1102，2121等都是满足要求的数字。n<=10

灰太狼/ 2022年08月21日 03:14/ 0 赞/ 216 阅读

相关 51nod-加农炮

一个长度为M的正整数数组A，表示从左向右的地形高度。测试一种加农炮，炮弹平行于地面从左向右飞行，高度为H，如果某处地形的高度大于等于炮弹飞行的高度H（A\[i\] >= H），

男娘i/ 2022年06月17日 14:08/ 0 赞/ 226 阅读

相关 51Nod--1004 n^n的末位数字

题目链接：[http://www.51nod.com/onlineJudge/questionCode.html\!problemId=1004][http_www.51nod

古城微笑少年丶/ 2022年06月15日 12:22/ 0 赞/ 134 阅读

相关 51Nod--1008 N的阶乘 mod P

题目链接：[http://www.51nod.com/onlineJudge/questionCode.html\!problemId=1008][http_www.51nod

青旅半醒/ 2022年06月14日 00:20/ 0 赞/ 146 阅读

相关 51nod 1079中国剩余定理

[1079 中国剩余定理][1079] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB 分值: 0 [难度：基础题][Link 1] ![sta

心已赠人/ 2022年05月22日 02:11/ 0 赞/ 203 阅读

相关 3的幂的和 51Nod - 1013——同余定理+逆元

3的幂的和基准时间限制：1 秒空间限制：131072 KB 分值: 20 难度：3级算法题收藏关注求：30\+31\+...\+3Nmod1000000007

青旅半醒/ 2022年05月19日 13:41/ 0 赞/ 195 阅读

相关 51Nod1103 N的倍数前缀和+抽屉定理

题目链接：[这里写链接内容][Link 1] 一个长度为N的数组A，从A中选出若干个数，使得这些数的和是N的倍数。例如：N = 8，数组A包括：2 5 6 3 18

女爷i/ 2022年05月15日 05:27/ 0 赞/ 140 阅读

相关（前缀异或和）51nod 2128 前缀异或

[2128 前缀异或][2128] 输入一个长度为n(1 <= n <= 100000)数组a\[1\], a\[2\], ..., a\[n\]。输入一个询问数m(

淡淡的烟草味﹌/ 2022年02月16日 03:29/ 0 赞/ 358 阅读