題目鏈接：點(diǎn)擊查看

題目大意：給出m堆石子，規(guī)則是尼姆博弈的規(guī)則，問先手必勝還是必?cái)?#xff0c;若能必勝則第一次有多少種方式取石子

題目分析：這個(gè)題目是因?yàn)橐婚_始知道尼姆博弈的結(jié)論，需要異或所有石子來判斷的，然后關(guān)于最后第一次該怎么取石子，還是在訓(xùn)練的時(shí)候自己亂推出來的。。至于是為什么當(dāng)時(shí)還是不知道的，現(xiàn)在來稍微分析一下

我們已經(jīng)知道了尼姆博弈的結(jié)論，即設(shè)ans為所有石子的異或值了：

a1^a2^...^an=ans

如果ans為0，那么先手必?cái)?#xff0c;如果ans不為0，則先手必勝，必勝的條件下，我們接下來需要尋找該怎么取石子能讓局面達(dá)到奇異局面，也就是必?cái)【置?#xff0c;即讓新的石子異或后變?yōu)?

我們假設(shè)需要改變一堆石子ai，變?yōu)閍i'，則他們的關(guān)系是：

ai'=ai^ans

我們代入上面的第一個(gè)公式中：

a1^a2^...^ai'^...^an=a1^a2^...^ai^ans^...^an=ans^ans=0

這樣就能變成奇異局面了，因?yàn)檫@是取石子游戲，必須滿足ai'嚴(yán)格小于ai才行，即需要滿足：

ai'<ai，即ai^ans<ai

滿足上述條件的ai'就是答案了

還是需要注意一下，異或?qū)儆谖贿\(yùn)算，他的優(yōu)先級比==要低，記得加括號來保證正確的運(yùn)算順序

代碼：

#include<iostream> #include<cstdio> #include<algorithm> #include<string> #include<cstring> #include<map> #include<cmath> using namespace std;typedef long long LL;const int N=2e5+100;int a[N];int main() {int n;while(scanf("%d",&n)!=EOF&&n){int ans=0;for(int i=1;i<=n;i++){scanf("%d",a+i);ans^=a[i];}if(!ans)puts("No");else{puts("Yes");for(int i=1;i<=n;i++){if((a[i]>(ans^a[i])))printf("%d %d\n",a[i],ans^a[i]);}}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 2176 取(m堆)石子游戏(尼姆博奕)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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