上上周做过的题目，1067 和 1024

最近实在太忙，项目里面的一个BUG经常要解很长时间，而且环境也比较恶劣。又有很多自己不能掌控的事情。所以最近也没有做题目。
上次的题目是PKU 1067，一个博弈方面的题目，题目很有意思。记录一下我的思路：
首先题目有一个很大的提示就是棋局都是可解的（就是对于一个棋局，谁会赢是确定的）。首先很容易找到一些必赢的棋局，比如：(1,2), (3,5)(4,7).看看是否有什么规律。对于当前棋局，总能找到一个下法，是的对手无论如何下棋，我都是能赢（递归），或者是，当前棋局，无论如何下棋，对手都能找到下法能赢。

不过规律似乎不是那么容易找到，但是从题目的规则上，容易找到一个筛选算法（带一点贪心性质）。从首先，定义函数 F(a, b）为棋局的胜负(1胜0负，这个胜负代表一种必胜和必负）， C(a, b)为一个规则下法所导致的棋局的集合，比如C(1, 2)就有: (1 , 1), (0, 1), (0, 2), (0, 0)...等（规则就是题目里面的一次只能取一边的任何数目，或者两边都取相同的数目）。那么对于个棋局 (a, b), 通过规则反推， 有：

F(a,b) = 0, 则F(a + x, b + x) = 1
F(a,b) = 0, 则F(a + x, b) = 1
F(a,b) = 0, 则F(a , b + x) = 1

于是：从F(0, 0)为输，那么F(0, 1), F(0, 2),...F( 1, 1), F(2, 2)....F(1, 0), F(2, 0)为赢（显然）。
那么是否可以找到下一个输F(a, b), 是不是把这些筛了下一个就是呢，的确，容易证明：
因为下一个（定义下一个为，b + 1，因为一次筛选肯定能筛掉所有当前行, a 从左到右选择第一个空白）因为下一个F(a,b),通过规则下法，（无论如何，不能不下）， 所以任何 F(c <= a, d <= b) 的棋局是在晒选过得集合里面。F(a,b),通过规则下法，（无论如何，不能不下）， 所以任何 F(c <= a, d <= b) 的棋局是在晒选过得集合里面。这里化个图是很简单的： 这图就是每次筛选用的不同颜色。
因此，如果范围不大，用这个筛选法就能得到结果，可是，这些必胜棋局确实有规律的，我只找到他们的口每次+1，我可怜的思路到此为止，题目中的范围很大，必须找到规律。
后来GOOGLE了，实在想不到了，这个题目的原本就是一个博弈问题，叫做Wythoff 博弈。必胜棋局是有一个通项公式的，BT...

A_n = floor(nP) and B_n = floor(nP) + n, where P = (1+sqrt(5))/2(黄金分割)

好了，到这一步，代码也没什么了。。。


第二题是PKU 1024. 是一个怪绕人的题目，通过迷宫路线求迷宫和多余墙壁。我没想到那个广搜+逐个移去墙壁也能AC。。。
其实我也有一个深搜的版本，深搜的版本预料之中是TLE, 广搜要好很多。，不过可能题目的数据量不大，本来在求墙壁多余的时候，是因该维护一个可“回朔”的队列要好些，因为一个墙壁在广搜的过程中，蔓延到他之前的搜索都是不变的，如果把它移去的话，那么这些层次的数据是应该保留，只用从考虑它开始的那一层广搜开始就行了。另外，有些墙壁天然就是有用的，比如双面路线的，就是不用搜索就可以剔除。不过这些我都没写，就写了个简单的直接搜，竟然AC了，而且16MS还挺快的。。。可能前面有个简单的优化其了一点左右，就是路径的合并，因为题目要求唯一路线，普通广搜只能搜出一条最佳路线，如果要求解所有路线，可能要对兄弟节点都展开，但是实际上可以吧兄弟合并，加入一个ENTER计数,这样就不用重复考虑兄弟又不失路径是否唯一的标志，丢失的只是路径本身（这个信息是不需要的。嘿嘿）。这个题目比较顺利，不若第一个题目那么BT。。