Beyond the Void

发现坐标的范围很大，而点并不是很多，首先想到了离散化的方法。然后横向扫描每个带状的区间，对于每个带状区间，再纵向扫描其中点的个数。这种方法是最容易想到的，但是时间复杂度却高达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 »

把每个政党的两个议员看作两个顶点，不能相处的议员之间连接一条边。类似于二分图的染色，但又不是严格的二分图。我们规定第2*i-1和2*i个顶 点为姊妹顶点。对于图中的每个连通分量，尝试从首个顶点开始访问染色，规定其加入理事会，然后访问该顶点的邻接顶点的姊妹顶点。遍历中如果发现了一对姊妹 顶点都被加入了理事会，则是不合法的，染色失败。如果染色成功，继续查找下一个连通分量，否则重新尝试从首个顶点的姊妹顶点开始访问染色，如果染色成功， 继续查找下一个连通分量，否则染色失败，不可能组建理事会。

该算法巧妙的类比了二分图染色，并根据该题的特点，设计出合适的方案，时间复杂度为O(M)。
Read the rest of this entry »