题解：P11634 [CTS2025] 仙人掌染色（暂无数据）

nullqtr_pwp · 2025-11-18 20:15:41 · 题解

注意到对于同一个位置，交换相邻两项不会对总贡献产生任何影响，因此每个点的贡献只与相邻黑边个数有关，有 n 条邻边其中 k 条染黑时，产生 g(n,k)=p\frac{nk(n-k)}{2} 的贡献。

考虑树的做法，直接在上面 dp：设 f_{u,0/1} 表示 u 子树中 (u,fa_u) 是否染黑的最大收益。转移形如，选 k 个取 f_{v,1}，剩下的取 f_{v,0}，最大化 \sum f_{v,i}。这是经典贪心，先取所有 f_{v,0}，然后选 k 个 f_{v,1}-f_{v,0} 最大的位置即可。进一步考虑边仙人掌的做法，首先建立圆方树，然后考虑环的问题怎么处理，注意到方点的儿子顺序对应的就是环的顺序，取出方点的父亲圆点 u 以及在这个方点的邻边 x,y，发现只关心 x,y 是否被选。再考虑下面的儿子，顺时针做一个 2\times 2 的矩阵乘法状物：记录首条边，它上一条边是否被选的状态，然后讨论下一条边是否被选。因此转移的重点依然在圆点的统计，需要对于邻接圆点，方点决策，这是一个比树部分更复杂的贪心。

问题转化：长度为 m 的物品集合，每个物品可以决策产生 1 的重量并且收益为 a_i，或者 2 的重量并且收益为 b_i，或者直接不选。需要对所有 k 求出重量恰好为 k 的最大收益。

对于 a_i<b_i-a_i 以及 a_i\ge b_i-a_i 讨论。对于后者发现可以拆成两个重量为 1 的独立物品。由于重量很小，经典结论是先考虑按照性价比贪心后，最终需要调整的部分很少。那么在此策略选 a 后一定会立刻选 b_i-a_i，因此组合成 \frac{b_i}{2} 性价比的物品。按照性价比排序后，考虑 \ge k 的最小前缀和，如果是 k 那么一定最优，否则是 k+1，只会删除已选重量为 1 的 \min(v_i) 或者删除重量为 2 的 \min b，并加入未选取中重量为 1 的最大收益的物品。这样容易对所有 k 求出答案。这个子问题只需要排序，可以 \mathcal O(m\log m)。

视 n,m 同阶，原问题容易做到时间复杂度 \mathcal O(n\log n)。