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