抽屉原理简述:

第一抽屉原理:

  1. 把多于n+k个的物体放到n个抽屉里,则至少有一个抽屉里的东西不少于两件。
  2. 把多于mn(m乘以n)+1(n不为0)个的物体放到n个抽屉里,则至少有一个抽屉里有不少于(m+1)的物体。
  3. 把无穷多件物体放入n个抽屉,则至少有一个抽屉里 有无穷个物体。

第二抽屉原理:

  1. mn1(mn-1)个物体放入n个抽屉中,其中必有一个抽屉中至多有m1(m—1)个物体 (例如,将3×5-1=14个物体放入5个抽屉中,则必定有一个抽屉中的物体数少于等于3-1=2)。

HDU_1205 吃糖果

Problem Description

HOHO,终于从Speakless手上赢走了所有的糖果,是Gardon吃糖果时有个特殊的癖好,就是不喜欢将一样的糖果放在一起吃,喜欢先吃一种,下一次吃另一种,这样;可是Gardon不知道是否存在一种吃糖果的顺序使得他能把所有糖果都吃完?请你写个程序帮忙计算一下。

Input

第一行有一个整数T,接下来T组数据,每组数据占2行,第一行是一个整数N(0<N<=1000000),第二行是N个数,表示N种糖果的数目Mi(0<Mi<=1000000)。

Output

对于每组数据,输出一行,包含一个"Yes"或者"No"。

Sample Input

2
3
4 1 1
5
5 4 3 2 1

Sample Output

No
Yes

题解:

设其中某类糖果的数量最多,数量为max,总的糖果数为sum,如果mam>sum-max+1;则一定不能吃完,否则能吃完。

代码:

#include <stdio.h>
int main()
{ 
  	__int64  n,m,t,max,sum;
    scanf("%I64d",&t);
    while(t--){
        sum=0;
        max=0;
        scanf("%I64d",&n);
        for(int i=0;i<n;i++){
            scanf("%I64d",&m);
            sum+=m;
            if(max<m)
            	max=m;        
        }
        sum-=max;
        if(max>sum+1)
        	printf("No\n");
        else
        	printf("Yes\n");
    }
        return 0;
}

HDU_1808 Halloween treats

Problem Description

Every year there is the same problem at Halloween: Each neighbour is only willing to give a certain total number of sweets on that day, no matter how many children call on him, so it may happen that a child will get nothing if it is too late. To avoid conflicts, the children have decided they will put all sweets together and then divide them evenly among themselves. From last year's experience of Halloween they know how many sweets they get from each neighbour. Since they care more about justice than about the number of sweets they get, they want to select a subset of the neighbours to visit, so that in sharing every child receives the same number of sweets. They will not be satisfied if they have any sweets left which cannot be divided.

Your job is to help the children and present a solution.

Input

The input contains several test cases.
The first line of each test case contains two integers c and n (1 ≤ c ≤ n ≤ 100000), the number of children and the number of neighbours, respectively. The next line contains n space separated integers a1 , ... , an (1 ≤ ai ≤ 100000 ), where ai represents the number of sweets the children get if they visit neighbour i.

The last test case is followed by two zeros.

Output

For each test case output one line with the indices of the neighbours the children should select (here, index i corresponds to neighbour i who gives a total number of ai sweets). If there is no solution where each child gets at least one sweet, print "no sweets" instead. Note that if there are several solutions where each child gets at least one sweet, you may print any of them.

Sample Input

4 5
1 2 3 7 5
3 6
7 11 2 5 13 17
0 0

Sample Output

3 5
2 3 4

题解:

有c个孩子,去n个邻居家要糖果,现在已知每个邻居所能给的糖果数ai,问怎么个要法能保证全部所得的糖果能被c个孩子平分。

我们考虑前k个邻居的糖果总数,那么这样的和一共有n个,a1,a1+a2,...,a1+...+an,如果将他们分别除以孩子的个数c,那么余数只可能在1~c-1之间,换句话说,和有n个,而余数有c-1个,并且从题目中可知c<=n,那么根据抽屉原理可知,必然有两个和的余数是相同的,这也就意味着这两个和中包含的公有项的和能被c整除,即为所求答案。

代码:

include <cstdio>
include <cstring>

const int MAXN = 1e5+5;
int a[MAXN], SumMod[MAXN], flag[MAXN];

int main()
{
    int c, n;
    while(~scanf("%d%d", &c, &n) && (c+n))
    {
        SumMod[0] = 0;
        memset(flag, 0, sizeof(flag));
        for(int i=1; i<=n; ++i)
            scanf("%d", &a[i]);
        for(int i=1; i<=n; ++i)
        {
            SumMod[i] = (SumMod[i-1] + a[i]) % c;  // 处理前缀和,并取模
            if(flag[SumMod[i]] == 0)
                flag[SumMod[i]] = i;
            else                                   // 如果相同的余数在前面出现过
            {
                int j = flag[SumMod[i]] + 1;
                int k = j;
                for(; j<=i; ++j)                   // 公共项即为答案
                    if(j == k) printf("%d", j);
                    else printf(" %d", j);
                break;
            }
        }
        puts("");
    }
    return 0;
}