正題

---

題目大意

有$n$堆石子，每次選擇一個區間博弈，先手必須先取最右邊的石子堆。

每次詢問$(r,a,b)$表示在$a～b$中選擇一個數$l$。要求使用$l～r$這個區間的石子進行博弈，然后若先手必勝輸出最右邊的石子需取的最大石子個數并讓石子堆減去這個數。若先手必敗輸出$?1$

---

解題思路

首先這是一個$NIM$博弈，若$a_{l}xor{a}_{l+1}xor{a}_{l+2}xor...xor{a}_r=0$那么先手必敗。

那如果$a_{l}xor{a}_{l+1}xor{a}_{l+2}xor...xor{a}_{r?1}=x$且$x\le a_r$那么我們可以從$a_r$中取走$a_r?x$個石頭然后使得$a_r=x$那么這樣輪到后手開始時所以的異或起來就為0了。

那么我們如何求最小值呢？分塊套Trie暴力！

因為數據水所以能夠過，不過需要加兩個優化

當$b=r$時直接讓$l$取$r$，這個十分顯然，因為要使異或和最小所以自己異或自己就是0

當$a_r=0$時輸出-1，依舊十分顯然

日后可能會將正解補上有生之年

---

$code$

#pragma GCC optimize(2) %:pragma GCC optimize(3) %:pragma GCC optimize("Ofast") %:pragma GCC optimize("inline") #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=110000; int n,w[N],m; int main() {scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&w[i]);scanf("%d",&m);while(m--){int x=0,ans=2147483647,a,b,r;scanf("%d%d%d",&r,&a,&b);if(w[r]==0){printf("-1\n");continue;}if(r==b){printf("%d\n",w[r]);w[r]=0;continue;}for(int i=r-1;i>=a;i--){x=x^w[i];if(i<=b) ans=min(ans,x);}if(w[r]-ans>0) printf("%d\n",w[r]-ans),w[r]=ans;else printf("-1\n");} }

總結

以上是生活随笔為你收集整理的jzoj3339-[NOI2013模拟]wyl8899和法法塔的游戏【博弈论,暴力】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。