Portal--> bzoj3105 新Nim游戲

Solution

　　轉化一下問題

　　首先看一下原來的Nim游戲，先手必勝的條件是：每堆數量的異或和不為\(0\)

　　所以在新的游戲中，如果要保證自己（先手）有必勝策略的話，那必須要保證到一開始先手拿走若干堆之后，后手無法拿走若干堆使得剩下每堆的數量異或和為\(0\)，也就是說我們要留下的應該是一個極大線性無關組

　　線性無關組這個的話我們可以通過線性基解決，具體的話就是如果\(insert\)完了之后這個數被變成了\(0\)，那么說明這個數和線性基里面的數線性相關

　　容易注意到\(insert\)的順序會有影響，那么現在的問題就是，應該選取哪些數作為線性基（或者說應該按照什么順序把那堆數插到線性基里）

　　先把結論擺出來：實際上只要按照從大到小的順序貪心地加就好了

　　為什么可以貪心呢？

　　

　　這里需要借助一個很神奇的東西：Portal-->擬陣

　　

?　　我們設\(n\)個火柴堆的數目為集合\(S\)，如果\(S\)的某個子集\(R\)不存在任何一個非空子集異或和為\(0\)，那么\(R\in I\)

　　接下來我們來證明一下\(M=(S,I)\)是一個擬陣

　　1、首先\(S\)肯定是一個有限集

　　2、遺傳性：設\(A\in I\)，則由定義可知\(A\)不存在任何一個非空子集滿足異或和為\(0\)，所以對于任意\(B \subseteq A\)，\(B\)都滿足不存在任何一個非空子集異或和為\(0\)（因為\(B\)的子集也是\(A\)的子集），所以\(B\in I\)，所以\(I\)是遺傳的

　　3、交換性質：設\(，A，B\in I\)，且\(|B|>|A|\)，我們現在要證明\(\exists x\in B-A\)使得\(A\cup\{x\}\in I\)，這里考慮用反證法：假設對于\(\forall x\in B-A\)均有\(A\cup \{x\}\notin I\)，則\(B-A\)中的元素均可以由\(A\)的某個子集的異或和表示，因此我們可以得到結論\(B\)中的所有元素均可以由\(A\)的某個子集的異或和來表示。但是這與我們前面的假設\(|B|>|A|\)是矛盾的，所以假設不成立，得證。

?　　我們將\(M=(S,I)\)看成一個帶權擬陣，每個\(S\)中的元素的權值就是對應的堆中火柴的數量，那么運用貪心算法我們就可以在帶權擬陣中找出權值最大的基

　　所以就能直接用貪心做啦

? 　　

　　代碼大概長這個樣子：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const int MAXN=110,UP=30; int a[MAXN]; int n,m; ll ans; namespace xxj{int a[UP+1];bool insert(int x){for (int i=UP;i>=0;--i)if (x&(1<<i)){if (!a[i]){a[i]=x;break;}x^=a[i];}return x;} }int main(){ #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin); #endifscanf("%d",&n);for (int i=1;i<=n;++i) scanf("%d",a+i);sort(a+1,a+1+n);ans=0;for (int i=n;i>=1;--i)if (!xxj::insert(a[i])) ans+=a[i];printf("%lld\n",ans); }

轉載于:https://www.cnblogs.com/yoyoball/p/9218187.html

總結

以上是生活随笔為你收集整理的【bzoj3105】新Nim游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

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