题目:

  P3727曼哈顿计划E

分析:

  大长题面容易给人一种不可做的错觉,但是这题考的知识点都是我们熟悉的。

  稍加分析我们可以得到,我们可以把每个点当成一个单独的游戏,如果k=1,就是简单的nim游戏,这样,当多个游戏放在一起的时候,我们就可以根据一条链的权值异或和来判断必胜必败。

  这个给我们启发,根据SG定理(应该是这个定理?)当我们选一条链,根据这条链上所有点的SG函数的异或和,可以判断胜负。

  所以我们可以对于每个k想办法求点的sg函数,就可以用点分治解决这个题。

  怎么求sg函数?(打表找规律啊),或者如果你有办法推也可以。

 代码:

 #include<bits/stdc++.h>
#define ms(a,x) memset(a,x,sizeof(a))
using namespace std;
const int N=,M=1e7;
struct node{int y,nxt;}e[N*];
int t,n,k,s,c=,hs,pd,nt,h[N];
int w[N],siz[N],vis[N],tp[N],tt[N];
void add(int x,int y){
e[++c]=(node){y,h[x]};h[x]=c;
e[++c]=(node){x,h[y]};h[y]=c;
} int sg1(int x){return x;}
int sg2(int x){return (x+)%(s+)?x&:;}
int sg3(int x){return x/s;}
int sg4(int x){
switch(x%){
case : return x-;
case : return x+;
default : return x;
}
} void init(){
ms(h,);ms(vis,);c=;
} void gs(int x,int fa){
siz[x]=;
for(int i=h[x],y;i;i=e[i].nxt)
if((y=e[i].y)!=fa&&!vis[y])
gs(y,x),siz[x]+=siz[y];
} int gg(int x,int fa){
for(int i=h[x],y;i;i=e[i].nxt)
if((y=e[i].y)!=fa&&!vis[y]&&siz[y]>=hs)
return gg(y,x);return x;
} void dfs(int x,int fa,int o){
tt[nt]=x;tp[nt++]=o;
for(int i=h[x],y;i;i=e[i].nxt)
if((y=e[i].y)!=fa&&!vis[y]) dfs(y,x,o^w[y]);
} struct Hash{
static const int P1=,P2=;
int h1(int x){return x%P1;}
int h2(int x){return x%P2;}
int t1[P1],t2[P2],st[N],top;
Hash(){ms(t1,-);ms(t2,-);}
int find(int x){
return t1[h1(x)]==x||t2[h2(x)]==x;
} void insert(int x){
if(find(x)) return ;
int h=h2(x);st[top++]=x;
if(t2[h]==-) t2[h]=x;
else while(~x){
h=h1(x);swap(x,t1[h]);
if(x==-) return ;
h=h2(x);swap(x,t2[h]);
}
} void del(int x){
if(t1[h1(x)]==x) t1[h1(x)]=-;
else t2[h2(x)]=-;
} void clear(){
while(top) del(st[--top]);
}
}H;void dc(int x){
gs(x,);hs=siz[x]>>;int g;
g=gg(x,);vis[g]=;H.insert();
for(int i=h[g],y;i;i=e[i].nxt)
if(!vis[y=e[i].y]){
nt=;dfs(y,,w[y]);
for(int j=;j<nt;j++)
if(H.find(w[g]^tp[j]))
{pd=;break;}
for(int j=;j<nt;j++)
H.insert(tp[j]);
} H.clear();
for(int i=h[g],y;i&&!pd;i=e[i].nxt)
if(!vis[y=e[i].y]) dc(y);return ;
} int main(){
scanf("%d",&t);while(t--){
init();scanf("%d",&n);
for(int i=,y,x;i<n;i++)
scanf("%d%d",&x,&y),add(x,y);
for(int i=;i<=n;i++)
scanf("%d",&w[i]);scanf("%d",&k);
int (*sg)(int);
if(k==) sg=sg1;
else if(k==) scanf("%d",&s),sg=sg2;
else if(k==) scanf("%d",&s),sg=sg3;
else sg=sg4;pd=;
for(int i=;i<=n;i++)
if(!(w[i]=sg(w[i]))) pd=;
if(!pd) dc();
puts(pd?"Mutalisk ride face how to lose?":
"The commentary cannot go on!");
} return ;
}

博弈论+点分治

最新文章

  1. Mysql5.0没有nvarchar,national
  2. NOI 1.5 42:画矩形
  3. Java Hello World例子和添加按钮事件与功能
  4. hdu 1860统计字符
  5. 【代码】verilog之:电子钟
  6. Android开发常见问题
  7. 在XAF应用程序使用现有的数据库?
  8. Python求算数平方根和约数
  9. Delphi- 一些H8记录
  10. xcode 自动添加注释,生成文档
  11. 【蒙地卡罗法求PI】
  12. 玩转SSH(四):Struts + Spring + MyBatis
  13. JAVA课程设计-猜数游戏 201521123017
  14. sublime text 3 ctrl+b浏览器启动html
  15. pxe自动化批量安装系统(Centos7)
  16. mysql数据库--explain(查询表是否走索引)各个字段含义
  17. BZOJ 1510: Kra-The Disks
  18. Java中的Iterable与Iterator详解
  19. C# 获取外网IP地址
  20. 如何用Python编写一个聊天室

热门文章

  1. 简单重载运算符in priority_queue By cellur925
  2. 一个致命的 Redis 命令,导致公司损失 400 万
  3. 结束线程方法2 Java提供的中断机制
  4. python使用rabbitmq实现简单的消息转发
  5. php中3DES加密技术
  6. Ice-cream Tycoon9(线段树)
  7. spring mvc添加静态资源访问时@Controller无效的解决
  8. 初学者应该怎么学习前端?web前端的发展路线大剖析!
  9. 1、Centos7 python2.7和yum完全卸载及重装
  10. Java多态的应用