[删边游戏] POJ 3710 Christmas Game

2019-11-06 08:56:29

字体：大中小

来源：转载

供稿：网友

详见组合游戏略述——浅谈SG游戏的若干拓展及变形贾志豪对于树的删边问题可证叶子节点的 SG 值为 0 中间节点的 SG 值为它的所有子节点的 SG 值加 1 后的异或和

对于这道题通过分析发现了如下奇妙的性质：

对于长度为奇数的环，去掉其中任意一个边之后，剩下的两个链长度同奇偶，抑或之后的 SG 值不可能为奇数，所以它的 SG 值为 1对于长度为偶数的环，去掉其中任意一个边之后，剩下的两个链长度异奇偶，抑或之后的 SG 值不可能为 0，所以它的 SG 值为 0

所以我们可以去掉所有的偶环，将所有的奇环变为长短为 1 的链

这里写图片描述

#include<cstdio>#include<cstdlib>#include<algorithm>#include<cstring>#define cl(x) memset(x,0,sizeof(x))using namespace std;inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}inline int read(int &x){ char c=nc(),b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; else if (c==EOF) return 0; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b; return 1;}const int N=105;const int M=505;struct edge{ int u,v,next;}G[M<<1];int head[N],inum=1;inline void add(int u,int v,int p){ G[p].u=u; G[p].v=v; G[p].next=head[u]; head[u]=p;}int flag[N],depth[N],fat[N],sg[N];int d;#define V G[p].vinline void dfs(int u,int fa){ for (int p=head[u];p;p=G[p].next) if (p!=(fa^1)){ if (!depth[V]){ depth[V]=depth[u]+1; fat[V]=u; dfs(V,p); if (flag[u]) return; if (d) sg[u]^=d&1?1:0,d=0; else sg[u]^=sg[V]+1; }else if (depth[V]<depth[u]){ int t=u; while (t!=V) flag[t]=1,t=fat[t]; d=depth[u]-depth[V]+1; return; } }}int main(){ int T,n,m,Sg,iu,iv; freopen("t.in","r",stdin); freopen("t.out","w",stdout); while (read(T)){ Sg=0; while (T--){ read(n); read(m); for (int i=1;i<=m;i++) read(iu),read(iv),add(iu,iv,++inum),add(iv,iu,++inum); depth[1]=1; dfs(1,0); Sg^=sg[1]; cl(head); inum=1; cl(sg); cl(depth); cl(fat); cl(flag); } PRintf("%s/n",Sg?"Sally":"Harry"); } return 0;}

上一篇：原型模式

下一篇：来了！！小鱼一键重装系统最全面科普！！！

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注