正題

題目鏈接:https://www.luogu.com.cn/problem/P3480

---

題目大意

$n$個(gè)石頭堆上進(jìn)行$\text{Nim}$游戲，不過(guò)需要滿足每次操作前后都有$a_i\le a_{i+1}(i\in [1,n))$

---

解題思路

讓每一個(gè)$b_i=a_i?a_{i?1}$就是一個(gè)階梯博弈問(wèn)題了。

階梯博弈問(wèn)題：$n$堆石頭，第$i$堆石頭有$a_i$個(gè)，每次一個(gè)玩家可以取走若干個(gè)第一堆的石頭，或者將第$i$堆的任意個(gè)石頭丟到第$i?1$堆里面。

這個(gè)問(wèn)題的$sg$函數(shù)就是編號(hào)為奇數(shù)的石頭數(shù)量的異或和，具體證明的話就是如果只看奇數(shù)堆石頭，那么轉(zhuǎn)移奇數(shù)的堆里的石頭就相當(dāng)與去掉一些石頭。所以如果奇數(shù)堆必勝的玩家一定會(huì)轉(zhuǎn)移奇數(shù)堆的，因?yàn)槿绻笫洲D(zhuǎn)移偶數(shù)堆里的那么先手再把新的轉(zhuǎn)走狀態(tài)就不會(huì)改變。

所以直接做就好了，時(shí)間復(fù)雜度$O(Tn)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1100; int T,n,a[N]; int main() {scanf("%d",&T);while(T--){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=n;i>=1;i--)a[i]=a[i]-a[i-1];int ans=0;for(int i=n;i>=1;i-=2)ans^=a[i];puts(ans?"TAK":"NIE");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的P3480-[POI2009]KAM-Pebbles【阶梯博弈】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。