Abstract
Codeforces 105D
并查集(官方标的)
Body
Source
Description
题意很复杂,自己看……我一开始也没看懂,把那个gif动态图看个10遍以上就懂了。
Solution
比较裸的并查集。注意到染色操作实际上就是将原本颜色不同的格子合并到一起即可。计算螺旋形距离的话,实际上只跟格子相对中心格的坐标有关。我是直接找公式,CF上面的代码好像大部分是直接记录,各种step++什么的,看不懂。
但是仔细分析后我觉得,其实和并查集没有什么关系……令当前需要染色的格子集合为S。可以证明,实际上每次染色只会把别的格子并入S,而不会从S中删除或换掉格子(尽管S的颜色不断改变)。于是只用记录S的颜色和大小即可。
P.S. 写得这么简陋还叫解题报告实在是太不好意思了,以后标签改成[代码]好了。
Code
并查集(我写的并查集很长很难看,大家还是看CF上面的代码好了)
#include #include #include #include #include #include #include #include
非并查集
#include #include #include #include #include #include #include #include