企业网站开发方案,手机测评网站,网站怎么免费注册,html中文美食网站题干#xff1a;
一个长度为N的数组A#xff0c;从A中选出若干个数#xff0c;使得这些数的和是N的倍数。
例如#xff1a;N 8#xff0c;数组A包括#xff1a;2 5 6 3 18 7 11 19#xff0c;可以选2 6#xff0c;因为2 6 8#xff0c;是8的倍数。
Input
第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个数NN为数组的长度同时也是要求的倍数。(2 N 50000) 第2 - N 1行数组A的元素。(0 Aii 10^9)
Output
如果没有符合条件的组合输出No Solution。 第1行1个数S表示你所选择的数的数量。 第2 - S 1行每行1个数对应你所选择的数。
Sample Input
8
2
5
6
3
18
7
11
19
Sample Output
2
2
6
解题报告 跟蓝桥的那道K倍区间很像只是这题不是连续区间了所以有点伤。。想了半天没想出来。 其实是可以转化成那一题的反正是个SPJ问题嘛我们可以根据抽屉定理构造出一组解就是一定存在连续区间使得、、、于是就转化成那道K倍区间了。。。预处理取模求前缀遍历求解。。。思路就一样了。
普及知识
桌上有十个苹果要把这十个苹果放到九个抽屉里无论怎样放我们会发现至少会有一个抽屉里面至少放两个苹果。这一现象就是我们所说的“抽屉原理”。 抽屉原理的一般含义为“如果每个抽屉代表一个集合每一个苹果就可以代表一个元素假如有n1个元素放到n个集合中去其中必定有一个集合里至少有两个元素。” 抽屉原理有时也被称为鸽巢原理。它是组合数学中一个重要的原理。又叫狄利克雷抽屉原理
AC代码
#includebits/stdc.h
#define pm make_pair
#define fi first
#define se second
using namespace std;
int a[500005];
pairint,int sum[500005];
int main()
{int n,ans;cinn;sum[0] pm(0,0);for(int i 1; in; i) {scanf(%d,ai);sum[i] pm((sum[i-1].first a[i]) % n,i);}sort(sum1,sumn1);for(int i 1; in; i) {if(sum[i].first sum[i1].first) {ans i;break;}}printf(%d\n,sum[ans1].second - sum[ans].second);for(int i sum[ans].second1;isum[ans1].second; i) {printf(%d\n,a[i]);} return 0 ;}
