洛谷P4301 [CQOI2013]新Nim游戲

題目描述

傳統(tǒng)的Nim游戲是這樣的：有一些火柴堆，每堆都有若干根火柴（不同堆的火柴數(shù)量可以不同）。兩個(gè)游戲者輪流操作，每次可以選一個(gè)火柴堆拿走若干根火柴。可以只拿一根，也可以拿走整堆火柴，但不能同時(shí)從超過(guò)一堆火柴中拿。拿走最后一根火柴的游戲者勝利。

本題的游戲稍微有些不同：在第一個(gè)回合中，第一個(gè)游戲者可以直接拿走若干個(gè)整堆的火柴。可以一堆都不拿，但不可以全部拿走。第二回合也一樣，第二個(gè)游戲者也有這樣一次機(jī)會(huì)。從第三個(gè)回合（又輪到第一個(gè)游戲者）開(kāi)始，規(guī)則和Nim游戲一樣。

如果你先拿，怎樣才能保證獲勝？如果可以獲勝的話，還要讓第一回合拿的火柴總數(shù)盡量小。

輸入輸出格式

輸入格式：

第一行為整數(shù)\(k\)。即火柴堆數(shù)。
第二行包含\(k\)個(gè)不超過(guò)10^9的正整數(shù)，即各堆的火柴個(gè)數(shù)。

輸出格式：

輸出第一回合拿的火柴數(shù)目的最小值。如果不能保證取勝，輸出-1。

思路：

線性基
對(duì)于nim游戲，有一個(gè)規(guī)律就是如果所有數(shù)異或和不為零，那么就是先手勝，否則先手?jǐn)　?br /> 可以這么理解這個(gè)規(guī)律，如果異或和不為零，那么說(shuō)明此時(shí)棋盤(pán)上還有棋子，那么先手一定可以通過(guò)一次操作使得異或和變成零。
當(dāng)異或和變成零之后，就會(huì)有兩種情況，一種是棋盤(pán)上還有棋子，一種是棋盤(pán)上沒(méi)有棋子。
對(duì)于第二種情況，已經(jīng)獲得勝利了。
而對(duì)于第一種情況，后手的一次操作一定會(huì)讓異或和非零，那么就再次回到了一開(kāi)始的情況，如此重復(fù)，先手一定會(huì)贏。

那么對(duì)于新nim游戲，留給先手的問(wèn)題就變成了構(gòu)造出一個(gè)和最大的數(shù)集，使這個(gè)數(shù)集中全部或部分的數(shù)以任意方式組合進(jìn)行異或運(yùn)算都無(wú)法使得異或和為零，即后手無(wú)法構(gòu)造出異或和為零的狀態(tài)（他的必勝狀態(tài)）。

至此就符合了線性基性質(zhì)。

CODE：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define MAXN 110 int nums[MAXN],li[MAXN]; int i,j,k,m,n; long long int ans; bool insert(int n){for(int i=62;i>=0;i--){if((n>>i)&1){if(!li[i]){li[i]=n;return true;}n^=li[i];}}return false; } int main(){scanf("%d",&n);for(i=1;i<=n;i++) scanf("%d",nums+i);sort(nums+1,nums+n+1);for(i=n;i>=1;i--){if(!insert(nums[i])) ans+=nums[i];}printf("%lld\n",ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/linxif2008/p/10198073.html

總結(jié)

以上是生活随笔為你收集整理的洛谷P4301 [CQOI2013]新Nim游戏的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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