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 …

hdu 1846 题目链接 题意：有n个石子，每次最多取m个，最少取１个，如果没有石子可取就输了。给出n,m，两个人都很聪明，问先手和后手谁赢。。 思路： 首先定义几个概念： p点：即必败点，某玩家位于此点，只要对方无失误，则必败 **　N点 ：即必胜点，某玩家位于此点，只要自己无失误，则必胜。** ** 一、 所有终结点都是必败点P（这道题目中，轮到谁取石子，还剩0个石子的时候，此人无石子可取，就输了）；** ** 二、所有一步能走到必败点P的就是N点；（这里是_存在一种_情况可以走到p点即可）** ** 三、通过一步操作只能到N点的就是P点；　（这里是_所有_的情况都只能走到n点）** 那么当m=3的时候，则有：  x ：0 1 …

http://codeforces.com/contest/604/problem/E 题意：有两个人做游戏，游戏规则如下： 有n堆石子，每次可以对一堆石子进行操作，如果当前石子是偶数，那么可以选择将这2*x个石子分成k堆石子数为x的石子堆，还有一种没有前提的操作是取走当前堆的一个石子，问先手赢还是后手赢，先手和后手都足够聪明的情况下。 思路：博弈论。。不会做。。第一次接触sg函数。。转载一篇题解： http://m.blog.csdn.net/blog/qq_24451605/50154973 /* *********************************************** Author :111qqz …

Rabbit and Grass **Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3058 Accepted Submission(s): 2261 ** Problem Description 大学时光是浪漫的，女生是浪漫的，圣诞更是浪漫的，但是Rabbit和Grass这两个大学女生在今年的圣诞节却表现得一点都不浪漫：不去逛商场，不去逛公园，不去和AC男约会，两个人竟然猫在寝食下棋…… 说是下棋，其实只是一个简单的小游戏而已，游戏的规则是这样的： 1、棋盘包含1*n个方格， …

hdu 2149题目链接 题意＆思路：巴什博奕，点m是n点。。。然后往前画即可。。。 /************************************************************************* > File Name: code/hdu/2149.cpp > Author: 111qqz > Email: rkz2013@126.com > Created Time: 2015年09月22日 星期二 20时18分02秒 ************************************************************************/ …