专题地图 › 并排比较
这两道题哪里一样?想好再点
P005910 · 组合计数综合
已知集合 ( 且 )的任意一个 划分 ,一定存在某个集合 ( 且 ),在 中有两个元素 满足
则 的最小值为。
P006652 · 组合计数综合
某校举办数学文化节,据统计当天共有 多(不少于 ,小于 )名同学进校参观,每位同学进校参观一段时间后离开(之后不会再进来)。若无论这些同学以怎样的时间安排参观,我们都能找到 位同学,使得要么这 位同学在某个时间都在校园内参观,要么任何时间他们中都没有两个人同时在校园内参观。求 的最大值。
“任意安排都必有一组”的阈值题,需要保证方向与坏构造两半。先把对象分成彼此不发生目标关系的组,用容量或鸽巢给出必然性;最小或最大保证值还必须由满足全部原限制的分组反例锁定。
前题先找两两比例接近的一批整数迫使同组数对,再以同余类拉开间距;后题把参观时间化为区间,贪心分成互不重叠组,用两种群体规模的乘积界,并反向构造分离时间段。