易混 2022 年广西预赛 · P005924
把不能同时入选的元素连成冲突关系后,应先看各块的结构和目标的权重。链上求最大个数与互不相交冲突对上求最大元素和,虽都可分块,却不能照搬同一个隔项策略。
前题按模固定差分成较长的链,以相邻配对限制选取个数;后题须先用像仍在全集中的条件缩小候选集,此后只剩互不相交的冲突对,可逐对保留较大权值。
固定禁差集合的最大基数
已知集合 ,若 中任意两个数之差不等于 , 则 中元素个数的最大值为。
分数写 a/b,根号写 √ 或 sqrt,π 写 pi 也可以。
限制只涉及相差 的两个整数,因此按照模 的 余数分类后,每一类都成为一条等差数列;题目等价于从每条数列中选取互不相邻的项。
对 ,令
由于
当 时, 有 个元素;当 时, 有 个元素。
把 中的元素从小到大排列。相邻两项之差恰为 ,所以相邻两项不能同时属于 。若 有 个元素,将第 项配成一组,第 项配成一组,依此类推, 则每组至多选一个元素;若 为奇数,最后还剩一个元素。因此
共有 个余数类,故
另一方面,取
其中最大元素为 ,且 。若 中两个数之差为 ,则它们模 同余;但同一余数类中两个所选元素之差必为 的倍数,不可能等于 。因此 满足题意。
所以所求最大值为
表明恰有 条链长为 ,其余 条链长为 ; 两种链的最大不相邻选取数均为 。上界为 , 而上述集合确有 个元素并避开差 ,所以上界能够达到。另对较小的 与禁差 作穷举检查,结果与逐余数类公式一致。
遇到“任意两数之差不能等于固定整数 ”的集合极值问题,可先按模 分类。 每个余数类形成公差为 的链,禁差条件转化为链上的相邻项不能同时选取; 长度为 的链至多选 项,再逐类求和并给出隔项选取构造即可。
须把禁差96转成96条不相邻选取链,再给隔项取数的达到实例;关键在链结构的识别。
易混 2022 年广西预赛 · P005924
把不能同时入选的元素连成冲突关系后,应先看各块的结构和目标的权重。链上求最大个数与互不相交冲突对上求最大元素和,虽都可分块,却不能照搬同一个隔项策略。
前题按模固定差分成较长的链,以相邻配对限制选取个数;后题须先用像仍在全集中的条件缩小候选集,此后只剩互不相交的冲突对,可逐对保留较大权值。
已记下,谢谢!