SG函数

Game of CS(LightOJ-1355) 题面 Jolly and Emily are two bees studying in Computer Science. Unlike other bees they are fond of playing two-player games. They used to play Tic-tac-toe, Chess etc. But now since they are in CS they invented a new game that definitely requires some knowledge of computer science. Initially they draw a random rooted tree (a connected graph with no cycles) in a paper which consists of n nodes, where the nodes are numbered from 0 to n-1 and 0 is the root, and the edges are weighted. Initially all the edges are unmarked. And an edge weigh w, has w identical units. ...

Paint Chain(HDU-3980) 题面 Aekdycoin and abcdxyzk are playing a game. They get a circle chain with some beads. Initially none of the beads is painted. They take turns to paint the chain. In Each turn one player must paint a unpainted beads. Whoever is unable to paint in his turn lose the game. Aekdycoin will take the first move. Now, they thought this game is too simple, and they want to change some rules. In each turn one player must select a certain number of consecutive unpainted beads to paint. The other rules is The same as the original. Who will win under the rules ?You may assume that both of them are so clever. ...

Partitioning Game(LightOJ-1199) 题面 Alice and Bob are playing a strange game. The rules of the game are: Initially there are n piles. A pile is formed by some cells. Alice starts the game and they alternate turns. In each tern a player can pick any pile and divide it into two unequal piles. If a player cannot do so, he/she loses the game. Now you are given the number of cells in each of the piles, you have to find the winner of the game if both of them play optimally. ...

S-Nim(POJ-2960) 题面 Arthur and his sister Caroll have been playing a game called Nim for some time now. Nim is played as follows: The starting position has a number of heaps, all containing some, not necessarily equal, number of beads. The players take turns chosing a heap and removing a positive number of beads from it. The first player not able to make a move, loses. Arthur and Caroll really enjoyed playing this simple game until they recently learned an easy way to always be able to find the best move: ...

A Chess Game(POJ-2425) 题面 Let’s design a new chess game. There are N positions to hold M chesses in this game. Multiple chesses can be located in the same position. The positions are constituted as a topological graph, i.e. there are directed edges connecting some positions, and no cycle exists. Two players you and I move chesses alternately. In each turn the player should move only one chess from the current position to one of its out-positions along an edge. The game does not end, until one of the players cannot move chess any more. If you cannot move any chess in your turn, you lose. Otherwise, if the misfortune falls on me… I will disturb the chesses and play it again. ...

Fibonacci again and again(HDU-1848) 题面 任何一个大学生对菲波那契数列(Fibonacci numbers)应该都不会陌生，它是这样定义的： F(1)=1; F(2)=2; F(n)=F(n-1)+F(n-2)(n>=3); 所以，1,2,3,5,8,13……就是菲波那契数列。 在HDOJ上有不少相关的题目，比如1005 Fibonacci again就是曾经的浙江省赛题。 今天，又一个关于Fibonacci的题目出现了，它是一个小游戏，定义如下： 1、 这是一个二人游戏; 2、 一共有3堆石子，数量分别是m, n, p个； 3、 两人轮流走; 4、 每走一步可以选择任意一堆石子，然后取走f个； 5、 f只能是菲波那契数列中的元素（即每次只能取1，2，3，5，8…等数量）； 6、 最先取光所有石子的人为胜者； ...

Nim(POJ-2068) 题面 Let’s play a traditional game Nim. You and I are seated across a table and we have a hundred stones on the table (we know the number of stones exactly). We play in turn and at each turn, you or I can remove on to four stones from the heap. You play first and the one who removed the last stone loses. In this game, you have a winning strategy. To see this, you first remove four stones and leave 96 stones. No matter how I play, I will end up with leaving 92 - 95 stones. Then you will in turn leave 91 stones for me (verify this is always possible). This way, you can always leave 5k+1 stones for me and finally I get the last stone, sigh. If we initially had 101 stones, on the other hand, I have a winning strategy and you are doomed to lose. ...

Cutting Game(POJ-2311) 题面 Urej loves to play various types of dull games. He usually asks other people to play with him. He says that playing those games can show his extraordinary wit. Recently Urej takes a great interest in a new game, and Erif Nezorf becomes the victim. To get away from suffering playing such a dull game, Erif Nezorf requests your help. The game uses a rectangular paper that consists of W*H grids. Two players cut the paper into two pieces of rectangular sections in turn. In each turn the player can cut either horizontally or vertically, keeping every grids unbroken. After N turns the paper will be broken into N+1 pieces, and in the later turn the players can choose any piece to cut. If one player cuts out a piece of paper with a single grid, he wins the game. If these two people are both quite clear, you should write a problem to tell whether the one who cut first can win or not. ...

公平组合游戏 公平组合游戏（Impartial Combinatorial Games）简称ICG，大致定义如下： 游戏有2名选手 对于游戏任何一种可能的局面（position），合法的操作集合只取决于这个局面本身 选手轮流操作（move），且只能在合法操作集合中选择 在游戏出于某状态，当前选手合法操作集合为空时判负，游戏结束 查看解析 一个公平游戏可以抽象地用一个有向无环图来表示，这个图中每个点都对应一个状态，每条有向边代表从一个状态到另一个状态的合法操作。 ...