记录一个菜逼的成长。。
题目链接
题目大意: 有T组数据 给你G个子游戏，每个子游戏有一个数n,两个人轮流可以减去b的幂次,前提是小于等于n。不能再减就算输。 问最后谁赢。
打sg表找规律。。 多个子游戏 ，则结果异或。
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> using namespace std; #define ALL(v) (v).begin(),(v).end() #define cl(a,b) memset(a,b,sizeof(a)) #define clr clear() #define pb push_back #define mp make_pair #define fi first #define se second typedef long long LL; typedef pair<int,int> PII; const int maxn = 1000000 + 10; int sg[maxn],f[15]; bool Hash[maxn]; PII g[maxn]; void init() { f[0] = 1; for( int i = 1; i < 8; i++ ){ f[i] = f[i-1] * 12; } } void sg_solve(int n,int m) { init(); memset(sg,0,sizeof(sg)); for( int j,i = 1; i <= n; i++ ){ memset(Hash,0,sizeof(Hash)); for( j = 0; j <= m; j++ ){ if(i - f[j] >= 0)Hash[sg[i-f[j]]] = 1; } for( j = 0; j <= n; j++ ) if(!Hash[j])break; sg[i] = j; } } void table() { sg_solve(1000,7); for( int i = 1; i <= 30; i ++){ printf("- ",i); printf("%d\n",sg[i]); } } int main() { //table(); //freopen("powers.in","r",stdin); int T; scanf("%d",&T); while(T--){ int G,b,n; scanf("%d",&G); int ans = 0; for( int i = 0; i < G; i++ ){ scanf("%d%d",&g[i].fi,&g[i].se); if(g[i].fi & 1){ if(g[i].se & 1)ans ^= 1; else ans ^= 0; } else { int tmp = g[i].se % (g[i].fi+1); if(!tmp)ans ^= 0; else { if(tmp <= g[i].fi - 1){ if(tmp & 1)ans ^= 1; else ans ^= 0; } else { ans ^= 2; } } } } printf("%d\n",ans ? 1 : 2); } return 0; }