『算法-ACM 竞赛-数学-数论』鸽巢原理

鸽巢原理：

所谓鸽巢原理即 n+1 只鸽子，只有 n 个巢，则至少有一鸽巢有两只鸽子。

鸽巢原理又叫抽屉原理,球盒原理。

推广：

如果要把 n 个物件分配到 m 个容器中，必有至少一个容器容纳至少⌈n / m⌉个物件。（⌈x⌉大于等于 x 的最小的整数）

poj2356 Find a multiple（抽屉原理）

题目大意就是先给出一个数 N，接着再给出 N 个数，要你从这 N 个数中任意选择 1 个或多个数，使得其和是 N 的倍数

如果找不到这样的答案 则输出 0

答案可能有多个，只用任意输出一个解就行。

输出的第一行是选择元素的个数 M，接着 M 行分别是选择的元素的值

由鸽笼原理可知此题一定有解，不存在输出 0 的结果

分析：

我们可以依次求出 a[0],a[0]+a[1],a[0]+a[1]+a[2],……,a[0]+a[1]+a[2]…+a[n]；

假设分别是 sum[0],sum[1],sum[2],……,sum[n]

如果在某一项存在是 N 的倍数，则很好解，即可直接从第一项开始直接输出答案

但如果不存在，则 sum[i]%N 的值必定在[1,N-1]之间，又由于有 n 项 sum，有抽屉原理：

把多于 n 个的物体放到 n 个抽屉里，则至少有一个抽屉里有 2 个或 2 个以上的物体。
则必定有一对 i，j，使得 sum[i]%N=sum[j]%N，其中 i！=j，不妨设 j>i

则（sum[j]-sum[i]）%N=0，故 sum[j]-sum[i]是 N 的倍数

则只要输出从 i+1 ～ j 的所有的 a 的值就是答案

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
int n,a[10010],sum,sum0;
bool vis[10010]={0};

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    vis[0]=1;sum=0;
    for(int i=1;i<=n;i++)
    {
        sum+=a[i];
        sum%=n;
        if (vis[sum])
        {
            sum0=0;
            int s,t=i;
            if (sum0==sum) s=1;
            else
            {
                for(int j=1;j<=n;j++)
                {
                    sum0+=a[j];
                    sum0%=n;
                    if (sum0==sum) {s=j+1;break;}
                }
            }
            printf("%d\n",t-s+1);
            for(int j=s;j<=t;j++)
                printf("%d\n",a[j]);
            break;
        }
        else vis[sum]=1;
    }
    return 0;
}

一样的题目，不一样的感受：
POJ3370 Halloween treats