21-5-22校賽J 下圍棋

給出一個(gè)節(jié)點(diǎn)個(gè)數(shù)為n的樹，其根節(jié)點(diǎn)為1，兩個(gè)人輪流操作，每一次操作可以選擇一個(gè)非根節(jié)點(diǎn)，刪除這個(gè)節(jié)點(diǎn)及其子樹，當(dāng)一個(gè)人無(wú)法進(jìn)行操作的時(shí)候，他就輸?shù)袅恕?wèn)后手是必勝還是必?cái)　?/p>

一個(gè)樹上的博弈問(wèn)題，只能說(shuō)自己的sg函數(shù)生疏了，也可能是根本沒(méi)有掌握好（可以考慮刷點(diǎn)博弈的題了）。
對(duì)于一個(gè)節(jié)點(diǎn)來(lái)說(shuō)，其子節(jié)點(diǎn)所對(duì)應(yīng)的每一個(gè)子樹都可以看做nim游戲當(dāng)中的一個(gè)石堆，所以相當(dāng)于每一個(gè)節(jié)點(diǎn)的sg函數(shù)的計(jì)算就是一個(gè)nim模型

然后就是一個(gè)樹上刪邊博弈問(wèn)題，主要是為了證明一個(gè)結(jié)論：$$S{G}_A=S{G}_B+1(當(dāng)A只有B這一個(gè)兒子節(jié)點(diǎn))$$這個(gè)結(jié)論的證明是用的數(shù)學(xué)歸納法，當(dāng)K個(gè)點(diǎn)滿足這個(gè)要求時(shí)，在B的子樹當(dāng)中刪掉一條邊，可以轉(zhuǎn)移到$0$到$S{G}_B?1$當(dāng)中任何一個(gè)值，此時(shí)A為根的數(shù)也是K個(gè)，可以轉(zhuǎn)移到$1$到$S{G}_B$當(dāng)中任何一個(gè)值，且可以直接刪掉A使其為0，所以其SG函數(shù)值為$S{G}_B+1$

得到上面的結(jié)論之后，代碼實(shí)現(xiàn)是非常簡(jiǎn)單的

const int N = 100010; int head[N], num, sg[N];struct edge {int nxt, to; }; edge e[N << 1];void addEdge(int x, int y) {e[++ num].nxt = head[x];head[x] = num;e[num].to = y; }void dfs(int x, int fa) {int temp = 0;for (int i = head[x]; i; i = e[i].nxt){int to = e[i].to;if (to == fa) continue;dfs (to, x);temp ^= (sg[to] + 1);}sg[x] = temp; }int main() {int T;scanf ("%d", &T);while(T --){int n;scanf ("%d", &n);for (int i = 1; i <= n; i ++)head[i] = sg[i] = 0;num = 0;for (int i = 1; i < n; i ++){int u, v;scanf ("%d %d", &u, &v);addEdge(u, v);addEdge(v, u);}dfs(1, 0);if (sg[1] == 0)printf ("YES\n");elseprintf ("NO\n");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的21-5-22校赛J 下围棋的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。