雅礼国庆集训 day1 T3 画作
题面
题目下载
算法
猜测最优解是
每一次染色都是之前染色的子集且颜色相反(证明不会)
所以可以逆向思维(注意直接逆向不成立)
最后一次染色一定在一个四连通块中, 之前的染色一定是后一次染色的超集
把每个颜色的连通块缩点, 例如
每次将一个点(即原图中的连通块)染色成反色, 相当于加入了与之连接的反色连通块, 变成了一个新的点, 也就是图上的边
于是对于每一个点, bfs求其到最远点的最短路径长度即为答案
时间复杂度 \(O(r^2 c^2)\)
代码
一会打
总结
结论题猜测大法
注意染色, 四连通块问题一般可以建模成图, 然后在处理