首页 > 代码库 > 【BZOJ】3576: [Hnoi2014]江南乐
【BZOJ】3576: [Hnoi2014]江南乐
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3576
很显然，这是一个multi-nim游戏。
注意：1.一个点的SG值就是一个不等于它的后继点的SG的且大于等于零的最小整数。(mex)
2.主游戏的SG值等于所有子游戏的异或和
所以区分好主游戏和后继点的区别。
一开始多个石子堆组合起来形成了一个主游戏。
一个石子堆可以分为多个石子堆，每一种分发构成了一个主游戏，这些主游戏的异或和构成的当前这个点(状态)的SG函数。
显然有一个${m^{2}}$做法，即记忆化搜索SG函数。
考虑${x/i}$只有$\sqrt{n}$种取值，再考虑一下它们的奇偶性，然后分块来做。
70Code:
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 10010010 #define llg long long 11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);12 llg n,m,bj[maxn],sg[maxn],T,F,a[maxn];13 14 llg dp(llg x)15 {16 if (bj[x]) return sg[x];17 bj[x]=1;18 sg[x]=0;19 bool e[maxn];20 memset(e,0,sizeof(e));21 for (llg m=2;m<=x;m++)22 {23 llg v1=m-x%m,v2=x%m;24 llg nsg=0;25 if (v1&1) nsg^=dp(x/m);26 if (v2&1) nsg^=dp(x/m+1);27 e[nsg]=1;28 }29 for (llg i=0;1;i++) if (!e[i]) {sg[x]=i; return sg[x];}30 }31 32 int main()33 {34 yyj("game");35 cin>>T>>F;36 for (llg i=0;i<F;i++) bj[i]=1;37 while (T--)38 {39 scanf("%lld",&n);40 llg ans=0;41 for (llg i=1;i<=n;i++)42 {43 scanf("%lld",&a[i]);44 ans^=dp(a[i]);45 }46 if (ans) printf("1");else printf("0");47 if (T) printf(" ");48 }49 return 0;50 }
100Code:
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 10010010 #define llg int11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);12 llg n,m,bj[maxn],sg[maxn],T,F,a[maxn];13 14 llg dp(llg x)15 {16 if (bj[x]) return sg[x];17 bj[x]=1;18 sg[x]=0;19 bool e[maxn];20 memset(e,0,sizeof(e));21 for (llg m=2,j=0;m<=x;m=j+1)22 {23 j=x/(x/m);24 llg v1=m-x%m,v2=x%m,cnt=j-m+1;25 llg nsg=0;26 if (v1&1) nsg^=dp(x/m);27 if (v2&1) nsg^=dp(x/m+1);28 e[nsg]=1;29 if (cnt>=2)30 {31 nsg=0;32 if (((m+1)-x%(m+1))&1) nsg^=dp(x/(m+1));33 if ((x%(m+1))&1) nsg^=dp(x/(m+1)+1);34 e[nsg]=1;35 }36 }37 for (llg i=0;1;i++) if (!e[i]) {sg[x]=i; return sg[x];}38 }39 40 int main()41 {42 yyj("game");43 cin>>T>>F;44 for (llg i=0;i<F;i++) bj[i]=1;45 while (T--)46 {47 scanf("%d",&n);48 llg ans=0;49 for (llg i=1;i<=n;i++)50 {51 scanf("%d",&a[i]);52 ans^=dp(a[i]);53 }54 if (ans) printf("1");else printf("0");55 if (T) printf(" ");56 }57 return 0;58 }
【BZOJ】3576: [Hnoi2014]江南乐
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。