上上周做过的题目，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。。

合肥 家乐福

周五下班回家的时候，大概七八点的样子，801路车到青阳路突然改道转金寨路。长江路三里庵段有很多警车。原来是预料之中的抵制家乐福示威活动正式开始了。
星期天接待一个很久没来的朋友，路过长江路，突然一大群人打着标语，喊着口号沿路冲了过去。

以上是我知道的所有的关于合肥家乐福抵制活动的记录。

后来上网，发现合肥的抵制游行活动，无论规模还是影响力，遥遥领先于其他城市。

在此表达一下我的心愿。

尊重自己的同胞，尊重别人的爱国方式，无论形式上还是内容上。请千万不要把拳头挥向自己的同胞，谣言自然不攻自破，但是也要注意若干脑子进水，或者天生暴力倾向，或者别有用心的人。言论自由，不仅仅是对zf的要求，也是对我们自己的要求，当一群人拥有了人数优势，和zf一样，就拥有了一定的暴力，所谓道德制高点的优势，这个时候如果言论的自由被凶恶的打压，和所谓zf的打压没有任何的区别，还显得更加卑劣。

不要沉溺这种大规模活动的表面强势，这毕竟是弱者展示强势的最后手段。做好自己，多多思考，文化，价值观的强势，才是真正的强大。为什么外国的媒体可以侮辱我们，而我们却不能发出自己的声音，为什么外国人看到照片上有坦克和人就会激动。为什么Made in china被外国人肆意歪曲，为什么那么多的科研作假。。。中国的未来，不仅仅是奥运!

好用不经用 ，EG.

上上个星期买了一块EG, 正反狂3. 一个星期就适应了，比OC更适合我。 但是，今天重新刷一遍胶水，面材就脱落了一小块。。。。 真不经用。郁闷。

Blogger里面插代码

Blogger的HTML编辑器插入C代码比较麻烦,得加一个pre，但是pre也不太方便。真是的。不知道有什么好的办法。直接从本地编辑器复制出来的代码粘贴到Blogger就乱七八糟的，自作主张的做了各种排版。不知道在哪里去调整。 晚上去和表弟喝酒，这次的做题先就不写了，和下次的题目一起写。 唉，周末真无聊，自从英超被买断，再也没看过英超，意甲周末也是不一定有，西甲太晚，看球是没什么指望了。要不再去打大波罗？以前在学校是联机玩，单机我玩了一个死灵，到地狱打不动了，全招的，累死了。去玩个法师好了。

北京奥运

本来我对北京奥运没什么特别的感觉。但是最近的关于奥运的事件，打上ZD事件的烙印，觉得奥运对于中国，开始有了某种特殊的意义。这次ZD事件和奥运的风波，在中国，无论各方都在重新思考，世界和中国。

真的没玩够

我最不后悔的事情，和某些人比较，就是在大学的时候选择的是玩的路线，嘿嘿。真的很开心，现在工作了才觉得好明智，如果大学没玩，工作后就没有什么玩的意思了。 很庆幸的是，我到大学之后，电脑已经开始普及，高中的时候电脑游戏就开始兴起，不过大学之后，游戏更呈“专业化”发展。所以，玩的主题基本就是游戏了。其他的，于前辈人共有的比如喝酒唱歌之类，自然不在话下。无论何时，总能找到一帮子人，和你玩。大学三个班，第一年和三班玩，第二年和一班玩，第三年和一班玩，第四年和二班玩。 工作后，身边的朋友逐渐远走了，也没人可以玩了。生活真的黯淡了很多，也许有些人会说，玩够了，该干正经的了，或者说，年纪不小了，该收了。可是我怎么总是觉得没有玩够啊，现在每天没有人一起玩游戏，的确没什么时间，可是觉得现在这样是在浪费生命。 每天回去我都只能在cs,sc两个老游戏里面殴电脑，把他们想像成曾经的同学。。。 。。。 生命在于玩乐。

第三题很失败，1015。

妈的， space速度还真不是一般的慢，还是用我的blogspot好了，虽然国内无法访问。 这周做个题目不顺，就是那个1015,陪审团问题。虽然有个思路，但是因为实在没有时间去做，没有提交，因为老是没作对。 思路是类似动态规划。貌似不能叫做动态规划来解的题，因为题目的最优解并不是通过求解相同最优子结构来做的，而是通过相同子结构迭代求一系列解来做。求和问题和01背包很类似，有大量同子问题。通过增长决策的源数据下标，增长求和个数（<=20），不断求得一个范围内的和数问题。然后选择最优的。因为没有用去尝试这个解法（空间复杂度比较高，而且用C写，存路径很麻烦的，debug也要费不少时间），所以不敢保证是对的，也不想再纠缠下去。 Bs自己。 后来在《算法导论》的NP完全问题的近似解法中也看到一个类似的算法求子集和数的问题（不过这个和数是固定的，子结构中超过这个和数就可以cut掉，解法没什么，但是那个通过归并排序来求下个决策下标的和数比较不错），书上没说这个是属于动态规划，俺也不敢说。虽然真的和动态规划很像。