首页 > 代码库 > BZOJ 3105 [CQOI2013]新Nim游戏 ——线性基
BZOJ 3105 [CQOI2013]新Nim游戏 ——线性基
【题目分析】
神奇的题目,两人都可以第一次取走足够多堆的石子。
nim游戏的规则是,如果异或和为0,那么就先手必输,否则先手有必胜策略。
所以只需要剩下一群异或和为0就可以了。
先排序,线性基扫一遍即可(保留最多的不为0的堆)
【代码】
#include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <set> #include <map> #include <string> #include <algorithm> #include <vector> #include <iostream> #include <queue> using namespace std; #define maxn 100005 #define ll long long int read() { int x=0,f=1; char ch=getchar(); while (ch<‘0‘||ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();} while (ch>=‘0‘&&ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();} return x*f; } int n,a[maxn],b[maxn]; int lb[32]; ll ans; int main() { n=read(); for (int i=1;i<=n;++i) scanf("%d",&a[i]); sort(a+1,a+n+1); for (int i=1;i<=n;++i) b[i]=a[i],ans+=b[i]; for (int i=n;i;--i) { for (int j=31;j>=0;j--) { if ((a[i]>>j)&1) { if (!lb[j]) {lb[j]=a[i];break;} else a[i]^=lb[j]; } } if (a[i]) ans-=b[i]; } cout<<ans<<endl; }
BZOJ 3105 [CQOI2013]新Nim游戏 ——线性基
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。