Codeforces Round 1026 (Div. 2)题解

Dashboard - Codeforces Round 1026 (Div. 2) - Codeforces

A

将数组排序后，如果首尾相加为偶数，则直接输出0，否则枚举从前去掉的最少数字，和从后去掉的最少数字以达到首尾相加为偶数的最小值

void solve() {
    int n;
    cin >> n;
    std::vector<int> a(n);
    for (int &x : a) {
        cin >> x;
    }
    std::sort(a.begin(), a.end());
    if ((a[0] + a[n - 1]) % 2 == 0) {
        cout << 0 << "\n";
        return;
    }
    int ans = n - 1;
    for (int i = 1; i < n - 1; i++) {
        if ((a[i] + a[n - 1]) % 2 == 0) {
            ans = std::min(ans, i);
            break;
        }
    }
    for (int i = n - 2; i > 0; i--) {
        if ((a[0] + a[i]) % 2 == 0) {
            ans = std::min(ans, n - i - 1);
            break;
        }
    }
    cout << ans << "\n";
}

B

如果某个前缀的)数量 $>$ (数量，那么它必然是不合法的括号序列

只需要判断在1~n-1位置的前缀上存在某个位置的(数量 $=$ )数量，只需要去掉这个前缀上的一个(，那么再去掉该位置之后的一个 )（可知n位置一定是一个)），整个括号序列就会变得不合法

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    int bal = 0;
    bool ok = false;
    for(int i = 0; i < n - 1; i++){
        if(s[i]=='(') {
            bal++;
        }
        else{
            bal--;
        }   
        if(bal == 0){
            ok = true;
            break;
        }
    }
    cout << (ok ? "YES\n" : "NO\n");
}

C

最初从 $(0,0)$ 开始飞行，考虑目前合法的飞行范围，假设前一个位置的合法飞行范围为 $(tl,tr)$，则

• $d[i]=0$，则保持不变
• $d[i]=1$，则 $(tl+1,tr+1)$
• $d[i]=-1$，则 $(tl,tr+1)$

最后与当前位置的障碍物合并：设该位置障碍物为 $(l, r)$ 则取 $(tl,tr)\leftarrow(max(tl, l),min(tr,r))$ 为当前位置合法范围，如果有 $tl>tr$，无合法方案，返回-1

否则可从最后位置选取一个高度往前递推求出答案

void solve() {
    int n;
    cin >> n;
    std::vector<int> d(n);
    for (int &x : d) {
        cin >> x;
    }
    std::vector<PII> lr(n), hr(n);
    for (auto &[l, r] : lr) {
        cin >> l >> r;
    }
    for (int i = 0; i < n; i++) {
        auto [tl, tr] = i > 0 ? hr[i - 1] : std::make_pair(0, 0);
        if (d[i] == -1) {
            tr++;
        } else if (d[i] == 1) {
            tl++;
            tr++;
        }
        int curmn = std::max(lr[i].fi, tl), curmx = std::min(lr[i].se, tr);
        if (curmn > curmx) {
            cout << -1 << "\n";
            return;
        }
        hr[i] = {curmn, curmx};
    }
    int h = hr[n - 1].se;
    for (int i = n - 1; i >= 0; i--) {
        if (d[i] == 1) {
            h--;
        } else if (d[i] == -1) {
            if (h >= (i > 0 ? hr[i - 1].fi : 0) && h <= (i > 0 ? hr[i - 1].se : 0)) {
                d[i] = 0;
            } else {
                d[i] = 1;
                h--;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        cout << d[i] << " \n"[i == n - 1];
    }
}

​

D

二分答案，用 $dp[i]$ 表示当前在节点 $i$ 拥有的电池数量，由于是个拓扑图，拓扑序从小到大，因此跑一遍拓扑序即可

void solve() {
    int n, m, mx = -1;
    cin >> n >> m;
    std::vector<std::vector<PII>> g(n);
    std::vector<int> b(n);
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    for (int i = 0; i < m; i++) {
        int s, t, w;
        cin >> s >> t >> w;
        s--;
        t--;
        mx = std::max(mx, w);
        g[s].emplace_back(t, w);
    }
    auto check = [&](int x) -> bool {
        std::vector<int> dp(n, -1);
        dp[0] = std::min(x, b[0]);
        for (int i = 0; i < n; i++) {
            for (auto [v, w] : g[i]) {
                if (w <= dp[i]) {
                    dp[v] = std::min(dp[i] + b[v], x);
                }
            }
        }
        return dp[n - 1] >= 0;
    };
    int l = 0, r = mx + 1;
    while (l < r) {
        int m = (l + r) / 2;
        if (check(m)) {
            r = m;
        } else {
            l = m + 1;
        }
    }
    cout << (l == mx + 1 ? -1 : l) << "\n";
}

E

包含所有 $n$ 个点有且仅有一次

考虑欧拉路径：

1. 所有 $v_i$ 相同的乐器和所有 $p_i$ 相同的节点之间可以相互到达
2. 不能连续三次经过 $v_i$ 相同的节点或者 $p_i$ 相同的节点

可见选择为 $p_i\sim v_i\overset{v+i=v_j}\longrightarrow v_j\sim p_j\overset{p_j=p_k}\longrightarrow p_k \sim v_k$ 如果我们选择将相同的 $v$ 和相同的 $p$ 进行缩点，则可以发现所有点构成一个二分图，这样建图思路就清晰了，同时也能保证不在相同 $v$ 或 $p$ 的节点上连续跳转三次

void solve() {
    int n;
    cin >> n;
    std::vector<PII> a(n);
    std::vector<int> v(n), p(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i] >> p[i];
        a[i] = {v[i], p[i]};
    }
    std::sort(v.begin(), v.end());
    std::sort(p.begin(), p.end());
    v.erase(std::unique(v.begin(), v.end()), v.end());
    p.erase(std::unique(p.begin(), p.end()), p.end());
    std::map<int, int> mv, mp;
    int idx = 0;
    for (int x : v) {
        mv[x] = idx++;
    }
    for (int x : p) {
        mp[x] = idx++;
    }
    std::vector<int> path, deg(idx);
    std::vector<std::vector<PII>> g(idx);
    std::vector<int> end(idx);
    std::vector<bool> vis(n);
    for (int i = 0; i < n; i++) {
        int vi = mv[a[i].fi], pi = mp[a[i].se];
        g[vi].emplace_back(pi, i);
        g[pi].emplace_back(vi, i);
        deg[vi]++;
        deg[pi]++;
    }
    int odd = 0, s = -1;
    for (int i = 0; i < idx; i++) {
        if (deg[i] % 2 != 0) {
            odd++;
            s = i;
        }
    }
    if (odd > 2) {
        cout << "NO\n";
        return;
    }
    if (s == -1) {
        for (int i = 0; i < idx; i++) {
            if (deg[i]) {
                s = i;
                break;
            }
        }
    }
    auto dfs = [&](auto && dfs, int u) -> void {
        while (end[u] < g[u].size()) {
            auto [v, id] = g[u][end[u]++];
            if (!vis[id]) {
                vis[id] = true;
                dfs(dfs, v);
                path.push_back(id);
            }
        }
    };
    dfs(dfs, s);
    if (path.size() != n) {
        cout << "NO\n";
        return;
    }
    cout << "YES\n";
    std::reverse(path.begin(), path.end());
    for (int i = 0; i < n; i++) {
        cout << path[i] + 1 << " \n"[i == n - 1];
    }
}