POJ 2356 Find a multiple
题意:解题过程:AC代码:
POJ 2356 Find a multiple
题目传送门
题意:
给出你n个数,问你能否从这n个数中取出任意数量的数,使这些数的和是n的倍数,不行则输出0,否则输出方案。
解题过程:
根据抽屉原理可知这题并不存在0的情况,因为我们设前i个数的和对n取模为Si,如果出现Si等于0的情况,那么答案就是这前i个数,否则这些数必定是分布在1~n-1这部分内,所以必定存在不同的i,j,他们的S值相同,而答案就是i+1到j这个区间。而解这道题的方法也是如此。
AC代码:
#pragma GCC optimize (3)
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <vector>
#include <cstdlib>
#include <cstring>
using namespace std;
const int maxn=
10005;
int n;
int a[maxn],pos[maxn],pre[maxn];
int main() {
scanf(
"%d",&n);
for(
int i=
1;i<=n;i++) {
scanf(
"%d",&a[i]);
}
int l=
1,r;
for(
int i=
1;i<=n;i++) {
pre[i]=pre[i-
1]+a[i];
pre[i]%=n;
if(pre[i]==
0) {
r=i;
break;
}
if(pos[pre[i]]!=
0) {
l=pre[i]+
1;
r=i;
break;
}
pos[pre[i]]=i;
}
printf(
"%d\n",r-l+
1);
for(
int i=l;i<=r;i++) {
printf(
"%d\n",a[i]);
}
return 0;
}
本人蒟蒻OIer一枚,欢迎加QQ:840776708一起学习蛤。
转载于:https://www.cnblogs.com/Apocrypha/p/9433666.html
相关资源:JAVA上百实例源码以及开源项目