牛客练习赛63 F.牛牛的树行棋(博弈 SG函数)

  • 时间:
  • 浏览:
  • 来源:互联网

题目链接:https://ac.nowcoder.com/acm/contest/5531/F

牛牛的树行棋

  • 前置知识
  • 思路
  • 代码

前置知识

这道题目需要博弈论中的SG函数的知识,这里就不多赘述。主要是用到以下结论:

  1. 若当前局面的 SG 值为 0,先手必败,否则先手必胜。
  2. 若一个游戏是多个独立游戏组成的,那么当前局面的 SG 值是多个独立游戏 SG 值的异或和。

思路

  1. 首先可以明确的一点,棋盘中的叶子结点无后继状态,所以SG函数对应的值为0。
  2. 经过推断可以推出,一个结点的SG值等于其所有子节点的最大的SG值加一,可以利用dfs算出每个结点的SG值。
  3. 此时可以通过上述结论2判断先手必胜或者必败,即判断所有结点SG值的异或值ans是否为0,如果ans值为0则先手必败,否则先手必胜。
  4. 如果先手必胜,那么就要求方案数。因为只有 SG 值为 0 的局面是必败的,第一次移动之后的局面 SG 值一定要等于 0。假设当前移动的棋子的SG函数值为sg[u],那么只要把这个棋子移动到子树中SG函数值为 x [ u ] x[u] x[u] xor a n s ans ans的结点,那么新局面的SG函数值为 a n s ans ans xor x [ u ] x[u] x[u] xor x [ u ] x[u] x[u] xor x [ u ] x[u] x[u] xor a n s ans ans = 0,这也就进入了必败态。并用cnt数据记录SG值出现的次数。

代码

#include<bits/stdc++.h>
using namespace std;
const int INF=2147483647;
const int maxn=5e5+10;

vector<int> e[maxn];
int sg[maxn], cnt[1<<20];
int sum,ans;

void dfs1(int u,int fa)
{
	for(auto v:e[u]){
		if(v==fa) continue;
		dfs1(v,u);
		sg[u]=max(sg[u],sg[v]+1);
	}
	ans^=sg[u];
}

void dfs2(int u,int fa)
{
	cnt[sg[u]]++;
	int k=ans^sg[u];
	sum+=cnt[k];
	for(auto v:e[u]){
		if(v==fa) continue;
		dfs2(v,u);
	}
	cnt[sg[u]]--;
}

int main()
{
	int n;
	scanf("%d",&n);
	while(--n){
		int u,v;
		scanf("%d %d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs1(1,0);
	if(ans){
		puts("YES");
		dfs2(1,0);
		printf("%d\n",sum);
	}
	else puts("NO");
	return 0;
}

本文链接http://www.dzjqx.cn/news/show-617118.html