2020.5.9 CTU Open Contest 2016 prob:5/6/10 rank:5/89

Tarjan

陶吟翔：Codeforces641Div2-E，题目大意是有一个$n \times m (n,m \le 500)$的矩阵，每个格子要么是黑色要么是白色。现在在每一轮里，如果与一个格子相邻的四个格子都与这个格子颜色不相同，那么下一轮这个格子的颜色就不会改变，否则这个格子的颜色就会从黑变白或从白变黑。有$T(T \le 10^6)$个询问，每次询问格子$(i,j)$在第$p$轮的颜色。乍一看会想找循环节，但是仔细分析会发现如果一个格子的颜色会变，那么说明有和它相邻的格子和它颜色一样，那么那个格子也会变，这说明某一个格子一旦会发生变化，一定是黑白交替。然后就是变化是会传递的，就是说一个点如果一开始不会发生变化，但是它旁边的点会变化，那么下一轮它就会开始变化。所以我们找到一开始会变得点，然后从它们开始BFS处理出每个点会开始发生变化得轮数，在根据这个信息来判断某一个点在某轮式什么颜色。由于一个点最多入队一次出对一次，询问复杂度$O(1)$，总时间复杂度$O(nm+T)$，这里是网址。

郭衍培：