CodeTon Round 5 总结

比赛链接

这一场打得一般，因为太困了。😢

---

A 「Tenzing and Tsondu」

水题，易证总和高的人必胜，总和相等则平局。

时间复杂度：\(O(n)\)

空间复杂度：\(O(1)\)

#include <iostream>

using i64 = long long;

void solve() {
    int n, m;
    std::cin >> n >> m;
    i64 sum_1 = 0, sum_2 = 0;
    for (int i = 0, x; i < n; i++) {
        std::cin >> x;
        sum_1 += x;
    }
    for (int i = 0, x; i < m; i++) {
        std::cin >> x;
        sum_2 += x;
    }
    if (sum_1 > sum_2) {
        std::cout << "Tsondu\n";
    }
    else if (sum_1 < sum_2) {
        std::cout << "Tenzing\n";
    }
    else {
        std::cout << "Draw\n";
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int numTest;
    std::cin >> numTest;
    while (numTest--) {
        solve();
    }

    return 0;
}

B 「Tenzing and Books」

根据题意，如果某本书的 knowledge 某个 bit 位为 1 而 x 在该位为 0，即满足 knowledge & ~x 非 0，则该书一定不能选取，根据栈的性质，该书以下的书也不能选取。

而或运算对于 3 个栈的操作顺序本身而言没有影响，所以我们依次遍历每个栈即可，如果遍历过程中出现不能选择的书，那么就结束该轮循环，进入下一个栈，3 轮循环中如果出现某个状态等于 x ，则说明可以使得 knowledge 的值等于 x ，若 3 轮循环结束后都没有得到目标答案，则说明无法使得 knowledge 的值等于 x 。

时间复杂度：\(O(n)\)

空间复杂度：\(O(n)\)

#include <iostream>

#define MAX_N 100005

int stk[3][MAX_N];

void solve() {
    int n, x;
    std::cin >> n >> x;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < n; j++) {
            std::cin >> stk[i][j];
        }
    }
    int mask = ~x, ans = 0;
    if (x == 0) {
        std::cout << "Yes\n";
        return;
    }
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < n; j++) {
            if (stk[i][j] & mask) break;
            ans |= stk[i][j];
            if (ans == x) {
                std::cout << "Yes\n";
                return;
            }
        }
    }

    std::cout << "No\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    
    int numTest;
    std::cin >> numTest;
    while (numTest--) {
        solve();
    }

    return 0;
}

C 「Tenzing and Balls」

若存在 \(i、 j、 m、 n\) 使得 \(a_i = a_j\) 且 \(a_m = a_n\) ，则考虑区间 \([i, j]\) 和 \([m, n]\) ：

• 若两个区间无交集，则两个区间都可以删除且互不影响；
• 若两个区间是包含关系，不妨设 \([i, j] \subsetneq [m, n]\)，则 \([i, j]\) 只能在 \([m, n]\) 之前删除，而删除 \([i, j]\) 再删除 \([m, n]\) 与直接删除 \([m, n]\) 的效果是一样的；
• 若两个区间相交且不为包含关系，则只能删除其中一个区间。

综上所述，问题就变成了如何选取不相交的区间，使得选取的区间总长度最长。

我们假设 \(dp[i]\) 表示区间 \([0, i]\) 删除完后剩下来的数的最小值，\(dp[0]\) 初始化为 1，我们可以得到以下关系：

• 若不删除 \(a_i\) ，则 \(dp[i] = dp[i - 1] + 1\)
• 若能删除 \(a_i\) ，则 \(dp[i] = \underset{j}{min}\ \{dp[j]\ |\ j < i - 1 \land a_{j + 1} = a_i \}\)

于是，我们就得到了状态转移方程：\(dp[i] = min\{dp[i - 1] + 1,\ \underset{j}{min}\ \{dp[j]\ |\ j < i - 1 \land a_{j + 1} = a_i \}\)

而对于 \(\underset{j}{min}\ \{dp[j]\ |\ j < i - 1 \land a_{j + 1} = a_i \}\) 这一项，我们考虑使用一个数组更新每轮迭代后满足 \(a_{j + 1} = a_i\) 的最小 \(dp[j]\) 的值即可。迭代完后 \(n - dp[n - 1]\) 即为可删除的最大数量。

时间复杂度：\(O(n)\)

空间复杂度：\(O(n)\)

#include <iostream>
#include <cstring>

#define MAX_N 200005

int arr[MAX_N];
int dp[MAX_N]; // 最少剩多少个
int memo[MAX_N]; // memo[t] 表示满足 arr[j + 1] == t 的所有数里面 dp[j] 的最小值

void solve() {
    int n;
    std::cin >> n;
    for (int i = 0; i < n; i++) {
        std::cin >> arr[i];
        dp[i] = i + 1;
    }
    memset(memo + 1, 0x7f, n * sizeof(int));
    memo[arr[0]] = 0;
    for (int i = 1; i < n; i++) {
        dp[i] = std::min(dp[i - 1] + 1, memo[arr[i]]);
        memo[arr[i]] = std::min(memo[arr[i]], dp[i - 1]);
    }

    std::cout << n - dp[n - 1] << '\n';
}


int main() {

    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int numTest;
    std::cin >> numTest;
    while (numTest--) {
        solve();
    }

    return 0;
}

D 「Tenzing and His Animal Friends」

题目有点抽象，大概就是说全部轮游戏中 \(u_i\) 和 \(v_i\) 的分开游戏时间总和均不超过 \(y_i\)，即 \(u_i\) 不和 \(v_i\) 玩的游玩时间不超过 \(y_i\) ，对 \(v_i\) 也是同理。于此同时，顶点 1 每轮游戏都要参加，顶点 n 每轮游戏都不能参加。

我们接下来将所有的限制看成一个无向图，若存在限制 \((u_i, v_i, y_i)\)，那么就在顶点 \(u_i\) 和 \(v_i\) 之间连接一条权重为 \(y_i\) 的边。

考虑以下两种情况：

• 若顶点 1 无法在有限步内到顶点 n，就说明顶点 1 和顶点 n 属于不同的分支，那我们每次可以和顶点 1 所在分支全部顶点一起玩，且没有时间限制。此时答案为 inf 。

• 若顶点 1 可以到达顶点 n，我们假设其中一条路径为 \(<1, k_1, k_2, ..., k_m, n>\) ，每个顶点的游玩时间为 \(t_1, t_{k_1}, t_{k_2}, ..., t_{k_m}, t_n\)。

  因为顶点 1 每轮游戏都参与，所以顶点 1 游玩的时间就是总的游戏时间，因此我们只要求出 \(t_1\) 的最小值即可。

  由于一对顶点 \((x, y)\) 分开的时间不超过 \(d(x, y)\)，我们可以得到：\(t_x - t_y \leq d(x, y)\)。

  所以有： \[ \begin{array}{} t_1 - t_{k_1} \leq d(1, k_1) \\ t_{k_1} - t_{k_2} \leq d(k_1, k_2) \\ ... \\ t_{k_m} - t_{n} \leq d(k_m, n) \end{array} \] 将上式求和： \[ \implies t_1 - t_n \leq d(1, k_1) + d(k_1, k_2) + ... + d(k_m, n) \] 又因为顶点 n 不参与游戏，所以 \(t_n = 0\)，综上所述： \[ t_1 \leq d(1, k_1) + d(k_1, k_2) + ... + d(k_m, n) \] 右式其实就是顶点 1 到顶点 n 的路径长度，换言之，游戏的时长必须小于等于所有顶点 1 到顶点 n 的路径长度。所以我们只要求出顶点 1 到顶点 n 到最短路径即可，考虑最小堆优化的 Dijkstra 算法，并用一个数组记录每次出队列的顶点。

  时间复杂度：\(O(mlog(m + n))\)

  空间复杂度：\(O(n + m)\)

#include <iostream>
#include <vector>
#include <queue>

using i64 = long long;

void solve() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<std::pair<int, int>>> g(n);
    for (int i = 0, u, v, y; i < m; i++) {
        std::cin >> u >> v >> y;
        u--;
        v--;
        g[u].push_back({v, y});
        g[v].push_back({u, y});
    }
    std::vector<i64> dist(n, -1);
    std::priority_queue<std::pair<i64, int>, std::vector<std::pair<i64, int>>, std::greater<>> q;
    q.push({0, 0});
    std::vector<i64> ans;
    while (!q.empty()) {
        auto [d, to] = q.top();
        q.pop();
        if (dist[to] != -1) continue;
        dist[to] = d;
        ans.push_back(to);
        if (to == n - 1) break;
        for (auto [nxt, w] : g[to]) {
            q.push({d + w, nxt});
        }
    }
    if (dist[n - 1] == -1) {
        std::cout << "inf\n";
        return;
    }
    std::cout << dist[n - 1] << ' ' << ans.size() - 1 << '\n';
    std::string s(n, '0');
    for (int i = 1, len = ans.size(); i < len; i++) {
        s[ans[i - 1]] = '1';
        std::cout << s << ' ' << dist[ans[i]] - dist[ans[i - 1]] << '\n';
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    solve();

    return 0;
}