Hướng giải của Game trên cây

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Lời giải: Game trên cây

Phân tích

Đây là trò chơi di chuyển xuống lá. Mỗi đỉnh là đống Nim với kích thước = độ sâu từ đỉnh đó. Grundy[S] = độ sâu của S. Nếu lẻ, First thắng.

Code mẫu C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N, S; cin >> N >> S;
    vector<vector<int>> g(N+1);
    for (int i = 0; i < N-1; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v); g[v].push_back(u);
    }
    vector<int> depth(N+1, 0);
    function<void(int,int)> dfs = [&](int u, int p) {
        for (int v : g[u]) if (v != p) { depth[v] = depth[u] + 1; dfs(v, u); }
    };
    dfs(S, 0);
    int maxDepth = *max_element(depth.begin(), depth.end());
    // Grundy = độ sâu từ S đến lá xa nhất. Nếu lẻ -> First
    // Thực tế Grundy của trò chơi trên cây = độ sâu mod 2
    cout << (maxDepth % 2 ? "First" : "Second") << endl;
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.