鸽巢原理学习

定理描述:
第一鸽巢原理:

  1. 把多于 m × n + 1 ( n 不 为 0 ) m\times n+1(n不为 0) m×n+1(n不为0)个的物体放到 n n n 个抽屉里,则至少有一个抽屉里有不少于 m + 1 m+1 m+1的物体
  2. 把 n − 1 n-1 n−1件东西放入 n n n个抽屉,则至少一个抽屉是空的。
  3. 无穷多的东西放到有限的抽屉里,至少一个抽屉有无数个东西。

第二鸽巢原理:
1.把 m × n - 1 m\times n-1 m×n-1个物体放入 n n n个抽屉中,其中必有一个抽屉中至多有 m − 1 m-1 m−1个物体。

一些结论:
1. n + 1 n+1 n+1个互不相同的正整数,它们全都小于或等于 2 n 2n 2n,证明当中一定有两个数是连续的。
2. m m m个在模 m m m意义下不同的正整数可以构成模 m m m的完全剩余系。
3. n n n个数( n > m n > m n>m),必然可以找到两个
4. m m m个互不相同的数,一定能找到若干连续的数,使他们之和模 m m m为 0 0 0
题目:
Flowers ( 2019-ICPC沈阳 - L )
题解:

上一篇:CF 1061 E


下一篇:区间 DP