POJ 2356 Find a multiple (数学,前缀和)

mac2022-06-30  166

 

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上百实例源码以及开源项目
最新回复(0)