題目鏈接：點(diǎn)擊查看

題目大意：給出一棵樹狀棋盤，棋盤上初始時(shí)可能為空也可能為白色，小黑和小白輪流操作，每次操作小黑可以選擇一個(gè)空位置染成黑色，小白可以選擇一個(gè)空位置染成白色，勝利規(guī)則和五子棋類似，有三個(gè)自己的顏色連成一條線即可勝利，問小白先手，兩人依次選擇最優(yōu)方法下棋，最后是白色勝利，黑色勝利，還是平局

題目分析：首先我們必須知道，因?yàn)槌跏紩r(shí)的局面，加上小白先手，所以小黑必不可能勝利，假設(shè)有一個(gè)點(diǎn)可以讓小黑成為必勝點(diǎn)，但小白是先手，肯定會(huì)先小黑一步去占領(lǐng)那個(gè)位置，所以小黑必不可能勝利，這樣我們只需要分析什么時(shí)候小白必勝，剩下的局面肯定都是平局了

這里掛一個(gè)大佬的博客，我覺得分析的相當(dāng)透徹了：

https://www.cnblogs.com/Itst/p/10356243.html

總結(jié)一下小白可以必勝的點(diǎn)就是：

至少有一個(gè)點(diǎn)的度為4

至少有一個(gè)點(diǎn)的度為3，且其至少有兩個(gè)度為2的子節(jié)點(diǎn)

兩端兩個(gè)度為3的點(diǎn)，中間由奇數(shù)個(gè)點(diǎn)組成的單鏈連接而成

然后就是如何預(yù)處理棋盤上初始化的白色點(diǎn)，我們可以將其轉(zhuǎn)化一下，這里借個(gè)圖：

點(diǎn)1為白色節(jié)點(diǎn)，我們可以將其視為點(diǎn)A，然后連接下面的點(diǎn)B點(diǎn)C與點(diǎn)D

為什么可以這樣構(gòu)造呢？因?yàn)榧僭O(shè)小白在點(diǎn)A處染白了，小黑下一步只能在點(diǎn)B處染色，這樣一來點(diǎn)B，點(diǎn)C和點(diǎn)D對(duì)游戲已經(jīng)毫無影響了，相當(dāng)于讓小白多下了一步，也達(dá)到了初始時(shí)該點(diǎn)即為白色的條件

那么如果小黑不在點(diǎn)B染色呢？?如果小黑不在B點(diǎn)染色的話，小白接下來就會(huì)在B點(diǎn)染色，再然后小黑就會(huì)面臨必輸?shù)木置?#xff0c;所以聰明的小黑肯定會(huì)選擇在點(diǎn)B染色的

這個(gè)題目主要是比較難構(gòu)造，以及小白必勝的條件分析不全，所以導(dǎo)致莫名其妙的WA，看了題解后才知道這個(gè)題目只有三種狀態(tài)需要討論，算是積累知識(shí)吧

還有一點(diǎn)需要提一下，這個(gè)題目不能用vector當(dāng)鏈表用，會(huì)T掉，只能老老實(shí)實(shí)用數(shù)組模擬鏈表來實(shí)現(xiàn)，并且初始化的時(shí)候要將數(shù)組開大到兩倍，因?yàn)閯偛盼覀冝D(zhuǎn)換白點(diǎn)的關(guān)系，每個(gè)初始為白色的點(diǎn)可能需要和一個(gè)新點(diǎn)（點(diǎn)B）建立新邊，但點(diǎn)C和點(diǎn)D就不需要真實(shí)存在了，在建立好點(diǎn)B后，我們只需要將點(diǎn)B的入度視為3即可

就這樣吧，剩下的就是實(shí)現(xiàn)上述的結(jié)論了，上代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e6+100;int n;int tot;int node[N];int head[N];int nex[N];int in[N];void addedge(int u,int v) {node[tot]=v;nex[tot]=head[u];head[u]=tot++;node[tot]=u;nex[tot]=head[v];head[v]=tot++;in[u]++;in[v]++; }bool check() {int ans=0;//記錄有多少個(gè)入度為3的節(jié)點(diǎn) for(int i=1;i<=n;i++){if(in[i]>=4)return true;if(in[i]==3){int cnt=0;//記錄有多少個(gè)有兒子的節(jié)點(diǎn)for(int j=head[i];j!=-1;j=nex[j]){int u=i;int v=node[j];if(in[v]>=2)cnt++;} if(cnt>=2)return true;ans++;}}if(ans==2&&(n&1))return true;return false; }void init() {tot=0;for(int i=1;i<=n;i++){head[i]=-1; in[i]=0;} }int main() { // freopen("input.txt","r",stdin);int w;cin>>w;while(w--){scanf("%d",&n);init();for(int i=1;i<n;i++){int a,b;scanf("%d%d",&a,&b);addedge(a,b);}string s;cin>>s;if(n<=2){cout<<"Draw"<<endl;continue;}else if(n==3){int cnt=0;for(int i=0;i<s.size();i++)if(s[i]=='W')cnt++;if(cnt>=2)cout<<"White"<<endl;elsecout<<"Draw"<<endl;continue;}for(int i=0;i<s.size();i++){if(s[i]=='W'){++n;head[n]=-1;addedge(i+1,n);in[n]=3;}}if(check())cout<<"White"<<endl;elsecout<<"Draw"<<endl;}return 0; }

?

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。