暑假集训 杭电多校 Round 1

暑假集训第一次杭电多校。

题目链接

---

I 「Assertion」

签到题，知道抽屉原理就行了。

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

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

#include <iostream>

void solve() {
    int n, m, d;
    std::cin >> n >> m >> d;
    if (d <= (m + n - 1) / n) {
        std::cout << "Yes\n";
    }
    else {
        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;
}

E 「Cyclically Isomorphic」

判断两个字符串 str1 和 str2 是否符合 "Cyclically Isomarphic" 的性质，只需要判断 str2 是否是 str1 + str1 的子串即可。

时间复杂度：\(O(Qm)\)（重复的查询不计入）

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

#include <iostream>
#include <vector>
#include <map>

void solve() {
    int n, m, q;
    std::cin >> n >> m;
    std::vector<std::string> arr(n);
    std::vector<std::string> pat(n);
    for (int i = 0; i < n; i++) {
        std::string str;
        std::cin >> str;
        arr[i] = str;
        pat[i] = str + str;
    }
    std::map<std::pair<int, int>, bool> res;
    std::cin >> q;
    for (int i = 0, x, y; i < q; i++) {
        std::cin >> x >> y;
        x--;
        y--;
        if (x > y) {
            int tmp = x;
            x = y;
            y = tmp;
        }
        if (res.find({x, y}) == res.end()) {
            res[{x, y}] = pat[x].find(arr[y]) != std::string::npos;
        }
        
        std::cout << (res[{x, y}] ? "Yes\n" : "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;
}

B 「City Upgrading」

树上 DP，选定一个根节点，从叶节点向上 DP，状态转移方程还是比较好想的，如果父节点没有被选取，则至少要有一个子节点被选取。

若父节点被选取，则子节点的子树必须都被覆盖。

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

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

#include <iostream>
#include <algorithm>
#include <vector>

using i64 = long long;
const i64 inf = 0x7f7f7f7f7f7fll;

class Solution {
private:
    std::vector<int> cost;
    std::vector<std::vector<int>> g;
    std::vector<std::vector<i64>> dp; // dp[i] 表示 i 以及其子树覆盖的最小花费
    // dp[i][0] 表示不选择 i
    // dp[i][1] 表示选择 i

    void dfs(int x, int fa) {
        dp[x][1] = cost[x];
        for (int v : g[x]) {
            if (v != fa) {
                dfs(v, x);
                // 只需要一个子树选择父节点即可
                dp[x][0] += std::min(dp[v][0], dp[v][1]);

                i64 res_1 = std::min(dp[v][0], dp[v][1]); // 选择儿子节点
                i64 res_2 = 0;
                for (int sv : g[v]) {
                    if (sv != x) {
                        res_2 += std::min(dp[sv][0], dp[sv][1]);
                    }
                }
                // 不选择儿子节点，则需要覆盖该儿子节点的所有孙子子树

                dp[x][1] += std::min(res_1, res_2);
            }
        }
        i64 res = dp[x][0];
        dp[x][0] = inf;
        for (int v : g[x]) {
            // 至少一个子树选择父节点
            if (v != fa) {
                dp[x][0] = std::min(dp[x][0], res - std::min(dp[v][0], dp[v][1]) + dp[v][1]);
            }
        }
    }

public:
    void solve() {
        int n;
        std::cin >> n;
        cost.resize(n);
        for (int i = 0; i < n; i++) std::cin >> cost[i];
        g.resize(n);
        for (int i = 0, x, y; i < n - 1; i++) {
            std::cin >> x >> y;
            x--;
            y--;
            g[x].push_back(y);
            g[y].push_back(x);
        }
        dp.resize(n, std::vector<i64>(2, 0));

        dfs(0, -1);

        std::cout << std::min(dp[0][0], dp[0][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--) Solution().solve();

    return 0;
}

L 「Play on Tree」

给定一颗树，两人轮流删掉一个子树，删掉最后一个节点的人输掉比赛。则叶节点的 SG 值为 0，非叶节点的 SG 值为其所有子节点的 (SG 值 + 1) 的异或和。

对于不同的根节点，可以考虑换根 DP，从而得到每一个节点作为根节点的 SG 值。

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

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

#include <iostream>
#include <cstring>

using i64 = long long;

const int MAX_N = 2e5 + 5;
int first[MAX_N];
struct {
    int to;
    int next;
} edges[2 * MAX_N];
int cnt = 0;

void addEdge(int x, int y) {
    edges[cnt] = {y, first[x]};
    first[x] = cnt++;
}

int sg1[MAX_N];
int sg2[MAX_N];

void dfs1(int v, int fa) {
    sg1[v] = 0;
    for (int e = first[v]; e != -1; e = edges[e].next) {
        int x = edges[e].to;
        if (x == fa) continue;
        dfs1(x, v);
        sg1[v] ^= (sg1[x] + 1);
    }
}

void dfs2(int v, int fa) {
    // 换根
    for (int e = first[v]; e != -1; e = edges[e].next) {
        int x = edges[e].to;
        if (x == fa) continue;
        sg2[x] = ((sg2[v] ^ (sg1[x] + 1)) + 1) ^ sg1[x];
        dfs2(x, v);
    }
}

const int mod = 1e9 + 7;

int quickPow(int x, int n) {
    int res = 1;
    while (n) {
        if (n & 1) res = (i64)res * x % mod;
        x = (i64)x * x % mod;
        n >>= 1;
    }

    return res;
}

void solve() {
    cnt = 0;
    memset(first, 0xff, sizeof(first));
    int n;
    std::cin >> n;
    for (int i = 0, x, y; i < n - 1; i++) {
        std::cin >> x >> y;
        x--, y--;
        addEdge(x, y);
        addEdge(y, x);
    }
    dfs1(0, -1);
    sg2[0] = sg1[0];
    dfs2(0, -1);
    int res = 0;
    for (int i = 0; i < n; i++) res += sg2[i] != 0;

    std::cout << (i64)res * quickPow(n, mod - 2) % mod << '\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;
}