绍兴住房和城乡建设厅网站,wordpress+百度云图安装,顺德做外贸网站,网站模板化文章目录题目描述解析代码题目描述 解析
首先#xff0c;这道题的情境对二人来说是不对称的#xff0c;所以不太好使用SG函数来求解 但直观上也好考虑 利用树的递归性质可以求出每个节点的颜色是否确定 并确定根的颜色是否确定 如果确定是红就随便涂 确定是蓝就-1 关键在于不…
文章目录题目描述解析代码题目描述 解析
首先这道题的情境对二人来说是不对称的所以不太好使用SG函数来求解 但直观上也好考虑 利用树的递归性质可以求出每个节点的颜色是否确定 并确定根的颜色是否确定 如果确定是红就随便涂 确定是蓝就-1 关键在于不确定的情况 我的第一感觉是一直往下递归寻找不确定的节点 最后递归到无色的叶子就是可以涂的 这的确是对的但遗漏了一种可能 举个例子来说明 此时看起来2结点已经确定是蓝色所以涂6、7是无用的 但是如果小红涂了6或7,小蓝必须应也涂二者其一否则就会失去2结点 此时小红再回来涂3依然可以获胜
总结一下就是当某个结点蓝色只比红色多一时前提是其父亲也满足该条件或还未确定它也是可以递归尝试涂色的
当然如果蓝色比红色多超过1你就是涂小蓝也不会理你
这样这道题才算彻底解决
代码
#includebits/stdc.h
#define ll long long
using namespace std;
const int N4e5100;
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 jd0;for(int ifi[x];~i;ip[i].nxt){int top[i].to;jdfind(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 ifi[x];~i;ip[i].nxt){int top[i].to;if(op[to]0||(op[to]-1out[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 i1;in;i){int a;scanf(%d,a);if(a) addline(a,i),out[a];}for(int i1;in;i){int a;scanf(%d,a);if(a0) col[i]1;else if(a1) col[i]-1;else col[i]0;}int jdfind(1); if(jd0) printf(-1\n);else if(jd0){tot0;for(int i1;in;i){if(!out[i]!col[i]) tot;}printf(%d ,tot);for(int i1;in;i){if(!out[i]!col[i]) printf(%d ,i);}printf(\n);}else{tot0;solve(1);sort(q1,q1tot);printf(%d ,tot);for(int i1;itot;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
*/
