N的倍数
2024-09-07 14:32:08
一个长度为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
C++的运行时限为：1000 ms ，空间限制为：131072 KB
根据抽屉原理，必有答案。
可以想象，把每个数都都mod一下n，数列中只会存在0~n-1的数。
可以想象，这些数必然能够组成n的倍数。
做法是弄一个前缀和，
如果h[i]==0,输出s[1]~s[i]；
如果h[l]+h[r]==0,输出s[l+1]~s[r];
代码实现：
#include<cstdio>
int n;
int s[],h[];
int v[];
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&s[i]);
h[i]=(s[i]+h[i-])%n;
if(!h[i]){
printf("%d\n",i);
for(int j=;j<=i;j++)
printf("%d\n",s[j]);
return ;
}
if(v[h[i]]){
printf("%d\n",i-v[h[i]]);
for(int j=v[h[i]]+;j<=i;j++)
printf("%d\n",s[j]);
return ;
}
v[h[i]]=i;
}
}
答案好像只要可以就行，好强的数据，好强的评测机。
题目来源：51Nod
最新文章
- OC泛型
- modprobe和lsmod命令配合使用
- SSL/TLS协议运行机制
- js中获取键盘事件【转】
- The Truth About .NET Objects And Sharing Them Between AppDomains
- nginx的autoindex-目录浏览还有其它两个参数
- Centroid - SGU 134(树的搜索)
- Ubuntu上CUDA和CUDNN的安装
- k8s部署dashboard:v1.5.1
- 浅谈 MongoDB
- 洛谷P4926 [1007]倍杀测量者(差分约束)
- vue cli 项目的提交
- js插件---iCheck是用来做什么的
- for in和for of
- 在平台中使用JNDI 数据源
- LeetCode SQL:Employees Earning More Than Their Managers
- Beta Scrum Day 3 — 听说
- Nginx配置PATHINFO隐藏index.php
- js判断向量叉点 并求出交点坐标
- GCJ 2015R2(Bilingual-最小割)