博弈论转化

本题的限制条件很多,我们尝试转化,

我们发现,定义 c[i] 为第 i 堆可以取得数量,如果第 i 堆取出了 x ,那么 c[i] - x , c[i + 1] + x

我们发现这是一个反着的阶梯Nim,qwq

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;int T, n, num[1005], c[1005];int main() {    cin>>T;    while(T--) {        cin>>n;        for(int i = 1 ; i <= n ; i++) {            cin>>num[i];            c[i] = num[i] - num[i - 1];        }        int ans = 0;        for(int i = n ; i >=1 ; i -= 2) {            ans ^= c[i] ;        }        if(ans) printf("TAK\n");        else printf("NIE\n");    }    return 0;}