Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：n行格子，每行m个，每行有一黑一白两个棋子，给定初始位置，先手执黑棋，后手执白棋，每次可以在同一行内向左移动，不能超过边界，且不能越过对方的棋子，同一个格子只能有一个棋子。问先手是否必赢。
思路：可以看成n个独立的游戏的 叠加。。。所以最后异或和一下就好。。
我们来求sg函数。。。一开始的是想把点对hash成一个数。。。然后发现其实没必要。。。直接二维就好了。。
由于初始化的时候要考虑最大。。。所以sg函数的值会有一个便宜。。。和设定N有关。。减去偏移就好了。。。（我的代码里这个偏移是11026）
1A蛤蛤蛤
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2016年07月22日 星期五 21时01分19秒
4File Name :code/hdu/1730.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=2E2+7;
34bool vis[N*N];
35int sg[N][N];
36int n,m;
37
38void sg_init(int m)
39{
40 ms(sg,0);
41
42 for ( int i1 = 1 ; i1 <= m ; i1++)
43 for ( int i2 = 1 ; i2 <= m ; i2++)
44 {
45 if (i1==i2) continue ; // 棋子不能在同一个位置？
46 ms(vis,false);
47
48 int x = i1;
49 int y = i2;
50
51 if ( x<y )
52 {
53 for ( int j = x+1 ; j <=y-1; j++)
54 vis[sg[x][j]] = true;
55
56 for ( int j = 1 ; j <= x-1 ; j++)
57 vis[sg[j][y]] = true;
58 }
59 else
60 {
61 for ( int j = y + 1 ; j <= x-1 ; j++)
62 vis[sg[j][y]] = true;
63
64 for ( int j =1 ; j <= y-1 ; j++)
65 vis[sg[x][j]] = true;
66 }
67
68 for ( int j1 = 1 ; j1 <= m ; j1++ )
69 for ( int j2 = 1 ; j2 <= m ; j2++)
70 if (!vis[j1*m+j2])
71 {
72 //cout<<"acccc"<<endl;
73 sg[i1][i2] = j1*m+j2;
74 break;
75 }
76 }
77}
78int main()
79{
80 #ifndef ONLINE_JUDGE
81 freopen("code/in.txt","r",stdin);
82 #endif
83
84 sg_init(105);
85
86// for ( int i = 0 ;i <= 10 ; i++)
87// for ( int j = 0 ; j <= 10 ; j++)
88// cout<<"i:"<<i<<" j:"<<j<<" "<<sg[i][j]<<endl;
89 while (~scanf("%d%d",&n,&m))
90 {
91 int sum = 0 ;
92 for ( int i = 1 ; i <= n ; i++)
93 {
94 int x,y;
95 scanf("%d%d",&x,&y);
96 int tmp = sg[x][y]-11026;
97 sum^=tmp;
98 }
99 if (sum)
100 {
101 puts("I WIN!");
102 }
103 else
104 {
105 puts("BAD LUCK!");
106 }
107 }
108
109
110 #ifndef ONLINE_JUDGE
111 fclose(stdin);
112 #endif
113 return 0;
114}