第四题: 对于每枚棋子它最终所在列只和它初始所在列、左右操作有关;它最终所在行只和它初始所在行、上下操作有关。于是将上下操作抽取出来、左右操作抽取出来分开处理。 求列的值(只考虑左右操作): 记"左" 对答案的影响为 -1 记"右" 对答案的影响为 1 然后遍历所有的左右操作,对操作统计一个前缀和sum。如果第 i 列+ sum < 1,那么它的结果将和第 i+1列相同,并查集合并第 i 列和第 i +1 列(将第 i 列合并到第 i+1 列);如果第 i 列 + sum >Y,那么它的结果将和第 i-1列相同,并查集合并第 i列和第 i-1列(将第 i 列合并到第 i-1 列)。那么第 i 列最后的结果就是它的祖先初始所在列+sum(祖先没有被合并,说明祖先并不会“碰壁”)。 特殊情况:合并到只剩一个列了,说明所有列的结果都相同,直接暴力模拟一遍左右操作对该列的影响即可。 求行的值同上。

相关推荐

牛客网
牛客企业服务