題目鏈接

https://atcoder.jp/contests/agc033/tasks/agc033_c

題解

終于會做點最簡單的博弈論了……
首先題目中操作的含義就是選定一個點，把所有不是這個點的葉子刪掉（如果這個點不是葉子就刪所有葉子）。
對于任何一棵點數不少于\(3\)的樹，一定存在一個點（比如非葉子節點），使得對該點操作之后直徑減少\(2\)；同時一定存在一個點（比如直徑的端點），使得對該點操作后直徑減少\(1\)；同時不存在任何一種操作使得直徑發生其他的變化。因此這是一個Bash博弈的模型，答案與直徑長度模\(3\)的值有關。
設直徑長度（點數）為\(l\). 若\(l=1\)則先手必勝，\(l=2\)則后手必勝。后面就變成了剛才討論的情況，因此當且僅當直徑長度\(\mod 3=2\)時后手必勝。
時間復雜度\(O(n)\).

代碼

#include<bits/stdc++.h> #define llong long long using namespace std;inline int read() {int x = 0,f = 1; char ch = getchar();for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}return x*f; }const int N = 2e5; struct Edge {int v,nxt; } e[(N<<1)+3]; int fe[N+3]; int fa[N+3]; int len[N+3]; int n,en,mx;void addedge(int u,int v) {en++; e[en].v = v;e[en].nxt = fe[u]; fe[u] = en; }void dfs(int u) {for(int i=fe[u]; i; i=e[i].nxt){int v = e[i].v; if(v==fa[u]) continue;fa[v] = u; dfs(v);mx = max(mx,len[u]+len[v]+1);len[u] = max(len[u],len[v]+1);} }int main() {scanf("%d",&n);for(int i=1; i<n; i++) {int u,v; scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u);}dfs(1);if(mx%3==1) {puts("Second");}else {puts("First");}return 0; }

總結

以上是生活随笔為你收集整理的AtCoder AGC033C Removing Coins (博弈论)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。