首页 > 数据结构 > Hash表 > HDU 2839-Game-计算几何-[解题报告]HOJ
2014
02-17

HDU 2839-Game-计算几何-[解题报告]HOJ

Game

问题描述 :

After played many kinds of nim games, Xay and Amr decided to play something different. As the judge, I wrote several valid pairs of numbers on the blackboard. For every pair (x, y), it is valid only if -y ≤ x ≤ y and the greatest common divisor of x and y is 1. The typical legal move is to alter just one of these pairs. If we change (x, y) to (a, b):
1. (a, b) should be a valid pair.
2. 1 ≤ b < y if y != 1
3. 1 ≤ b ≤ y, -b < a < b if y = 1.

Furthermore, such a replacement will be legal for Xay only if a*y – b*x < 0, legal for Amr only if a*y – b*x > 0.For example, Xay can change (2, 5) to (1,3), (1,4), (-1,2), (0,1), (-1,1), etc. And Amr can similarly change (2, 5) to (1, 2), (2, 3), (3, 4), (1, 1), etc.

They will play on these pairs alternately. The last one who be able to move is the winner .We have already knew that both Amr and Xay are very clever and they will play this game perfectly. Now, my dear programmers, can you predict that who will be the winner?

输入:

The first line contains a single positive integer T. which is the number of test cases. Each test case starts with a line with a single positive integer n(1 ≤ n ≤ 100) and a string “Xay” or “Amr” means who moves first. Then n lines follows, each line contains a pair of integers x and y. (1 ≤ y ≤ 15 and �y ≤ x ≤ y)

输出:

The first line contains a single positive integer T. which is the number of test cases. Each test case starts with a line with a single positive integer n(1 ≤ n ≤ 100) and a string “Xay” or “Amr” means who moves first. Then n lines follows, each line contains a pair of integers x and y. (1 ≤ y ≤ 15 and �y ≤ x ≤ y)

样例输入:

3
1 Xay
0 1
2 Amr
1 1
-1 1
2 Xay
1 4
-1 2

样例输出:

Amr
Xay
Amr

Hint

If Xay choose the pair (x, y), he will change it to (a, b) which make a/b as large as possible. 

 The Spot Game 


The game of Spot is played on an NxN board as shown below for N = 4. During the game, alternate players may either place a black counter (spot) in an empty square or remove one from the board, thus producing a variety
of patterns. If a board pattern (or its rotation by 90 degrees or 180 degrees) is repeated during a game, the player producing that pattern loses and the other player wins. The game terminates in a draw after 2N moves if no duplicate pattern is produced before
then.

Consider the following patterns:

picture23

If the first pattern had been produced earlier, then any of the following three patterns (plus one other not shown) would terminate the game, whereas the last one would not.

Input and Output

Input will consist of a series of games, each consisting of the size of the board, N (2 tex2html_wrap_inline180 N tex2html_wrap_inline180 50)
followed, on separate lines, by 2N moves, whether they are all necessary or not. Each move will consist of the coordinates of a square (integers in the range 1..N) followed by a blank and a character `+’ or `-’ indicating the addition or removal of a spot
respectively. You may assume that all moves are legal, that is there will never be an attempt to place a spot on an occupied square, nor to remove a non-existent spot. Input will be terminated by a zero (0).

Output will consist of one line for each game indicating which player won and on which move, or that the game ended in a draw.

Sample input

2
1 1 +
2 2 +
2 2 -
1 2 +
2
1 1 +
2 2 +
1 2 +
2 2 -
0

Sample output

Player 2 wins on move 3
Draw

题意:放石头游戏(The game of Spot)在一块NxN的板子上进行,如下图为N=4的板子。游戏的玩法是两个玩家轮流放一块石头在空的格子上,或是可以从板子上拿一块石头起来,游戏的进行中可以发现,板子上石头的布局会不断变化,当一玩家排出已重复出现过的布局时,他就算输了这一局(一种布局如果将之旋转90度、180度、270度亦视为相同的布局)。若在2N步内未出现过相同的布局就算和局。

一开始就看错了题目,以为棋盘是4*4的,没看到n*n,wa了无数次,其中哈希函数也写错了。。一道简单的哈希题花了很久的时间。

#include<iostream>
#include<cstring>
#include<set>

using namespace std;

char grid[55][55];
set<string> vis;
int n;

int try_to_insert()
{
    string str="";
    int i,j;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            str=str+grid[i][j];
        }
    }
    if(vis.count(str)) return 0;
    vis.insert(str);
    str="";
    for(i=n-1;i>=0;i--)
    {
        for(j=0;j<n;j++)
        {
            str=str+grid[i][j];
        }
    }
    if(!vis.count(str)) vis.insert(str);
    str="";
    for(i=n-1;i>=0;i--)
    {
        for(j=n-1;j>=0;j--)
        {
            str=str+grid[i][j];
        }
    }
    if(!vis.count(str)) vis.insert(str);
    str="";
    for(i=0;i<n;i++)
    {
        for(j=n-1;j>=0;j--)
        {
            str=str+grid[i][j];
        }
    }
    if(!vis.count(str)) vis.insert(str);
    return 1;
}

int main()
{
    while(cin>>n&&n)
    {
        int flag=1,winner,num;
        int i,x,y;
        char ch;
        vis.clear();
        memset(grid,'0',sizeof(grid));
        for(i=0;i<2*n;i++)
        {
            cin>>x>>y>>ch;
            if(flag==0) continue;
            if(ch=='+') grid[x-1][y-1]='1';
            else if(ch=='-') grid[x-1][y-1]='0';
            if(try_to_insert()==0)
            {
                flag=0;
                num=i+1;
                if(i%2==0) winner=2;
                else winner=1;
                cout<<"Player "<<winner<<" wins on move "<<num<<endl;
            }
        }
        if(flag) cout<<"Draw"<<endl;
    }
    return 0;
}

解题参考:http://blog.csdn.net/zju_ziqin/article/details/18970247


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。