此文章可以使用目录功能哟↑(点击上方[+])

 FZU Problem 2240 Daxia & Suneast's problem

 Problem Idea

解题思路:

【题意】
n堆石子,每堆石子颗数为a1,a2,...,an

m轮游戏,每轮游戏开始前,suneast会把第i堆的石子改成x颗

在第j堆到第k堆之间进行取石子游戏

daxia先取,然后双方轮流,每次取的数量不得超过该堆的一半

不能取时为负

【类型】
博弈+[单点更新,区间查询]线段树

【分析】
令人熟悉的取石子游戏,不知道已经是多少次变型

但总的解法还是相似的

对于这种每堆石子的数量可能很大的情况,一般是无法用sg函数直接求得的

这个时候,我们通常的做法是通过sg函数打表来找到规律
在使用sg函数之前,我们先大致了解一下sg函数(具体的可以自行网上学习):
SG函数表示的是某种局面的状态,它是由mex运算得到的
mex表示最小的不属于这个集合的非负整数,例如mex{0,1,2,4}=3,mex{2,3,5}=0,mex{}=0;
其实mex可以这么理解,0表示必败态,非零表示必胜态,根据定理"能一步到达必败态的点就是必胜态",故只有集合包含0,那么mex得到的数必定非0
根据定理"只能到达必胜态的点是必败态",故若集合中不包含0,那么mex得到的数必定为0
接下来,我们回归正题,suneast换石子数只是改变了某堆的sg值,但并不影响我们利用sg值找规律

以下是打表程序:

const int N = 100;
int sg[N];
bool v[N];
int mex(int x)
{int i;memset(v,false,sizeof(v));for(i=1;i<=x/2;i++)v[sg[x-i]]=true;for(i=0;;i++)if(!v[i])return i;
}
int main()
{int i;sg[1]=0;for(i=2;i<N;i++)sg[i]=mex(i);for(i=1;i<N;i++)printf("sg[%d]=%d\n",i,sg[i]);return 0;
}

规律表如下:

仔细观察上述规律表,似乎有所发现,凡是相同颜色的sg值均+1递增

例如从1开始,每隔4个,sg值+1;例如从2开始,每隔2个,sg值+1;再例如从3开始,每隔8个,sg值+1;从7开始……

好像这一切跟二进制存在一定联系,于是,我们按照二进制重新打一次表

打表程序:

const int N = 100;
int sg[N];
bool v[N];
char b[10];
int mex(int x)
{int i;memset(v,false,sizeof(v));for(i=1;i<=x/2;i++)v[sg[x-i]]=true;for(i=0;;i++)if(!v[i])return i;
}
int main()
{int i;sg[1]=0;for(i=2;i<N;i++)sg[i]=mex(i);for(i=1;i<N;i++){itoa(i,b,2);printf("sg[%s]=%d\n",b,sg[i]);}return 0;
}

规律表:

这次好像有了进一步的发现,一个数n的sg值sg[n]等于n的二进制表示抹去为0的最低位及其后面的1之后的值

例如n=41时,二进制表示为101001,它的为0最低位为倒数第2位,所以抹去"01"之后就是它的sg值,故sg[41]=1010(2)=10

好了,到此为止,我们已经会算每一堆石子的sg值

要在第j堆到第k堆之间进行取石子游戏,无非就是将j,j+1,……,k-1,k这些堆的sg值进行异或运算

但每轮游戏,会改变某一堆的sg值,我们不可能每轮游戏都遍历一遍[j,k]区间,然后得到异或值,这样复杂度太高,毕竟,如果区间[j,k]等于[1,n]的话,时间复杂度为O(n^2),显然不可取,所以我们利用线段树来解决这个问题,这样复杂度只有O(nlogn)

每次改变某堆sg值时,只需将线段树该堆代表的叶子节点进行更新,而查询第j堆到第k堆时,就是对区间[j,k]进行区间查询

具体实现看代码,不懂的欢迎提出

【时间复杂度&&优化】
O(mlogn)

题目链接→FZU Problem 2240 Daxia & Suneast's problem

 Source Code

/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-9
#define LL long long
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 100005;
const int M = 100005;
const int inf = 1000000007;
const int mod = 1000000007;
struct tree
{int left,right,Xor;
}s[4*N];
int sg[N];
int solve(int x)
{while(x%2)x/=2;return x/2;
}
void push_up(int p)
{s[p].Xor=s[p*2].Xor^s[p*2+1].Xor;
}
void buildtree(int l,int r,int p)
{s[p].left=l,s[p].right=r;if(l==r){s[p].Xor=sg[l];return ;}int mid=(l+r)/2;buildtree(l,mid,p*2);buildtree(mid+1,r,p*2+1);push_up(p);
}
void update(int l,int p,int x)
{if(s[p].left==s[p].right&&s[p].left==l){s[p].Xor=x;return ;}int mid=(s[p].left+s[p].right)/2;if(l>mid)update(l,p*2+1,x);elseupdate(l,p*2,x);push_up(p);
}
int query(int l,int r,int p)
{if(l==s[p].left&&r==s[p].right)return s[p].Xor;int mid=(s[p].left+s[p].right)/2;if(l>mid)return query(l,r,p*2+1);else if(r<=mid)return query(l,r,p*2);elsereturn query(l,mid,p*2)^query(mid+1,r,p*2+1);
}
int main()
{int n,m,i,k,x,l,r;while(~scanf("%d%d",&n,&m)){for(i=1;i<=n;i++){scanf("%d",&x);sg[i]=solve(x);}buildtree(1,n,1);for(i=0;i<m;i++){scanf("%d%d%d%d",&k,&x,&l,&r);update(k,1,solve(x));if(query(l,r,1))puts("daxia");elseputs("suneast");}}return 0;
}

菜鸟成长记