poj 3370 Halloween treats (组合数学：鸽巢原理)

本文主要是介绍poj 3370 Halloween treats (组合数学：鸽巢原理)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

判断一组数中是否存在和整除c的子集，若存在输出子集中元素对应下标

否则输出no sweets

取sum为第1个到当前第i堆糖果的集合

令tmp = sum%c

则在i从1到n的过程中，因为n>=c

当n>c时根据鸽巢原理tmp必然重复

我们可以简单的取重复之间的所有数

而当n==c时只需取1-使得tmp == 0之间（包括边界）的下标即可

可以得知此题恒有解

代码如下：

#include <cstdio>
#include <cstring>
#define MAXN 100100
using namespace std;int flag[MAXN];
int a[MAXN];int main(void) {int n, c, sum, tmp;while(scanf("%d%d", &c, &n) && (c||n)) {sum = 0;memset(flag, 0, sizeof(flag));for(int i=1; i<=n; ++i) {scanf("%d", &a[i]);}for(int i=1; i<=n; ++i) {sum += a[i];tmp = sum%c;sum %= c;if(tmp == 0) {printf("%d", 1);for(int j=2; j<=i; ++j)printf(" %d", j);break;} else {if(flag[tmp]) {printf("%d", flag[tmp]+1);for(int j=flag[tmp]+2; j<=i; ++j)printf(" %d", j);break;}}flag[tmp] = i;}puts("");}return 0;
}

这篇关于poj 3370 Halloween treats (组合数学：鸽巢原理)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---