首页 > 代码库 > POJ 2356 Find a multiple 鸽巢原理
POJ 2356 Find a multiple 鸽巢原理
题目来源:POJ 2356 Find a multiple
题意:n个数 选出任意个数 使得这些数的和是n的倍数
思路:肯定有解 并且解是连续的一段数
证明:
假设有m个数 a1,a2,a3...am s1 s2 s3...sm为前缀和 s1 = a1 s2 = a1+a2 s3 = a1+a2+a3... sm = a1+a2+a3+...+am
1.如果某个前缀和si%m == 0 那么得到解
2.设x1=s1%m x2 = s2%m x3 = s3%m xm = sm%m
因为1不成立 所以xi > 1 && xi < m 由鸽巢原理的必定存在一对i j 使得xi == xj 得到解
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; const int maxn = 105010; int a[maxn]; int b[maxn]; int c[maxn]; int main() { int n, m; while(scanf("%d", &n) != EOF) { memset(b, 0, sizeof(b)); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); c[i] = a[i]; a[i] += a[i-1]; a[i] %= n; } for(int i = 1; i <= n; i++) { //c[i] += a[i-1]; if(a[i] == 0 || b[a[i]]) { int j = 1; if(b[a[i]]) j = b[a[i]]+1; printf("%d\n", i-j+1); for( ; j <= i; j++) { printf("%d\n", c[j]); } break; } b[a[i]] = i; } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。