正文

codeforces 768E Game of Stones

IP云
IP云V管理员/2 阅读
09/11
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接：http://codeforces.com/problemset/problem/768/E

NIM游戏改版：对于任意一堆，拿掉某个次数最多只能一次。

对于一堆石头数量为$X$。找到一个最小的$Z$使得${ (\sum_{i=1}^{Z}i)\leq x}$，我们把这一堆数量为X的石头，看作Z个数目分别为${1...n}$的石头堆。

那么一次拿一定量的石头，是不是相当于拿走了${{1,2,3....,Z}}$中的任意多堆石头？

当然如果拿的石头数目$P$超过了${\sum _{i=1}^{Z}i}$，相当于拿走了所有大于${{Z}'}$的的石头堆。${{Z}'=Max\left \{ val|(\sum _{i=1}^{val}i)\leq (X-P) \right \}}$

所以${SG(X)=Max(Z|(\sum_{i=1}^{Z}i)\leq X)}$

很显然，这是一个multi-nim游戏，主游戏的SG值等于所有子游戏的异或和。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;
#define maxn 10010
#define llg long long
#define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
llg n,m,x,v; llg make_sg(llg x)
{
if (x==) return ;
llg l=,r=(llg)1e9,val;
while (l<=r)
{
llg mid=(l+r)>>;
if ((mid*mid+mid)/<=x) {l=mid+; val=mid;}else r=mid-;
}
return val;
} int main()
{
yyj("SG");
cin>>n; for (llg i=;i<=n;i++)
{
scanf("%lld",&v);
x^=make_sg(v);
}
if (!x) cout<<"YES";else cout<<"NO";
return ;
}