一眼可以看出一个 \(\Theta(n^3)\) 的 DP。其实用双带权二分就可以用 \(\Theta(n \log^2 n)\) 的时间搞了，但是我没写这个写法。
考虑一下被选择时的贡献。\(p_a, p_b\) 是单元贡献，考虑同时被选的贡献 \(1 – (1 – p_a)(1 – p_b) = p_a + p_b – p_a p_b\)。所以我们可以考虑最大费用最大流，来算这个式子。
需要注意的是，我们需要保证每一次代价都是正的，因为我们其实并不需要最大流，而只是相对的最大费用。
Continue reading →
一道比较板的上下界网络流。先考虑 \( red > blue \) 的情况，我们把所有点染成红色的然后再做个最大替换即可。我们考虑对每个点、每个横坐标、每个纵坐标做一个点，横坐标和源点、纵坐标和汇点的边需要大概算一下，得出流量范围 \(\frac{cnt_x}{2} \leq flow \leq \frac{d + cnt_x}{2}\)。得出这个范围之后就用板子套一下即可。
如果本身就不是回文串，那么答案就是 \(1\)；如果本身是的话，考虑找一个分割点使得左右都不是，那么答案就是 \(2\)；如果还是没找到，那么就是无解了，因为最后串要么就是个单纯串或者是个删完一次之后变成单纯串的东西。
这道题乍一看不是很能做，因为摆放状态很多。然而，计算机科学这种东西解决不了问题的时候不讲究正解，只讲究近似。所以，我们可以枚举一个旋转角 \(\theta\) 来决定最终摆放的形态。枚举之后就可以直接二分费用并建边做二分图。
忘了写题解，但总觉得要写点啥，所以就有了这篇题集。