2463: [中山市选2009]谁能赢呢？ Time Limit: 10 Sec Memory Limit: 128 MB Submit: 1826 Solved: 1347 [Submit][Status][Discuss] Description 小明和小红经常玩一个博弈游戏。给定一个n×n的棋盘，一个石头被放在棋盘的左上角。他们轮流移动石头。每一回合，选手只能把石头向上，下，左，右四个方向移动一格，并且要求移动到的格子之前不能被访问过。谁不能移动石头了就算输。假如小明先移动石头，而且两个选手都以最优策略走步，问最后谁能赢？ Input 输入文件有多组数据。 输入第一行包含一个整数n，表示棋盘的规模。 当输入n为0时，表示输入结 …

1874: [BeiJing2009 WinterCamp]取石子游戏 Time Limit: 5 Sec Memory Limit: 162 MB Submit: 726 Solved: 296 [Submit][Status][Discuss] Description 小H和小Z正在玩一个取石子游戏。 取石子游戏的规则是这样的，每个人每次可以从一堆石子中取出若干个石子，每次取石子的个数有限制，谁不能取石子时就会输掉游戏。 小H先进行操作，他想问你他是否有必胜策略，如果有，第一步如何取石子。 Input 输入文件的第一行为石子的堆数N 接下来N行，每行一个数Ai，表示每堆石子的个数 接下来一行为每次取石子个数的种类数M 接下来M …

hdu 3980 题目链接 题意：一个有n个石子的环形串，初始没有被涂颜色，两个人轮流，涂连续m个没有被涂色的石子，不能操作的人为负。问先手是否有必赢策略。 思路：和hdu2999很像。。所不同的是。。。那道题是线型的珠子。。。这道题是环型的数字。。。 然而我们机智得发现。。。环形的任意涂一次。。就变成了线型的啊orz。。。 所以先随便取一次，然后剩下的n-m个按照线型串的方法搞，划分区间即可。 由于先随便取了一次，所以和线型的交换输赢的结论。。。 以及。。要特判一次都不能取的情况。。。2A /* *********************************************** Author :111qqz …

hdu2999题目链接 题意：有一串石子，给定一个集合S，每次只能拿连续x个石子，石子必须是在集合S中的数，问先手是否有必赢策略。需要注意石子的位置是不能变化的，也就是说如果一串连续的石子因为中间有石子被取走，那么这段石子就变成不连续的了，也就不能一次取走。 思路：一开始没有读懂题。需要特别强调的是。石子的位置是不能合并的。。 举个例子，如果我有5个石子，S={2},那么我取完一次剩下的情况是 {3,4,5}或者{1},{4,5}或者{1,2},{5}或者{1,2,3} 一共四种。 题意搞清楚以后就好做了。。类似于bomb game那道题。。我们仍然可以把取一次的操作拆分两个子过程，也就是两个区间。我们不关心区间具体的情况，只关心区 …

hdu 2873题目链接 题意：n*m个格子，有若干炸弹。对于在第一行或者第一列的炸弹，爆炸后会到那一行或者那一列的更前面（总的来说就是更靠近左上角）的位置。对于其他位置的炸弹，爆炸后会生成两个炸弹，分别到那一行的更前面或者那 一列的更前面。问先手是否有必赢策略。 思路： 不会做2333 参考了 参考博客1 参考博客2 大概明白了一点。整个游戏可以分为若干个炸弹的游戏的和，而实际上一个不在边界行或者列的炸弹，依然可以继续分，分成两个炸弹的和。而位于(i.j)的炸弹，分成两个炸弹的和，有(i-1)*(j-1)种方案（这个不重要2333） 处于边界行或者列的点的sg值我们是可以知道的。。因为规则单一。。和移动等价。。 然后根据边界来进一 …

hdu2509题目链接 题意：？？？ 思路：同1907 /* *********************************************** Author :111qqz Created Time :2016年07月23日 星期六 04时41分38秒 File Name :code/hdu/2509.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> …

hdu1907题目链接 题意：n堆石子，每次选一堆，最少拿一个，最多拿光那一堆，拿走最有一个的人输。 问是否有必胜策略。 思路：anti-nim问题。。。 要用到sj定理（是啥。。。?) 参考资料：参考博客 SJ定理 **对于任意一个Anti-SG游戏，如果定义所有子游戏的SG值为0时游戏结束，先手必胜的条件： ** **1、游戏的SG值为0且所有子游戏SG值均不超过1。 ** 2、游戏的SG值不为0且至少一个子游戏SG值超过1。 /* *********************************************** Author :111qqz Created Time :2016年07月22日 星期五 23 …

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 …

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 …