http://acm.hdu.edu.cn/showproblem.php?pid=4678
自己太蠢...没学SG...还是浩神指点我SG精髓以后才A的这题...(第一题SG
这里子游戏之间没有影响所以只要找规律得出所有子游戏的SG值 然后求XOR就行了
这里题面太复杂 但看懂以后其实可以转换成取石子游戏:
给你N堆石子 , 每次只能取一个或者整堆取走 谁先取完谁胜
每堆石子的数量就是空白部分附近所有连接数字的数量+1(空白本身算一个石子)
孤立的单个数字也组成一堆
那么根据找规律可得:
奇数堆SG = 1 偶数堆SG = 2
/********************* Template ************************/ #include <set> #include <map> #include <list> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <bitset> #include <cstdio> #include <string> #include <vector> #include <cassert> #include <cstdlib> #include <cstring> #include <sstream> #include <fstream> #include <numeric> #include <iomanip> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define EPS 1e-8 #define MAXN 1005 #define MOD (int)1e9+7 #define PI acos(-1.0) #define DINF (1e10) #define LINF ((1LL)<<50) #define INF ((int)1e10) #define max(a,b) ((a) > (b) ? (a) : (b)) #define min(a,b) ((a) < (b) ? (a) : (b)) #define max3(a,b,c) (max(max(a,b),c)) #define min3(a,b,c) (min(min(a,b),c)) #define BUG cout<<"BUG! "<<endl #define line cout<<"--------------"<<endl #define L(t) (t << 1) #define R(t) (t << 1 | 1) #define Mid(a,b) ((a + b) >> 1) #define lowbit(a) (a & -a) #define FIN freopen("in.txt","r",stdin) #define FOUT freopen("out.txt","w",stdout) #pragma comment (linker,"/STACK:102400000,102400000") // typedef long long LL; // typedef unsigned long long ULL; // typedef __int64 LL; // typedef unisigned __int64 ULL; // int gcd(int a,int b){ return b?gcd(b,a%b):a; } // int lcm(int a,int b){ return a*b/gcd(a,b); } /********************* F ************************/ int ma[MAXN][MAXN]; bool vis[MAXN][MAXN]; int ax[8] = {-1,-1,-1,0,0,1,1,1}; int ay[8] = {-1,0,1,-1,1,-1,0,1}; int SG[MAXN*MAXN]; int n,m,k; int check(int xx,int yy){ if(xx >= 0 && xx < n && yy >= 0 && yy < m) return true; return false; } int bfs(pair<int,int> s){ queue< pair<int,int> > q; int ct = 0; q.push(s); while(!q.empty()){ for(int i = 0 ; i < 8 ; i++){ int xx = q.front().first + ax[i]; int yy = q.front().second + ay[i]; if(check(xx,yy)){ if(ma[xx][yy] == 0 && !vis[xx][yy]) q.push(make_pair(xx,yy)); else if(ma[xx][yy] == 1 && !vis[xx][yy]) ct++; vis[xx][yy] = true; } } q.pop(); } return ct; } int main() { //FIN; //FOUT; int T; cin>>T; for(int cas = 1 ; cas <= T; cas++){ memset(ma,0,sizeof(ma)); memset(vis,false,sizeof(vis)); memset(SG,0,sizeof(SG)); scanf("%d%d%d",&n,&m,&k); for(int ck = 0 ; ck < k ; ck++){ int a,b; scanf("%d%d",&a,&b); ma[a][b] = 2; for(int i = 0 ; i < 8 ; i++){ if(check(a+ax[i],b+ay[i]) && ma[a+ax[i]][b+ay[i]] != 2) ma[a+ax[i]][b+ay[i]] = 1; } } int cnt = 0; for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < m ; j++){ if(ma[i][j] == 0 && !vis[i][j]){ vis[i][j] = true; SG[cnt++] = (bfs(make_pair(i,j)) + 1) % 2 == 0 ? 2 : 1; } } } for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < m ; j++){ if(ma[i][j] == 1 && !vis[i][j]){ vis[i][j] = true; SG[cnt++] = 1; } } } int res = SG[0]; for(int i = 1 ; i < cnt ; i++){ res = res ^ SG[i]; } if(res == 0) printf("Case #%d: Fanglaoshi ",cas); else printf("Case #%d: Xiemao ",cas); } return 0; }