牛客周赛 Round 118 E/F

E-小红玩树

由于本题是一颗无根树而非图，故点 α 到 β 的路径是唯一的

同理，对于小红来说，去往每个叶子节点的路径也是唯一的，小紫如果要赶上小红，那她的路线也是唯一的，所以仅需判断在同一终点的路径下，小紫是否能追上小红即可。设小红到每个点的最短距离为 d1_i， 小紫到每个点的最短距离为 d2_i， 考虑到小紫能移动 1 至 2 次且小红有多个路径可选，所以只要存在 d1_i * 2 ≤ d2_i 时，小红获胜

▶

code

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
int main(){
    int t;
    std::cin >> t;
    while (t--){
        int n, a, b;
        std::cin >> n >> a >> b;
        std::vector<std::vector<int>> chart(n + 1);
        std::vector<int> d1(n + 1, -1), d2(n + 1, -1);
        for (int u, v, i = 1; i < n; i++){
            std::cin >> u >> v;
            chart[u].emplace_back(v);
            chart[v].emplace_back(u);
        }
        auto dijk = [&](int u, std::vector<int>& dis) -> void{
            std::queue<std::pair<int, int>> q;
            q.push({u, 0});
            dis[u] = 0;
            while (!q.empty()) {
                auto &[u, dist] = q.front();
                q.pop();
                for (auto &v : chart[u]){
                    if (dis[v] != -1) continue;
                    dis[v] = dist + 1;
                    q.push({v, dis[v]});
                }
            }
        };
        dijk(a, d1);
        dijk(b, d2);
        bool flag = 0;
        for (int i = 1; i <= n; i++){
            if (chart[i].size() == 1){
                if (d2[i] >= d1[i] * 2){
                    flag = 1;
                }
            }
        }
        if (flag) std::cout << "red\n";
        else std::cout << "purple\n";
    }
    return 0;
}

F-小红拿石子2.0

设一轮指小红小紫各完成一次操作(p)，那么第 n 轮时，所有 a_i ≤ n − 1 的堆都会被清空，越大的数越能留到最后，所以我们仅考虑最大堆，设最大的数为 k，共有 m 堆

• 当 k > m 时：

  ​ $[\underbrace{k,k,\cdots,k}_m]\rightarrow_{p1} [\underbrace{k-1,k-1,\cdots,k-1}_{m-1}]\rightarrow_{p2}\cdots\rightarrow_{pk-1}[\underbrace{1,1,\cdots,1}_{m-k+1}]\Rightarrow purple\ win$

• 当 k = m 时:

  ​ $[\underbrace{k,k,\cdots,k}_m]\rightarrow_{p1} [\underbrace{k-1,k-1,\cdots,k-1}_{m-1}]\rightarrow_{p2}\cdots\rightarrow_{pk-1}[1]\Rightarrow red\ win$

• 当 k < m 时：

  ​ $[\underbrace{k,k,\cdots,k}_m]\rightarrow_{p1} [\underbrace{k-1,k-1,\cdots,k-1}_{m-1}]\rightarrow_{p2}\cdots\rightarrow_{pm-1}[k-m+1]\Rightarrow red\ win$

综上，如果 k ≤ m，那么小红一定赢，反之，小紫一定赢

▶

code

#include <algorithm>
#include <iostream>
#include <unordered_map>
int main(){
    int t;
    std::cin >> t;
    while (t--){
        int n, maxn = -0x3f3f3f3f;
        std::cin >> n;
        std::unordered_map<int, int> cnt;
        for (int x, i = 0; i < n; i++){
            std::cin >> x;
            maxn = std::max(maxn, x);
            cnt[x]++;
        }
        if (maxn >= cnt[maxn]) std::cout << "red\n";
        else std::cout << "purple\n";
    }
    return 0;
}