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;
}

 

这篇关于POJ 2356 Find a multiple 鸽巢原理的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---