CodeForces - 1110G Tree-Tac-Toe(博弈+构造)

题目链接：点击查看

题目大意：给出一棵树状棋盘，棋盘上初始时可能为空也可能为白色，小黑和小白轮流操作，每次操作小黑可以选择一个空位置染成黑色，小白可以选择一个空位置染成白色，胜利规则和五子棋类似，有三个自己的颜色连成一条线即可胜利，问小白先手，两人依次选择最优方法下棋，最后是白色胜利，黑色胜利，还是平局

题目分析：首先我们必须知道，因为初始时的局面，加上小白先手，所以小黑必不可能胜利，假设有一个点可以让小黑成为必胜点，但小白是先手，肯定会先小黑一步去占领那个位置，所以小黑必不可能胜利，这样我们只需要分析什么时候小白必胜，剩下的局面肯定都是平局了

这里挂一个大佬的博客，我觉得分析的相当透彻了：

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

总结一下小白可以必胜的点就是：

至少有一个点的度为4

至少有一个点的度为3，且其至少有两个度为2的子节点

两端两个度为3的点，中间由奇数个点组成的单链连接而成

然后就是如何预处理棋盘上初始化的白色点，我们可以将其转化一下，这里借个图：

点1为白色节点，我们可以将其视为点A，然后连接下面的点B点C与点D

为什么可以这样构造呢？因为假设小白在点A处染白了，小黑下一步只能在点B处染色，这样一来点B，点C和点D对游戏已经毫无影响了，相当于让小白多下了一步，也达到了初始时该点即为白色的条件

那么如果小黑不在点B染色呢？ 如果小黑不在B点染色的话，小白接下来就会在B点染色，再然后小黑就会面临必输的局面，所以聪明的小黑肯定会选择在点B染色的

这个题目主要是比较难构造，以及小白必胜的条件分析不全，所以导致莫名其妙的WA，看了题解后才知道这个题目只有三种状态需要讨论，算是积累知识吧

还有一点需要提一下，这个题目不能用vector当链表用，会T掉，只能老老实实用数组模拟链表来实现，并且初始化的时候要将数组开大到两倍，因为刚才我们转换白点的关系，每个初始为白色的点可能需要和一个新点（点B）建立新边，但点C和点D就不需要真实存在了，在建立好点B后，我们只需要将点B的入度视为3即可

就这样吧，剩下的就是实现上述的结论了，上代码：

#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;//记录有多少个入度为3的节点 for(int i=1;i<=n;i++){if(in[i]>=4)return true;if(in[i]==3){int cnt=0;//记录有多少个有儿子的节点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; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 1110G Tree-Tac-Toe(博弈+构造)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。