C/C++教程

Atcoder-AGC033C

本文主要是介绍Atcoder-AGC033C,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

看到这道题,是个博弈论,没见过树上的,于是想到在数列里的博弈论,又联想到树的特殊形式————链。

于是我们来讨论一下链的情况(对于没有硬币的点,我们就视为它被删掉了):


讨论链的情况

发现若是选择两端的点,顶点数会减一;若是选择中间的点,顶点数会减二。

现在我们站在链的角度来思考在树上选择的情况,一颗树可以看成一条链且在某些顶点上有分支的图。我们再来以这种方式来选点找找规律,发现树上的点删着删着最后总会变成一条链,且这条链是最长链的子链,于是我们把看这棵树的形式转换为其最长链(直径)且在某些顶点上有分支的图:


例子

通过手玩这个例子后发现,我们若是选最长链两端的点,最长链顶点数会减一;若是选择非最长链两端的点,最长链顶点数会减二,其余的分支会因为持续的选点而被删完。

所以发现,在树上的问题被我们转化成了在链上的问题,妙哉!

讨论完了删点的变化情况,我们再来讨论一下必胜条件:若最长链上有 \(i-1\)\(i-2\) 个点时均必胜,则最长链上有 \(i\) 个点时必败,否则必胜,特殊的,若最长链上有 \(1\) 个点时必胜,有 \(2\) 个点时必败。
打表发现用树的最长链上点的个数 \(\mod 3\) ,若等于 2 后手胜,否则先手胜。

Code:

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 2e5 + 5;

int n, x, y, fir, sec;
int la[N], en[N << 1], ne[N << 1], idx;

void add(int x, int y) {
	en[ ++ idx] = y; 
	ne[idx] = la[x];
	la[x] = idx;
}

void dfs(int u, int f, int step) {
	for (int i = la[u]; i; i = ne[i]) {
		int v = en[i];
		if(v == f) continue;
		if(fir < step) fir = step, sec = v; dfs(v, u, step + 1);
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin >> n;
	for (int i = 1; i < n; ++ i ) cin >> x >> y, add(x, y), add(y, x);
	dfs(1, 0, 1); dfs(sec, 0, 1); 
	if((fir + 1) % 3 == 2) cout << "Second";
	else cout << "First";
	return 0;
}
这篇关于Atcoder-AGC033C的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!