Beyond the Void

这道题描述的是我们玩过的经典的小游戏，推箱子。由于要求步数最少，基本的想法是BFS，记录人的位置和箱子的位置两个状态。但是状态数过多，有100*100*100*100，进一步思考可以发现记录人的绝对位置是没有必要的，因为只有人在箱子旁边的单元格内，才能推箱子，所以只需记录箱子的位置和人在箱子的方向，只有100*100*4个状态。

BFS过程中，状态扩展分类两种情况，一种是向前推箱子，步数要加1，另一种是改变人的方向。推箱子只需判断前面的位置是否是空地，如果是障碍则不能继续扩展。改变人的方向就有些复杂了，假设箱子的位置是(x0,y0)，人原来的位置是(x1,y1)，新的位置是(x2,y2)，则要判断(x1,y1)到(x2,y2)是否存在不经过(x0,y0)的路径。简单的想法是floodfill，时间复杂度为O(NM)。注意状态判重，还有就是初始位置的确定。由于人初始不一定在箱子边，需要floodfill一下，求出人能到达的箱子旁边的位置，如果根本不能到达，显然无解。

按这种想法写出的程序是要超时的，加上些例如我们在玩推箱子的时候不能把箱子推到墙角之类无关紧要的优化，还是无法通过。思考算法的主要瓶颈就在于判断改变方向时每次都要floodfill一遍，如果能把这里优化一下，或许就能通过。

进一步思考，发现两地如果连通，必须至少存在一条路径，如果总是连通，必须至少存在两条路径。也就是说，无论箱子作为障碍挡在哪条路径上，总还有另一条路径使这两点连通。这恰好是图论中双连通分支(点双连通)的定义，即没有割点的连通分支。所以可以这样判断，对于一个连通图，如果箱子不在割点上，箱子旁边的两点(人的位置)一定连通，如果箱子在割点上，则人的两点位置是否连通，取决于两点是否同属一个双连通分支。于是我们可以预处理出图中的所有割点和双连通分支，然后每次判断两点连通只需O(1)的时间。这样就可以解决这道题了。
Read the rest of this entry »

发现坐标的范围很大，而点并不是很多，首先想到了离散化的方法。然后横向扫描每个带状的区间，对于每个带状区间，再纵向扫描其中点的个数。这种方法是最容易想到的，但是时间复杂度却高达O(N^2logN)。关键在于优化每次确定带状区间的纵向扫描。

显然对于确定的带状区间，我们扫描时只需考虑它们的纵坐标。如果我们把一个纵坐标为y的点描述成两个事件(y,1)和 (y+h+1,-1)，然后把所有事件按照第一关键字排序，定义S[i]为前i项事件的第二关键字之和，那么Max{S[i]}就是确定的带状区间内高度 为w的矩形最多覆盖到的点数。为什么是这样，我们可以想象有两个挡板，分别是y=A-h-1(下板)和y=A(上板)，从下向上移动挡板，从而确定一个矩 形。某个点的第一个事件为(y,1)，当上板A=y时，该点被覆盖，若A继续增大，使得A-h-1=y，该点就恰好离开了覆盖区域，反过来我们可以以为是 A=y+h+1，所以定义第二个事件为(y+h+1,-1)。这样，前i个事件的第二关键字和S[i]，就代表了矩形在某个位置时覆盖的点数。S[i]的 最大值就是确定的带状区间内最大的覆盖点数。

带状区间的左右扫描，也可以考虑成两个挡板之间的问题，首先确定挡板的初始位置在最左端，依次向右移动左右两个挡板。确定一个区间后，统 计点事件的最大前缀和成了最关键的问题。由于左右挡板是移动的，我们需要动态统计一个排序结构。于是我们想到了用平衡树，维护每个点事件的第一关键字(y 坐标)升序，并记录权。移动右挡板时，把右挡边新位置所在线上的所有点对应的两个点事件加入平衡树；移动左挡板时，把左挡板时，把左挡边所在线上的所有点 事件从平衡树中删除。

为了快速统计出最大的前缀和，在此基础上，我们还需要对于平衡树中每个节点维护其子树所有节点权值和，以及子树中最大的前缀和。定义p的权值为p.w，以节点p为根的子树的权值和为p.s，以节点p为根的子树的最大的前缀和为p.m，我们可以递推算出p.m的值。

p.m=Max{
	p.left.m; //最大前缀和的尾元素在左子树
	p.left.s+p.w; //最大前缀和的尾元素就是p
	p.left.s+p.w+p.right.m; //最大前缀和的尾元素在右子树
}

于是全部序列的最大前缀和就是根节点root.m。

于是得到的算法如下：

1. 建立离散化坐标系;
2. 左右扫描，确定带状区间，维护平衡树中节点;
3. 统计对于确定带状区间，平衡树中元素最大的前缀和;

算法总的时间复杂度为O(NlogN)，可以解决问题了。编程中细节要注意，尤其是在于平衡树维护平衡性时要对节点m值重新计算。我用了 Treap，在插入一个点要旋转时，注意要先重新计算旋转到子树的点的m值，再计算子树根节点的m值。而删除仅仅懒惰删除即可，重要的是维护m值。
Read the rest of this entry »

题上描述这种图是很特殊的，每个顶点只有一条指出去的有向边，而且一定存在一个环，哪怕是自环，从任意一个顶点出发，最终一定进入一个环。我们的任务的判断这样的两个图是否同构。

首先，这个图不一定是弱连通的，可能会有多个连通分量，我们需要考虑每个连通分量。每个连通分量中一定存在一个环，去掉环上的边以后，剩下 的是一个森林，每棵树都是内向树。实际上它是环状内向树森林。对于两个内向树，我们可以很容易地判断它们是否同构，于是我们有了解决问题的方法。

首先是两个内向树，如果它们同构，它们的括号序列一定相同，反之也成立。判断两个环状内向树森林同构，首先应该满足环的大小相同，如果两 个环的顶点数都不一样，那么它们一定不会同构。如果环大小相同，则需要枚举两个环上的对应点，然后判断以环上每个顶点为根的内向树是否都同构。用上述方法 可以判断两个连通分量是否同构，对于题中给的两个图，首先判断连通分量的个数是否相同，然后用搜索的方法确定一个对应关系，以此判断每个每对连通分量是否 同构。如果存在一种对应方案使得所有的连通分量通过，那么这两个图同构。

上述方法中，生成所有内向树括号序列需要O(N^2logN)时间(需要排序)，枚举每个环的对应关系需要O(N)，判断两个内向树括号 序列相同需要O(N)，枚举连通分量间的对应关系由于是搜索，尽管实际搜索的很少，但是从时间复杂度上分析仍然是O(N!)。每个文件有D个测试数据，于 是总的时间复杂度是O((N^2logN+N^2*N!)*D)。但是实际上这个时间复杂度由于全部从最坏情况考虑(实际上所有最坏的情况不可能同时达 到)，所以是相当悲观的估计。实际编程对于N<=2000，已经可以完全应付了。

在编程实现的时候，许多地方要用到链表，否则空间是不够用的。细节不容忽视。

关于内向树以及生成括号序列，请参看有向树与树的括号序列表示法。
Read the rest of this entry »

题目很长，题意简述可为给定一个动态图(边权随已知最短路径周期变化)，求从X到Y的最短路径。我们只需把换乘车等待的时间看作动态的边长度。

按照路径构造有向图，构图后用一般的最短路径算法(Dijkstra,SPFA)即可解决，关键在松弛边时计算动态的边权。对于每条有向 边，需要记录其长度len，所属的线路b，从线路起点到该边的起始端的距离前缀长度pre。在松弛时，已知当前最短路为S，该边前缀pre，该边所属线路 的周期C，边长len。则我们所需等车的最短时间T，如果(A-pre)能整除C，T=A-pre；如果(A-pre)不能整除C，T=((A- pre)/C+1)*C (/为整除)。动态的边权E=len+T，用动态E松弛即可。

Read the rest of this entry »

做出这道题关键在于读懂题目，尤其是第3条和第4条规则。可以知道，所有蚂蚁是一拥而上的，而且蚂蚁很聪明，它们知道如果在某时一只蚂蚁到瓢虫的路 径与另一只蚂蚁的路径相互包含，就让距离近的蚂蚁继续行进，另一只蚂蚁停留不动。蚂蚁们还会互相礼让，如果要同时进入一个节点，就让编号小的蚂蚁进入，其 它蚂蚁停止不再动。

瓢虫会停留在多个位置，但是都是互相不关联的，我们可以把瓢虫停留的每个位置看作独立的测试点，每个测试点要用到上个测试点的结果，所以我们可以分割考虑每次瓢虫停留。

对于每次瓢虫停留，如果简单地模拟，会很容易超时。我们要把每只蚂蚁一次移动到位。首先从瓢虫的位置开始一遍BFS，找到所有可行进的蚂 蚁，记录每只蚂蚁到瓢虫位置的路径。然后按照路径长度从小到大为第一关键字，蚂蚁编号从小到大为第二关键字把蚂蚁进行排序，排名第一的蚂蚁一定是可以驱逐 瓢虫的蚂蚁，把它的路径上的顶点分别标记时间。然后依次处理每只蚂蚁，如果某只蚂蚁路径上有节点已经被标记时间，则这只蚂蚁的最大移动时间就是已经标记的 时间。在移动时也标记时间，用于影响后面的蚂蚁。这样，移动所有蚂蚁的时间复杂度是O(N+K)的。

算法的总的时间复杂度为O((N+K*logK)*L)，可以很快解决问题。实际编写时有很多细节需要注意。
Read the rest of this entry »