level 12
274C - The Last Hole!
Coming soon soon soon!(原文)
(等这题题解出来麻烦at我来补上)
274D - Lovely Matrix
比较主流的想法是每个列抽象成一个点，然后根据每行的信息建图，最后拓扑排序。
在1 1 1 1 2 2 2 2这种极端情况，边数是O(nm^2)的，需要减少边数。
可以采取加点的方式，对于一串连续的相同的数，新增一个点，所有的数都向这个点连边，然后再从这个新点往后连边，理解不能的去读程序。
另一个想法是，对于每行，我们标记下最小的不是-1的元素(可能有多个，全部标记上)。
则新矩阵的第一列，应该是所有不是-1的元素都被标记了的那一列。剩下的列类似逐步确定，一旦某一步找不到符合要求的列去安排则无解。
274E - Mirror Room
//这题比赛的时候暴力可以过，因为随机数据出来的数据太弱了卡不掉，@liouzhou_101最先在comment里指出了这一点。数据已经被加强了。
比较显而易见的，激光最终一定会回到开始时的状态(位置和方向)，我们将证明回到初始状态前反射的次数是O(n+m+k)的。
考虑一个没有障碍的格子，他最多有O(n+m)个"空的对角线方向上的线段"。当我们把某个格子设置成障碍之后，这个数量最多增加了2。
这就证明了"空的对角线方向上的线段"的个数是O(n+m+k)的；再考察激光的行为，他永远走在这些线段上，于是结论得证。
于是我们可以模拟了，实现"已知当前状态，求下一次反射发生的位置"就行。
现在我们来证明不会有一个格子被经过两次(这里经过两次被定义为在两个对角线方向上都被经过)。
上一个结论的证明中我们提到了"空的对角线方向上的线段"，依据方向我们可以把他们分为两类(属性1)；
此外，如果把整个网格像国际棋盘那样黑白染色，这些线段还可以根据其所经过的格子的颜色分为两类(属性2)。
显然每次反射(这里所说的反射不包括原路返回的情形)前后，激光所在的线段的两种属性都要改变，从而在确定了初始状态后，这两种属性可以相互推出。
于是对于一个被染了黑色的格子，经过这个格子的时候属性2被固定了，属性1也就固定了；白格子也类似，这就证明了结论。
从而这个问题可以在O((n+m+k)lgk)的时间内解决，如果假定每步模拟是O(lgk)的话。
2013年02月23日 05点02分
