题意：

    给你n组石子，每组有两摞。操作为选其中一摞石子分成两摞，抛弃原来同一组的另一摞石子，直到无法操作。问给你这n组石子，问先手胜还是后手胜。 （比如（10,8,），你可以将10分为（5,5），那么这一组石子就成了（5,5），那个8就可以不用管了）

题目链接：

 

  题解：

    其实这道题我也不是很会，看了题解才写出来T_T

    首先每组是独立的，可以求出每一组的SG值然后用SG定理解决。

    那么每组的SG值怎么求呢？

　　好像没有人会qwq 所以我们先打个表。比如下面这个10*10的表（第一行为列号）

i:0 1 2 3 4 5 6 7 8 9 10

i:1 0 1 0 2 0 1 0 3 0 1

i:2 1 1 2 2 1 1 3 3 1 1

i:3 0 2 0 2 0 3 0 3 0 2

i:4 2 2 2 2 3 3 3 3 2 2

i:5 0 1 0 3 0 1 0 3 0 1

i:6 1 1 3 3 1 1 3 3 1 1

i:7 0 3 0 3 0 3 0 3 0 4

i:8 3 3 3 3 3 3 3 3 4 4

i:9 0 1 0 2 0 1 0 4 0 1

i:10 1 1 2 2 1 1 4 4 1 1

 

　　我（bie）们（ren）可以发现这么一个规律：

　　1，当i和j都是奇数时sg值为0 .  2，当i和j都为偶数是sg[i][j] = sg[i/2][j/2]+1 

　　3，当i，j一奇一偶时（假设i为奇数）sg[i][j] = sg[i+1][j+1]

　　复杂度为O（t*n*logS）

　　于是这道题就做完啦qwq

 AC代码：

 

#include
      
       #include
       
        #include
        
         #define LL long long#define RI register intusing namespace std;const int INF = 0x7ffffff ;const int N = 1e4 + 10 ;inline int read(){    int k = 0 , f = 1 ; char c = getchar() ;    for( ; !isdigit(c) ; c = getchar())      if(c == '-') f = -1 ;    for( ; isdigit(c) ; c = getchar())      k = k*10 + c-'0' ;    return k*f ;}int n, hh[N] ;int ser(int x,int y) {    if(x%2 && y%2) return 0 ;    if(x%2 &&!(y%2)) return ser(x+1,y) ;    if(!(x%2) && y%2) return ser(x,y+1) ;    return ser(x>>1,y>>1)+1 ;}int main() {    int t = read() ;    while(t--) {        int cnt = 0 ;        n = read() ;        n >>= 1 ;        for(int i=1;i<=n;i++) {            int a = read(), b = read() ;            hh[++cnt] = ser(a,b) ;        }        int ans = 0 ;        for(int i=1;i<=cnt;i++) ans ^= hh[i] ;        if(ans) printf("YES\n") ;        else printf("NO\n") ;    }    return 0 ;    }
        
       
      

 

 

 

 打表代码：

 

#include
      
       #include
       
        #include
        
         #define LL long long#define RI register intusing namespace std;const int INF = 0x7ffffff ;const int N = 1000 + 10 ;inline int read(){    int k = 0 , f = 1 ; char c = getchar() ;    for( ; !isdigit(c) ; c = getchar())      if(c == '-') f = -1 ;    for( ; isdigit(c) ; c = getchar())      k = k*10 + c-'0' ;    return k*f ;}int sg[N][N] ; int ser(int x,int y) {    if(sg[x][y]) return sg[x][y] ;    bool vis[N] = {
    0} ;    for(int i=1;i