算法

博弈类型的题
这个题属于最优解法的问题
最初可以看出 \(\rm{yy}\) 交换的列一定是一黑一白的, 不然无意义
考虑 \(\rm{youyou}\) 怎么选
对于两个都是黑的情况, 显然是都要选的, 这种贡献 yy 影响不了
对于两个都是白的情况, 显然是只选一个, 最大化贡献
对于一白一黑的情况, 有以下两种情况

• 选两个
• 选一个黑

对于选两个, \(\rm{yy}\) 无事可做
对于选一个黑, \(\rm{yy}\) 显然可通过交换使贡献 \(-2\)

那么考虑两种情况分讨
对于所有一黑一白都选, 那么答案是显然可以 \(O(n)\) 根据连通性求最优

对于选一个黑, 这里有一个 \(\rm{trick}\)