[BZOJ1188]-[HNOI2007]分裂游戏-Multi_SG

说在前面

博弈题不是套路就是神题…
（可能见多了就都是套路了hhhhh）

---

题目

BZOJ1188传送门
看题可戳传送门

---

解法

me真是想了好久，都没有想到怎么去定义局面（me可能是个sa_bi）

首先容易发现的是，对于必败方，可以把每个位置的豆子数对2取模
因为如果必败方对一个偶数位置进行了操作，那么另一个人可以进行相同的操作，这样必败方面临的总是偶数局面。如此下去，最后一次操作一定是由必胜方进行的。所以有偶数个豆子等于没有

然后me就从奇偶性瞎搞了一番，然后失败了…
然后去看了题解……

我们可以把一个豆子的位置，当成一个局面
一个豆子可以转移到比位置比它小的两个豆子的局面，然后就是个Multi_SG，然后就完了…
这样做是因为，如果把一整堆石子的数量看作状态，那么状态之间是互相干扰的，不方便讨论
但是如果把单独的石子看成状态，石子和石子间相互独立，就可以用SG解决了

---

下面是代码

#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

int T , N , a[22] , sg[25] ;

void UPD( int &t1 , int &t2 , int &t3 , int x , int y , int z ){
    if( ( x > t1 ) || ( t1 == x && y > t2 ) || ( t1 == x && t2 == y && z > t3 ) )
        t1 = x , t2 = y , t3 = z ;
}

bool vis[100] ;
void preWork(){
    sg[0] = 0 ;
    for( int i = 1 ; i <= 20 ; i ++ ){
        sg[i] = -1 ;
        memset( vis , 0 , sizeof( vis ) ) ;
        for( int j = i - 1 ; j >= 0 ; j -- )
            for( int k = j ; k >= 0 ; k -- )
                vis[ sg[j]^sg[k] ] = true ;
        for( int j = 0 ; sg[i] == -1 ; j ++ )
            if( !vis[j] ) sg[i] = j ;
    }
}

int main(){
    preWork() ;
    scanf( "%d" , &T ) ;
    while( T -- ){
        scanf( "%d" , &N ) ; N -- ;
        int SG = 0 ;
        for( int i = N ; i >= 1 ; i -- ){
            scanf( "%d" , &a[i] ) ;
            if( a[i]&1 ) SG ^= sg[i] ;
        } scanf( "%*d" ) ;

        int cnt = 0 , t1 = 0 , t2 = 0 , t3 = 0 ;

        for( int i = 1 ; i <= N ; i ++ ) if( a[i] )
            for( int j = i - 1 ; j >= 0 ; j -- )
                for( int k = j ; k >= 0 ; k -- )
                    if( !( SG ^ sg[i] ^ sg[j] ^ sg[k] ) )
                        cnt ++ , UPD( t1 , t2 , t3 , i , j , k ) ;

        if( cnt ) printf( "%d %d %d\n%d\n" , N - t1 , N - t2 , N - t3 , cnt ) ;
        else printf( "-1 -1 -1\n0\n" ) ;
    }
}