文章目录

• 题目描述
• 解析
• 代码

题目描述

解析

首先，这道题的情境对二人来说是不对称的，所以不太好使用SG函数来求解
但直观上也好考虑
利用树的递归性质可以求出每个节点的颜色是否确定
并确定根的颜色是否确定
如果确定是红就随便涂
确定是蓝就-1
关键在于不确定的情况
我的第一感觉是一直往下递归寻找不确定的节点
最后递归到无色的叶子就是可以涂的
这的确是对的，但遗漏了一种可能！
举个例子来说明：

此时看起来2结点已经确定是蓝色，所以涂6、7是无用的
但是，如果小红涂了6或7,小蓝必须应，也涂二者其一，否则就会失去2结点
此时小红再回来涂3，依然可以获胜

总结一下就是：当某个结点蓝色只比红色多一时（前提是其父亲也满足该条件或还未确定，它也是可以递归尝试涂色的

当然，如果蓝色比红色多超过1，你就是涂小蓝也不会理你

这样这道题才算彻底解决

代码

#include<bits/stdc++.h> #define ll long long using namespace std; const int N=4e5+100; int n,t; struct node{int to,nxt; }p[N*2]; int fi[N],cnt=-1; void addline(int x,int y){p[++cnt]=(node){y,fi[x]};fi[x]=cnt; } int col[N],out[N]; int op[N]; int find(int x){if(col[x]) return op[x]=col[x];else if(out[x]==0) return op[x]=0;int jd=0;for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;jd+=find(to);}op[x]=jd;if(op[x]>0) return 1;else if(op[x]<0) return -1;else return 0; } int q[N],tot; void solve(int x){if(!out[x]) {q[++tot]=x;return;}for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(op[to]==0||(op[to]==-1&&out[to])) solve(to);} } int main(){scanf("%d",&t);while(t--){cnt=-1;memset(fi,-1,sizeof(fi));memset(out,0,sizeof(out));scanf("%d",&n);for(int i=1;i<=n;i++){int a;scanf("%d",&a);if(a) addline(a,i),out[a]++;}for(int i=1;i<=n;i++){int a;scanf("%d",&a);if(a==0) col[i]=1;else if(a==1) col[i]=-1;else col[i]=0;}int jd=find(1); if(jd<0) printf("-1\n");else if(jd>0){tot=0;for(int i=1;i<=n;i++){if(!out[i]&&!col[i]) tot++;}printf("%d ",tot);for(int i=1;i<=n;i++){if(!out[i]&&!col[i]) printf("%d ",i);}printf("\n");}else{tot=0;solve(1);sort(q+1,q+1+tot);printf("%d ",tot);for(int i=1;i<=tot;i++) printf("%d ",q[i]);printf("\n");}} } /* 3 2 0 1 -1 -1 2 0 1 -1 1 26 0 1 1 1 2 2 2 3 3 3 3 3 4 4 4 13 13 13 14 14 14 14 14 15 15 15 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 1 -1 -1 -117 0 1 1 1 4 5 5 5 6 6 6 7 7 7 8 8 8 -1 0 1 -1 -1 -1 -1 -1 0 -1 -1 1 -1 -1 0 -1 -1 */

总结

以上是生活随笔为你收集整理的YBTOJ：红与蓝（博弈论）的全部内容，希望文章能够帮你解决所遇到的问题。

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