题目传送门:http://pan.baidu.com/s/1hsLh92W
OJ传送门:http://oi.cdshishi.net:8080/Problem/1712
这一道题,我一眼看到的时候,也是“啊”的。博弈论?不会啊QAQ
最后只能打了暴力,结果还打错了QAQ
来说一说正解。
我们定义三种节点:
1.无名必胜
2.有名必胜
3.先手必胜
再来讨论一下这三种节点间的关系:
假如一个节点的儿子中,1、2两种类型的节点一样多,则为类型3
否则,1、2哪种多,该节点就是那种节点
于是搞一个树形DP,就可以搞出根节点的类型
显然,如果是类型3,则无解
如果是类型2,则只有部分节点可选
如果是类型1,则全部的叶子结点都可选
另外,本题还要注意,因为非叶子结点的颜色,最终会取决于它儿子节点的颜色
所以,第一步走的节点,一定是叶子结点,否则,并没有什么卵用QAQ
#include<iostream> #include<cstdio> #include<vector> #include<algorithm> using namespace std; const int MAXN = 100000+9; int n,vout,que[MAXN],type[MAXN],num[MAXN][3]; vector<int> G[MAXN]; inline int read(){ char c=getchar(); int buf=0,f=1; while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();} return buf*f; } inline void init(){ n = read(); for (int i=1;i<=n;i++) G[i].clear(), num[i][0] = num[i][1] = num[i][2] = 0; for (int i=1;i<=n;i++) G[read()].push_back(i); for (int i=1;i<=n;i++) type[i] = read() + 1; int fro,bak; que[fro=bak=1] = 1; while (fro < n) { int w = que[bak++]; for (int i=0;i<(int)G[w].size();i++) que[++fro] = G[w][i]; } } void GetAns(int w){ if ((int)G[w].size() == 0) { if (type[w] == 0) que[++vout] = w; } else { int t = num[w][2] - num[w][1]; if (t <= 1 && t >= 0) for (int i=0;i<(int)G[w].size();i++) GetAns(G[w][i]); } } int main(){ freopen("ah.in","r",stdin); freopen("ah.out","w",stdout); int T; cin>>T; while (T--) { init(); for (int k=n,i=que[k];k;i=que[--k]){ if ((int)G[i].size() == 0) continue; else { for (int j=0;j<(int)G[i].size();j++) num[i][type[G[i][j]]]++; if (num[i][2] == num[i][1]) type[i] = 0; else if (num[i][1] > num[i][2]) type[i] = 1; else type[i] = 2; } } if (type[1] == 1) { int tot = 0; for (int i=1;i<=n;i++) if ((int)G[i].size() == 0 && type[i] == 0) que[++tot] = i; printf("%d ",tot); for (int i=1;i<=tot;i++) printf("%d ",que[i]); cout<<endl; } else if (type[1] == 0) {vout = 0, GetAns(1); sort(que+1,que+1+vout); cout<<vout<<' '; for (int i=1;i<=vout;i++) cout<<que[i]<<' '; cout<<endl;} else printf("-1\n"); } return 0; }