鸽笼原理

数学 鸽笼原理

定理

a1,a2,a3...am是正整数序列，至少存在整数k和r, 1 <= k < r <= m,使得ak+a(k+1)+...+ar是m的倍数。

几个推论

1. m只鸽子，n个笼，则至少有一个鸽笼里有不少于[(m - 1) / n] + 1只鸽子。
2. 若取n * (m - 1) + 1个球放进n个盒子，则至少有1个盒子有m个球。
3. 若m1,m2,...mn是n个正整数，而且(m1 + m2 + ... + mn) / n > r - 1 则m1,m2,...mn中至少有一个数不小于r

应用

POJ 2356

题意

给 n 个数，问其中是否存在某些数的和是 n 的倍数，如果存在，输出任意一组数字总数和每个数，否则输出 0

思路

根据鸽笼原理，答案一定存在且是连续。先求前k(1 <= k <= n)个数的和sum[k]，然后求sum[k]模除 n的值Mod[k]，如果存在 Mod[k] == 0，则直接输出结果，如果不存在，因为 1 <= Mod[k] <= n - 1，所以一定存在 Mod[a] == Mod[b] (a < b)，则a，b之间的数就是我们要求的结果

AC代码

const int maxn = 10005;
int num[maxn];
int pre[maxn];
void print(int pos) {
    printf("%d\n", pos);
    for (int i = 1; i <= pos; i ++) printf("%d\n", num[i]);
}
void print(int a, int b) {
    printf("%d\n", b - a);
    for (int i = a + 1; i <= b; i ++) printf("%d\n", num[i]);
}
int main() {
    int n;
    while (~scanf("%d", &n)) {
        bool flag = false;
        memset(pre, 0, sizeof(pre));
        int sum = 0, tmp, ans;
        for (int i = 1; i <= n; i ++) {
            scanf("%d", &num[i]);
            sum += num[i];
            tmp = sum % n;
            if (tmp == 0) {
                if (!flag) {
                    print(i);
                    flag = true;
                }
            } else {
                if (pre[tmp] && !flag) {
                    print(pre[tmp], i);
                    flag = true;
                } else pre[tmp] = i;
            }
        }
    }
    return 0;
}

POJ 3370

题意

类似于上一题，给n个数求是否存在某些数的和是c的倍数，c是小于n的，注意这一题输出的数字下标，且sum会超int

思路

见上一题

AC代码

const int maxn = 100005;
int pre[maxn];
int main() {
    int c, n;
    while (~scanf("%d %d", &c, &n)) {
        if (c == 0 && n == 0) break;
        ll sum = 0, cur, tmp;
        bool flag = false;
        memset(pre, 0, sizeof(pre));
        for (int i = 1; i <= n; i ++) {
            scanf("%lld", &cur);
            sum += cur;
            tmp = sum % c;
            if (tmp == 0) {
                if (!flag) {
                    for (int j = 1; j <= i; j ++) printf("%d%c", j, j == i ? '\n' : ' ');
                    flag = true;
                }
            } else {
                if (pre[tmp]) {
                    if (!flag) {
                        for (int j = pre[tmp] + 1; j <= i; j ++) printf("%d%c", j, j == i ? '\n' : ' ');
                        flag = true;
                    }
                } else pre[tmp] = i;
            }
        }
    }
    return 0;
}