本文主要是介绍#线性基,博弈论#洛谷 4301 JZOJ 3200 BZOJ 3105 新Nim游戏,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目
Nim游戏进阶,第一轮可以拿走若干堆的石子,之后与Nim游戏相同问先手是否必胜,是的话输出第一轮拿走的最小值,不是输出-1
分析
那么 N i m Nim Nim游戏先手必胜当且仅当A1 xor A2 xor…xor An不等于0,那么就要让把等于0的情况去掉,那么可以用到线性基,当无法插入也就说明异或和为0,所以累计答案,但是题目又说取最小值,那么从大到小排序,让大的早点被取掉
代码
#include <cstdio>
#include <cctype>
#include <algorithm>
#define rr register
using namespace std;
typedef long long ll;
int rec[31],n,a[1001]; ll ans;
inline signed iut(){rr int ans=0; rr char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans;
}
inline signed add(int x){for (rr int i=30;~i;--i)if ((x>>i)&1){if (!rec[i]){rec[i]=x;return 1;}x^=rec[i];}return 0;
}
signed main(){n=iut();for (rr int i=1;i<=n;++i) a[i]=iut();sort(a+1,a+1+n);for (rr int i=n;i;--i)if (!add(a[i])) ans+=a[i];return !printf("%lld",ans);
}
这篇关于#线性基,博弈论#洛谷 4301 JZOJ 3200 BZOJ 3105 新Nim游戏的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!