注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3729]Gty的游戏  

2014-11-20 18:45:16|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3729: Gty的游戏

第二道博弈论题
题目里没说清楚的两点:1.没法移动的人输 2.树的根是①号点
一开始读错题挂了好久= =、
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<map>
using namespace std;
const int N = 1E5+10;
struct Point{
Point(){next = NULL;}
int d;Point *next;
void push(int a){
Point *l = new Point;
l->d = a;l->next = next;
next = l;
}
}point[N];
int n,m,MZ,MOD;
int data[N],list[N*2];
short type[N];
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;
if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}return re*fh;
}
map<int,int>bh;
void dfs(int x){
list[++list[0]] = x;
bh[x] = x;
for(Point *i = point[x].next;i!=NULL;i=i->next)
if(!bh[i->d]) type[i->d] = type[x]^1,dfs(i->d);
list[++list[0]] = -x;
}
struct Node{
Node();
int d,sg[2];
short t;
Node *fa,*ch[2];
bool pl(){return this == fa->ch[0]?0:1;}
void count(){
sg[1] = ch[0]->sg[1] ^ ch[1]->sg[1];
sg[0] = ch[0]->sg[0] ^ ch[1]->sg[0];
sg[t] ^= d;
}
}*null,house[N],*pos[N][2];int hn;
Node *newNode(){
if(hn >= N)return new Node();
house[hn]=Node();return &house[hn++];
}
Node::Node(){fa = ch[0] = ch[1] = null; d = sg[0] = sg[1] = 0;}

struct Splay{
Node *ROOT;
Splay(){
ROOT = null = newNode();
*null = Node();
}
Node *Build(int l,int r){
if(r < l)return null;
int mid = (l+r)/2;
Node *ro = newNode();
if(list[mid]>0){
ro->d = data[list[mid]];
pos[list[mid]][0] = ro;
}else pos[-list[mid]][1] = ro;
ro->t = type[abs(list[mid])];
if(l<r){
ro->ch[0] = Build(l,mid-1);
if(ro->ch[0])ro->ch[0]->fa = ro;
ro->ch[1] = Build(mid+1,r);
if(ro->ch[1])ro->ch[1]->fa = ro;
}ro->count();
return ro;
}
void splay(Node *r,Node *tar = null){
for(;r->fa!=tar;rotate(r))
if(r->fa->fa!=tar)
rotate(r->pl()==r->fa->pl()?r->fa:r);
}
void rotate(Node *k){
Node *r = k->fa;if(r==null||k==null)return;
int x = k->pl()^1;
r->ch[x^1] = k->ch[x];
r->ch[x^1]->fa = r;
if(r->fa!=null)r->fa->ch[r->pl()] = k;
else ROOT = k;
k->fa = r->fa;r->fa = k;
k->ch[x] = r;
r->count();k->count();
}
void pack_suc(Node *r){
splay(r);
r = r->ch[1];
while(r->ch[0]!=null)r = r->ch[0];
splay(r,ROOT);
}
void insert(int x, int a, int d){
pack_suc(pos[x][0]);
Node *r;
pos[a][0] = r = newNode();pos[a][1] = newNode();
r->d=d;
r->ch[1] = pos[a][1];
r->ch[1]->fa = r;
r->t = type[a];
r->count();
ROOT->ch[1]->ch[0] = r;
r->fa = ROOT->ch[1];
splay(r);//?
}
void change(int x, int d){
splay(pos[x][0]);
ROOT->d=d;
ROOT->count();
}
int ask(int x){
splay(pos[x][0]);
splay(pos[x][1],ROOT);
return ROOT->ch[1]->ch[0]->sg[type[x]^1];
}
}tree;
int main(){
//freopen("in.txt","r",stdin);
int i,j,a,b,tmp;
n = scan();MOD = scan()+1;
for(i=1;i<=n;i++)data[i] = scan()%MOD;
for(i=1;i<n;i++){
a = scan();b = scan();
point[a].push(b);
point[b].push(a);
}
dfs(1);
tree.ROOT = tree.Build(1,list[0]);
//printf("%d",list[0]);
//for(i=1;i<=n;i++)printf("%d",data[i]);
//for(i=1;i<=list[0];i++)printf("%2d ",list[i]); printf("\n");
//for(i=1;i<=n;i++)printf("%d ",type[i]); printf("\n");
m = scan();
for(i=1;i<=m;i++){
tmp = scan();
switch(tmp){
case 1:{
a = scan()^MZ;
a = bh[a];
a = tree.ask(a);
if(a == 0)printf("GTY\n");
else printf("MeiZ\n");
//printf("%d ",a);
//printf("%d",a);
if(a)MZ++;
break;
}
case 2:{//change
a = scan()^MZ;b = (scan()^MZ)%MOD;
a = bh[a];
tree.change(a,b);
break;
}
case 3:{//add son
a = scan()^MZ;
a = bh[a];
bh[(scan()^MZ)] = ++n;
data[n] = (scan()^MZ)%MOD;
type[n] = type[a] ^1;
tree.insert(a,n,data[n]);
break;
}
}
}
return 0;
}

题解:
博弈论+Splay维护dfs序
想会做这道题首先要知道两个Nim游戏的经典变形。
第一个是加入一次只能选m个的限制。
第二个是“阶梯博弈”(POJ 1704),就是有一个楼梯,每次可以把一阶的任意个棋子移到下面一个台阶,不能移动(0号台阶不能向下移动)的玩家输。

第一个问题的解决方法是把所有的数 mod (m+1),因为显然加入这个限制之后每个子游戏的sg函数值变成了sg(n) = n%(m+1)。
第二个问题可以转换成Nim游戏,方法是如果对方移动了偶数层的棋子,那么你下一步可以把他刚移动的棋子再向下移动。这样偶数层上的棋子就可以视为不存在了,如果把一个奇数层的棋子移动到下一层,那么我们把它看成消失了,这样就变成了Nim游戏,也就是说只用考虑奇数层的棋子sg函数的异或值就行了。
在树上也同理,对于任意一棵子树,如果把根深度定义为0,那么也只要考虑深度为奇数的异或和。
题目就变成了支持动态修改,加点,维护子树信息,随便用个什么数据结构维护一下dfs序就行了。
  评论这张
 
阅读(445)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017