AC. 梦想

frank_c1

[ZJOI 2014] 消棋子

发布于2017年03月01日 | 暂无评论 | 365阅读 | 搜索

题意简述

有一个r \times c的棋盘和n种颜色的棋子,每种颜色各两枚。

棋盘中一个格子可能为空,也可能有恰好一枚棋子。

你可以执行一种消棋子的操作:选定一个空格子和两个平行于坐标轴的方向,如果这个格子在这两个方向上第一个遇到的棋子是同种颜色的棋子,则这两个棋子可以同时被消除。

给定棋盘的初始布局,现在你需要完成两个任务:

1. 给定一段消棋子的操作,求消去了多少对棋子。注意,不合法的操作将不会被执行。

2. 求在这个布局下最多能消除多少棋子。

1 \le r, c, n \le 10 ^ 5

算法讨论

对于第一问,我还是觉得这是为了给选手写对拍提前作准备233

第一问的话我们可以对于每个横坐标和纵坐标维护一个set,这样我们就可以支持快速查询在某一条线上的前驱和后继了。

考虑第二问。我们发现这有点像一个有向图的模型,棋子之间存在依赖关系。

我们消棋子的过程就像是在拓扑排序。但是这张图的连边是怎样的呢?

不妨考虑一个棋子消除的影响。注意到它的消失仅可能对当前4个方向上距离它最近的棋子产生影响,令这些棋子变成可消除的状态。一个点的度数是O(1)的,所以点数和边数都是O(n)的。

于是算法的框架就很明显了。我们从已经可以消除的棋子开始DFS,每消除一对就检查满足上述条件的棋子对是否已经可消除,如果可消除了就DFS过去。是否可消除的判断和第一问类似用set即可完成。

时间复杂度O(n \log n)