【bzoj3105】新Nim游戏

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游戏的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。