M_sea

CF1110G Tree-Tac-Toe
CodeForcesLuogu分析不会做.jpg以下所有图片均来自官方题解。首先初始就为白色的点不太好搞,考虑怎么...
扫描右侧二维码阅读全文
16
2019/05

CF1110G Tree-Tac-Toe

CodeForces

Luogu

分析

不会做.jpg

以下所有图片均来自官方题解。


首先初始就为白色的点不太好搞,考虑怎么样把它当成无色点。

假设 $A$ 是一个白色点,我们在它上面挂 $3$ 个新点:

可以发现这样子对游戏胜负没有影响。

可以这么考虑:如果白方把 $A$ 涂白了,那么黑方只能把 $B$ 涂黑。所以这就相当于多用一轮回到了给定的状态。


现在是一个没有颜色的树,考虑这上面的胜负情况。

显然黑色不可能赢,也就是说只可能白色获胜或者平局。

考虑白色获胜的情况有哪些:

  • 存在一个节点,满足它的度数 $\geq 4$ 。

白色染最上面那个节点,然后就赢了。

  • 存在一个节点,满足它的度数 $=3$ ,并且至少有 $2$ 个非叶子节点与它相邻。

白色染最上面那个点,然后在黑色染完之后再染一个相邻的非叶子节点,然后就赢了。


剩下的情况就只有一条链,左右两边可能挂了两个节点。

可以猜想,这种情况是平局。然后你就会 WA on #2 。

考虑下面这种情况:

可以发现这也是白色赢,原因是我们可以把上面的图看成下面的样子。

进一步扩展一下就是这样子:

  • 如果树的形态是一条链左右两边各挂了两个节点,并且节点个数为奇数,那么白色获胜。

获胜方法就不讲了


另外可以证明,除了以上 $3$ 种情况都是平局。


可能讲的比较繁杂,可以再看看 $\color{black}{\mathrm{I}}\color{red}{\mathrm{tst}}$ 的题解

具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=2000000+10;

struct Edge { int v,nxt; } e[N<<1];
int head[N],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}

int n,deg[N];
char str[N];

int main() {
    int T=read();
    while (T--) {
        memset(head,0,sizeof(int)*(n+1)),cnt=0;
        memset(deg,0,sizeof(int)*(n+1));
        
        n=read();
        for (re int i=1;i<n;++i) {
            int u=read(),v=read();
            addEdge(u,v),addEdge(v,u);
            ++deg[u],++deg[v];
        }
        scanf("%s",str+1);
        
        if (n<3) { puts("Draw"); continue; }
        if (n==3) {
            int sum=0;
            for (re int i=1;i<=3;++i) sum+=(str[i]=='W');
            puts(sum>=2?"White":"Draw");
            continue;
        }
        
        for (re int i=1;i<=n;++i) {
            if (str[i]!='W') continue;
            ++n,head[n]=0;
            addEdge(i,n),addEdge(n,i);
            ++deg[i],deg[n]=3;
        }
        
        int flag=0,s=0;
        for (re int i=1;i<=n;++i) {
            if (deg[i]>3) { flag=1; break; }
            if (deg[i]==3) {
                int sum=0;
                for (re int j=head[i];j;j=e[j].nxt)
                    if (deg[e[j].v]>=2) ++sum;
                if (sum>=2) { flag=1; break; }
                ++s;
            }
        }
        if (s==2&&(n&1)) flag=1;
        puts(flag?"White":"Draw");
    }
    return 0;
}
最后修改:2019 年 05 月 16 日 11 : 41 AM

发表评论