題目鏈接

https://codeforces.com/contest/1110/problem/G

題解

首先，若原樹上 \(u\) 點有白子，有一個很妙的轉化是可以新建 \(3\) 個新點 \(u_1,u_2,u_3\), 并連邊 \((u,u_1)\), \((u_1,u_2)\), \((u_1,u_3)\), 并且去掉原有的這個白子，和原問題是等價的。
然后考慮初始沒有白子的情況，觀察可得若存在一個點連接至少 \(2\) 個度數 \(\ge 3\) 的點，或者度數為 \(3\) 且連接至少 \(2\) 個度數 \(\ge 2\) 的點，或者度數至少為 \(4\)，那么先手必勝。
在其余情況下，我們可以看出 \(3\) 度點的個數一定不超過 \(2\) 個，否則一定存在一個三度點連接至少 \(2\) 個二度點。那么圖一定是一條鏈在從左到右或從右到左的第二個節點處掛了個葉子這種形態。
若存在 \(2\) 個三度點，這就相當于一條長為 \((n-4)\) 且兩端初始為白的鏈。若鏈的長度為奇數，那么白方每次染距離一端為 \(2\) 的點，必勝；若鏈長為偶數，平局；若三度點個數為 \(0\) 或 \(1\)，平局。
時間復雜度 \(O(n)\).

代碼

#include<bits/stdc++.h> #define llong long long #define mkpr make_pair #define riterator reverse_iterator using namespace std;inline int read() {int x = 0,f = 1; char ch = getchar();for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}return x*f; }const int N = 2e6; struct Edge {int v,nxt; } e[(N<<1)+3]; int fe[N+3]; int du[N+3]; char a[N+3]; int dep[N+3]; int n,en;void addedge(int u,int v) {en++; e[en].v = v; du[u]++;e[en].nxt = fe[u]; fe[u] = en; }void dfs(int u,int tfa) {for(int i=fe[u]; i; i=e[i].nxt){int v = e[i].v; if(v==tfa) continue;dep[v] = dep[u]+1;dfs(v,u);} }int main() {int T; scanf("%d",&T); while(T--){scanf("%d",&n);for(int i=1; i<n; i++) {int u = read(),v = read(); addedge(u,v),addedge(v,u);}scanf("%s",a+1);for(int i=n; i>=1; i--){if(a[i]=='W'){n+=3; addedge(i,n-2),addedge(n-2,i); addedge(n-2,n-1),addedge(n-1,n-2); addedge(n-2,n),addedge(n,n-2);}}bool flg1 = false;for(int i=1; i<=n; i++){if(du[i]>=4) {flg1 = true; break;}int cnt2 = 0,cnt3 = 0;for(int o=fe[i]; o; o=e[o].nxt){int v = e[o].v;if(du[v]>=2) cnt2++;}if(du[i]>=3&&cnt2>=2) {flg1 = true; break;}}if(flg1) {puts("White");}else{int cnt3 = 0;for(int i=1; i<=n; i++) if(du[i]==3) {cnt3++;}if(cnt3<=1) {puts("Draw");}else{int u = 0,v = 0;for(int i=1; i<=n; i++) {if(du[i]==3) {if(u==0) u = i; else v = i;}}dep[u] = 0; dfs(u,0);if(dep[v]&1) {puts("Draw");}else {puts("White");}}}for(int i=1; i<=en; i++) e[i].v = e[i].nxt = 0;for(int i=1; i<=n; i++) du[i] = dep[i] = fe[i] = 0;en = 0;}return 0; }

總結

以上是生活随笔為你收集整理的Codeforces 1110G Tree-Tac-Toe (博弈论)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。