易混 2026 年江苏预赛 · P005899
把不能同时入选的元素连成冲突关系后,应先看各块的结构和目标的权重。链上求最大个数与互不相交冲突对上求最大元素和,虽都可分块,却不能照搬同一个隔项策略。
前题按模固定差分成较长的链,以相邻配对限制选取个数;后题须先用像仍在全集中的条件缩小候选集,此后只剩互不相交的冲突对,可逐对保留较大权值。
映射约束集合的最大元素和
设 是集合 的两个子集,,且 时,。记 为 的元素之和,则 的最大值 是。
分数写 a/b,根号写 √ 或 sqrt,π 写 pi 也可以。
条件 先给出 。
再由 ,冲突对只有 、、,每对保留较大者。
若 ,则 ,所以
从而 。因此
又因 且 ,所以 。 特别地, 在每一对
中至多取一个元素。其余候选元素为 ,故
取
则 均为 的子集,二者不相交,且对每个 都有 。此时
所以
上界推导覆盖了 的全部可能元素:大于 的元素因像超出全集而不能选, 至 中只有三对发生内部冲突。所给构造的像集合恰为 ,与 无交,故上界确实可达。
遇到“选入 就必须把 放入另一个不交集合”的极值题,先利用值域限制删去 不可能的 ,再把 与仍在候选范围内的 看作冲突对。对正权元素求和时, 每个冲突对保留权值较大者,最后还要给出满足所有蕴含条件的整体构造。
先由2n+2≤20限制n≤9,再找三对冲突并同时构造合法的B,关键在转出禁配结构。
易混 2026 年江苏预赛 · P005899
把不能同时入选的元素连成冲突关系后,应先看各块的结构和目标的权重。链上求最大个数与互不相交冲突对上求最大元素和,虽都可分块,却不能照搬同一个隔项策略。
前题按模固定差分成较长的链,以相邻配对限制选取个数;后题须先用像仍在全集中的条件缩小候选集,此后只剩互不相交的冲突对,可逐对保留较大权值。
已记下,谢谢!