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 …

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

cf689C 题意：给出一个m。。问恰好使得不超过某个n的a*b^3（a,b是正整数）的方案数为m的n是多少。。。 思路：暴力+二分。。。 /* *********************************************** Author :111qqz Created Time :2016年07月18日 星期一 15时58分55秒 File Name :code/2016whust/G.cpp ************************************************ */ #include <cstdio> #include <cstring> #include …

cf689B题目链接 题意：n点。。点i到点j的代价是|i-j|..给出n条近路。。。a[i]表示点i到a[i]的代价为1（注意近路不一定就近） 思路：一开始建边卡了一下。。。实际上只要连相邻的就好了。。。然后边表只开了2N蠢哭。。。实际上应该3M...因为连相邻的边是双向的。。。再加上近路的单向。。。然后spfa就好了。。。。 /* *********************************************** Author :111qqz Created Time :2016年07月18日 星期一 13时33分18秒 File Name :code/2016whust/F.cpp …