hdu 1730 题意：n行格子，每行m个，每行有一黑一白两个棋子，给定初始位置，先手执黑棋，后手执白棋，每次可以在同一行内向左移动，不能超过边界，且不能越过对方的棋子，同一个格子只能有一个棋子。问先手是否必赢。 思路：可以看成n个独立的游戏的 叠加。。。所以最后异或和一下就好。。 我们来求sg函数。。。一开始的是想把点对hash成一个数。。。然后发现其实没必要。。。直接二维就好了。。 由于初始化的时候要考虑最大。。。所以sg函数的值会有一个便宜。。。和设定N有关。。减去偏移就好了。。。（我的代码里这个偏移是11026） 1A蛤蛤蛤 /* *********************************************** …

hdu 1404题目链接 题意：一个数字串，每次可以选择一位减少任意大小到一个非负数，或者清除一个0以及该位右边的所有数字。问是否有必胜策略。。 思路：定义来搞。。所有能一步走到p点的都是n点，那么如果我们现在知道p点，就可以反过来推n点。。 看到一些人强行把变量名起成sg就说自己用了sg函数也是笑死我了呵呵呵呵 /* *********************************************** Author :111qqz Created Time :2016年07月22日 星期五 19时11分16秒 File Name :code/hdu/1404.cpp …

终于忍不了因为没办法科学上网而不能做什么事的感觉了。。。 买了班瓦工 20刀/年。。。搭了ss。。然后全平台（ios/androd/fedora/win）的上网问题就全解决了。。。 网速似乎很快。。。youtube 1080p好无压力，虽然我不看2333

hdu 1536题目链接 题意：还是若干堆石子，但是每次取的个数只能是集合S中有的数。。问是否必赢。。。 思路：sg函数。。。1A /* *********************************************** Author :111qqz Created Time :2016年07月20日 星期三 23时32分48秒 File Name :code/hdu/1536.cpp ************************************************ */ #include <cstdio> #include <cstring> #include …

hdu 1517 题目链接 题意：初始为1，每次可以乘2..9中的一个数，最先达到或者超过n的人胜利。问谁有必赢策略。。 思路：一开始想用sg函数。。然而n太大（4e10）。。。绝对会超时。。。 所以可以更朴素得，去画n点和p点。。。我们可以发现。。。连续一段的局势是相同的。。。所以不能，也没必要找到每一个点对应的局势。 [n,+oo]是p点，那么[n/9,n-1]是n点，那么[n/9/2,n/9)又是p点。。。以此类推。。 这道题同时也告诉我们。。。没有什么方法是万能的。。。就算sg函数很神。。也有不能用的时候。。。所以掌握最本质的东西还是很重要的。。。 转载一段题解： **** 这道题如果用sg函数，利用点的局势做一定会超时，因 …

hdu 1848题目链接 题意：三堆石头，每次任选一堆取，取的石子数目必须是斐波那契数列中的数(1,2,3,5,8....)问先手是否有必赢策略。 思路：sg函数即可。。。。这次sg函数的优越性终于体现出来了。。。其他方法估计很难写吧。。 以及，这道题不知道为什么让我联想到了生成函数。。。感觉生成函数和sg函数作为工具还是有不少共同点的。。。 /* *********************************************** Author :111qqz Created Time :2016年07月20日 星期三 20时08分38秒 File Name :code/hdu/1848.cpp …

hdu1850题目链接 题意：n堆石子。。每堆可以取任意多个。。。先取完的赢。。问先手能否赢。。能赢的话第一步有几种取法。。 思路：sg函数。。对于方案数，可以用nim游戏的结论。 。设异或和为sum..那么统计满足 a[i]^sum<a[i]的个数就是第一步能走的方案数。 以及。。sg函数。。如果走的步数是任意的。。也就是没有限制。。。那么sg[i] = i...此时也就退化成了一般的nim游戏。。。 /* *********************************************** Author :111qqz Created Time :2016年07月20日 星期三 19时47分48秒 File …

hdu1847题目链接 题意：n个石子，每次只能取2的幂次个。。。问先手是否有必赢策略。。。 思路：画n点p点。。。发现n为３的倍数的时候先手必输。。。否则先手必赢。。。 /* *********************************************** Author :111qqz Created Time :2016年07月20日 星期三 18时54分46秒 File Name :code/hdu/1847.cpp ************************************************ */ #include <cstdio> #include …

参考资料　（后面的证明写错了，差评，不要看，看图就好了） 1. 题目1：今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根， 可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。 题目2：今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根， 可将一堆全取走，但不可不取，最后取完者为负，求必胜的方法。 嘿嘿，这个游戏我早就见识过了。小时候用珠算玩这个游戏：第一档拨一个，第二档拨两个，依次直到第五档拨五个。然后两个人就轮流再把棋子拨下来，谁要是最后一个拨谁就赢。有一次暑假看见两个小孩子在玩这个游戏，我就在想有没有一个定论呢。下面就来试着证明一下吧 先解决第一个问题吧。 定义：若所有火柴数异或为0，则该状 …

hdu 2147 题目链接 题意：一个n*m的方格，有一个棋子初始在右上角（１，m）,每次可以将棋子向下或者向左或者向左下移动**一个格子，**不能移出边界，当无路可走的时候就输了，问谁存在必赢策略。 思路：画n点p点。。。左下肯定是p　然后最后发现　n%2==1&&m%2==1的时候必输，否则必赢。 然后因为把m%2谢成名m&2 WA了好多发呵呵呵呵呵呵。 /* *********************************************** Author :111qqz Created Time :2016年07月19日 星期二 20时09分37秒 File Name …