周赛 Round 139 题解

由于牛客的渲染问题，你可以点此链接进入我的博客查看

A 小红的red

知识点：循环，分支

直接每个字符判断一下即可，给出两种写法。

法一：直接判断每一个字符

时间复杂度 

void solve() {
    string s;
    cin >> s;
    for (auto v : s) {
        if (v != 'r' && v != 'e' && v != 'd') {
            cout << "No" << endl;
            return;
        }
    }
    cout << "Yes" << endl;
}

法二：我们可以用 或者 的去重性质，预先设定好目标集为 ，然后检查插入所有字符后集合大小是否仍然为 ​ 。

时间复杂度 

void solve() {
    string s;
    cin >> s;
    unordered_set<char> st = {'r', 'e', 'd'};
    for (auto v : s) st.insert(v);
    cout << (st.size() == 3 ? "Yes" : "No") << endl;
}

B 小红的矩阵构造

知识点：构造，图论，桥，网格图

直观来看，对于一个长宽至少为 的矩形：

  • 把不同的字符放在角落，有两组不同
  • 放在边上，有三组不同
  • 放在中间，有四组不同

为了避免这样的情况，只有长或宽为 的时候才是合法的。需要特判长宽均为 ，没有相邻。

从图论观点看，我们把每个格子看成一个点，相邻格子之间连边。题目要求的“恰好一对相邻字符不相同”，就等价于在图里染色，并且要求恰好只有一条边两端颜色不同，也就是存在桥。

当 且 ，任意一条边都能和周围格子组成一个环，所以不存在桥，即无解。

否则图为一条链，染它的端点即可。

时间复杂度 

void solve() {
    int n, m;
    cin >> n >> m;
    if (n > 1 && m > 1 || n == 1 && m == 1) {
        cout << -1 << endl;
    } else {
        if (n == 1) {
            for (int i = 0; i < m; ++i) cout << (i == 0);
            cout << endl;
        } else {
            for (int i = 0; i < n; ++i) cout << (i == 0) << endl;
        }
    }
}

C 小红的数据结构

知识点：队列、栈、模拟

由于操作合法，我们可以直接模拟队列和栈的操作，比较弹出的元素和给定的序列元素是否相同。

时间复杂度 

void solve() {
    int n, _;
    cin >> n >> _;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    int ptr = 0;
    bool f1 = 1, f2 = 1;
    queue<int> q;
    vector<int> st;
    while (_--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x;
            cin >> x;
            q.push(x);
            st.push_back(x);
        } else {
            int A = q.front(), B = st.back();
            if (A != a[ptr]) f1 = 0;
            if (B != a[ptr]) f2 = 0;
            q.pop(), st.pop_back();
            ptr++;
        }
    }
    if (f1 && f2)
        cout << "both" << endl;
    else if (f1)
        cout << "queue" << endl;
    else if (f2)
        cout << "stack" << endl;
    else
        cout << -1 << endl;
}

D 小红的部分相同字符串

知识点：连通块，计数，并查集

每次合并相当于给两个点之间连一条边。最终统计连通块的个数，对于每一个连通块，都可以染 ​ 种颜色。

时间复杂度

如果你有并查集模板的话：

void solve() {
    int n, k;
    cin >> n >> k;
    DSU dsu(n);
    while (k--) {
        int u, v;
        cin >> u >> v;
        dsu.merge(u, v);
    }
    cout << mypow(Z(26), dsu.get()) << endl;
}

如果没有的话（那我建议你理一个）：

void solve() {
    int n, k;
    cin >> n >> k;
    int num = n;
    vector<int> f(n + 1);
    iota(f.begin(), f.end(), 0);
    auto find = [&](auto &&self, int x) -> int { return f[x] == x ? x : f[x] = self(self, f[x]); };
    while (k--) {
        int u, v;
        cin >> u >> v;
        u = find(find, u), v = find(find, v);
        if (u != v) num--, f[v] = u;
    }
    cout << mypow(Z(26), num) << endl;
}

E 小红的树权值

知识点：树形 ，最大独立集

在一棵树中，删除若干点后，若剩余图中没有边，那么每个连通块自然都是单点。所以原问题等价于，在以 为根的子树中，选出尽量多的点，使得任意两个被选中的点之间都没有边相连。

设：

  • 表示 的子树大小
  • 表示 的子树中最大独立集大小

那么答案就是：

设 表示：

  • ：在 的子树中，且不选 时，最多能选多少个点
  • ：在 的子树中，且选 时，最多能选多少个点

因为树上没有环，子树之间是独立的。对每个儿子子树，我们只需要关心父节点是否被选，设 为 的父亲：

  • 如果选 ，那么它的所有儿子都不能选，即

  • 如果不选 ，那么它的儿子可选可不选，即

时间复杂度 

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> g(n + 1);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v), g[v].push_back(u);
    }

    vector<int> st, pa(n + 1), siz(n + 1), order;
    st.push_back(1);
    pa[1] = 0;

    while (!st.empty()) {
        int u = st.back();
        st.pop_back();
        order.push_back(u);
        for (auto v : g[u]) {
            if (v == pa[u]) continue;
            pa[v] = u;
            st.push_back(v);
        }
    }

    vector<array<int, 2>> dp(n + 1);

    for (int i = n - 1; i >= 0; i--) {
        int u = order[i];
        siz[u] = 1;
        dp[u] = {0, 1};

        for (auto v : g[u]) {
            if (v == pa[u]) continue;
            siz[u] += siz[v];
            dp[u][0] += max(dp[v][0], dp[v][1]);
            dp[u][1] += dp[v][0];
        }
    }

    for (int i = 1; i <= n; i++) cout << siz[i] - max(dp[i][0], dp[i][1]) << " ";
    cout << endl;
}

F 小红的部分不同字符串

知识点：基环树/森林，计数，拓扑剥离

将必须保证不同的两个位置连边，因为点和边的数量相同，所以这张图是一个基环树/森林（因为没有保证连通性）。

连通块的大小我们可以使用并查集求出，连通块中环的大小我们可以用拓扑剥离。由于拓扑排序在遇到环的时候会失效，也就是说，剩下的所有处理不了的点都是环上的点。

设连通块大小为 ，连通块中的环大小为 。

  • 对于环上的点，需要保证相邻的点染色不同，所以染色方案数为 。
  • 对于环上挂载的树，每个点必须与它的父亲颜色不同，也就是每个点都是 种染色方案，总共的方案数即为 ​​ 。
  • 将两者相乘即为最后的答案。

环上染色方案数的推导，设环的长度为 ，可染色数为 ：

先把环拆成一条链，每个点都必须和前一个点染色方案不同，即为 ，然后再减去头尾相同的方案数 ，答案即为 ​ 。

时间复杂度 

void solve() {
    int n;
    cin >> n;
    DSU dsu(n);
    vector<int> a(n + 1), ind(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i], dsu.merge(i, a[i]), ind[a[i]]++;

    queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (ind[i] == 0) q.push(i);

    vector<bool> cycle(n + 1, 1);
    while (q.size()) {
        auto u = q.front();
        q.pop();
        cycle[u] = 0;
        int v = a[u];
        if (--ind[v] == 0) q.push(v);
    }

    vector<int> cyclen(n + 1);
    for (int i = 1; i <= n; ++i) {
        int r = dsu.find(i);
        if (cycle[i]) cyclen[r]++;
    }

    Z ans = 1;
    for (int i = 1; i <= n; ++i) {
        if (dsu.find(i) != i) continue;
        int S = dsu.siz[i], C = cyclen[i];

        ans *= mypow(Z(25), S - C) * (mypow(Z(25), C) + 25 * mypow(Z(-1), C));
    }
    cout << ans << endl;
}

并查集

struct DSU {
    vector<int> f, siz;

    DSU() {}
    DSU(int n) {
        init(n);
    }

    void init(int n) {
        f.resize(n + 1);
        iota(f.begin(), f.end(), 0);
        siz.assign(n + 1, 1);
    }

    int find(int x) {
        return f[x] == x ? x : f[x] = find(f[x]);
    }

    void merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        f[y] = x;
        siz[x] += siz[y];
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    int size(int x) {
        return siz[find(x)];
    }
};