[luogu2594 ZJOI2009]染色游戏(博弈论)

Solution

对于硬币问题，结论是：当前局面的SG值等于所有背面朝上的单个硬币SG值的异或和

对于求单个背面朝上的硬币SG值。。。打表找规律吧

Code

//By Menteur_Hxy

#include <cmath>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define Re register

#define Ms(a,b) memset(a,(b),sizeof(a))

#define Fo(i,a,b) for(Re int i=(a),_=(b);i<=_;i++)

#define Ro(i,a,b) for(Re int i=(b),_=(a);i>=_;i--)

using namespace std;

inline int read() {

    int x=0,f=1;char c=getchar();

    while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}

    while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();

    return x*f;

}

int T;

bool vis[510];

char s[110];

int lowbit(int x) {return x&-x;}

int getSG(int i,int j) {

	if(i==1||j==1) return log2(lowbit(i+j-1));

	else return i+j-2;

}

int main() {

    T=read();

    while(T--) {

    	Ms(vis,0);

    	int n=read(),m=read(),SG=0;

    	Fo(i,1,n) {

    		scanf("%s",s+1);

    		Fo(j,1,m) if(s[j]!='H') vis[getSG(i,j)]^=1;

    	}

    	Fo(i,0,n+m) if(vis[i]) {SG=1;break;}

    	puts(SG?"-_-":"=_=");

    }

}

巴特西

[luogu2594 ZJOI2009]染色游戏(博弈论)

Solution

Code

最新文章

热门文章