526互联

2022年中国大学生程序设计竞赛女生专场-比赛题解

发布时间 2023-04-20 21:50:16作者: blockche

比赛链接：Dashboard - 2022年中国大学生程序设计竞赛女生专场 - Codeforces

A. 减肥计划（模拟）

模拟，如果队列第一个人体重是最大的了，则这个人的位置不会再变，直接输出即可。

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

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

    int n, k;
    cin >> n >> k;
    deque<int> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        q.push_back(i);
    }

    int mx = *max_element(a.begin(), a.end());

    vector<int> cnt(n);
    while (true) {
        int u = q.front();
        q.pop_front();
        int v = q.front();
        q.pop_front();

        if (a[u] == mx) {
            cout << u + 1 << '\n';
            return 0;
        }

        if (a[u] < a[v]) swap(u, v);
        cnt[u]++;
        if (cnt[u] == k) {
            cout << u + 1 << '\n';
            return 0;
        }
        q.push_front(u);
        q.push_back(v);
    }

    return 0;
}

E. 睡觉（模拟）

  1. 如果一首歌放完后清醒度减少了，则一定能睡着。
  2. 如果初始清醒度\(x == k\)，且一首歌播放时x始终不大于k，则可以睡着。
  3. 其余情况如果前两首歌内没睡着，那么睡再久也睡不着，所以直接模拟前两首歌的情况。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

void solve() {
    int x, t, k, n, d;
    cin >> x >> t >> k >> n >> d;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    bool ok = true;
    int add = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] <= d) {
            add--;
        } else {
            add++;
        }
        if (add > 0) ok = false;
    }

    if (add < 0) {
        cout << "YES\n";
        return;
    }
    if (x == k && ok) {
        cout << "YES\n";
        return;
    }

    vector<int> b;
    b.insert(b.end(), a.begin(), a.end());
    b.insert(b.end(), a.begin(), a.end());

    add = 0;
    vector<int> val(b.size());
    for (int i = 0; i < b.size(); i++) {
        if (b[i] <= d) {
            add--;
        } else {
            add++;
        }
        val[i] = x + add;
    }

    int now = 0;
    for (int i = 0; i < b.size(); i++) {
        if (val[i] <= k) {
            now++;
            if (now >= t) {
                cout << "YES\n";
                return;
            }
        } else {
            now = 0;
        }
    }
    cout << "NO\n";
}

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

    int T;
    cin >> T;

    while (T--) {
        solve();
    }

    return 0;
}

H. 提瓦特之旅（图论，最短路）

w数组为步数的权值。

如果在每次询问里带着w的权值跑最短路，复杂度为\(O(q*n*n)\)，会超时，所以我们需要先预处理出从节点0开始到每个点\(i\)，使用步数\(j\)的最短路径，之后在询问中对所有步数取一遍最小值，复杂度\(O(n*n*n)\)。

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

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

    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, i64>>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        u--, v--;
        adj[u].emplace_back(v, c);
        adj[v].emplace_back(u, c);
    }

    vector dis(n, vector<i64>(n, 1e18));
    dis[0][0] = 0;
    for (int k = 0; k < n - 1; k++) {
        for (int i = 0; i < n; i++) {
            for (auto [v, c] : adj[i]) {
                dis[v][k + 1] = min(dis[v][k + 1], dis[i][k] + c);
            }
        }
    }

    int q;
    cin >> q;
    while (q--) {
        int t;
        cin >> t;
        t--;
        vector<i64> w(n - 1);
        for (int i = 0; i < n - 1; i++) {
            cin >> w[i];
        }
        for (int i = 1; i < n - 1; i++) {
            w[i] += w[i - 1];
        }

        i64 ans = 1e18;
        for (int i = 1; i < n; i++) {
            ans = min(ans, dis[t][i] + w[i - 1]);
        }
        cout << ans << '\n';
    }

    return 0;
}

I. 宠物对战（字符串hash，简单dp）

可以用字符串hash或字典树或ac自动三种方法来写，先说一下字符串hash的写法，其他的以后可能会补。

处理出A类和B类所有字符串的hash值，分别放入两个set中。

随后对字符串S进行dp，设\(dp[i][j]\)状态为：到第\(i\)个字符，最后一个子串属于\(j\)类时，字符串拼接所用的最少子串。

有一个优化是，把AB类字符串按长度分类放入不同set，这样在查询的时候对每个长度的set就最多查询n次了。

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

constexpr i64 mul(i64 a, i64 b, i64 p) {
    i64 res = a * b - i64(1.L * a * b / p) * p;
    res %= p;
    if (res < 0) {
        res += p;
    }
    return res;
}

struct Hash {
    const i64 P = 1E12 + 39;
    const int B = 13331;
    vector<i64> h, p;
    Hash(string s) : h(s.size() + 1), p(s.size() + 1) {
        int n = s.size();
        p[0] = 1;
        for (int i = 0; i < n; i++) {
            h[i + 1] = (h[i] * B + s[i]) % P;
            p[i + 1] = p[i] * B % P;
        }
    };

    i64 get(int l, int r) {
        return (h[r] + mul(h[l], P - p[r - l], P)) % P;
        // return (h[r] + __int128(h[l]) * (P - p[r - l])) % P;
    };
};

constexpr int inf = 1e9, N = 5e5 + 1;

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

    int n;
    cin >> n;
    unordered_set<i64> st[2][N];
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        Hash hs(s);
        st[0][s.size()].insert(hs.get(0, s.size()));
    }
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        string s;
        cin >> s;
        Hash hs(s);
        st[1][s.size()].insert(hs.get(0, s.size()));
    }

    string s;
    cin >> s;
    Hash hs(s);
    vector<array<int, 2>> dp(s.size() + 1, {inf, inf});
    dp[0] = {0, 0};
    for (int i = 0; i < s.size(); i++) {
        for (int j = 0; j <= i; j++) {
            i64 now = hs.get(j, i + 1);
            for (int k = 0; k < 2; k++) {
                if (st[k][i - j + 1].count(now)) {
                    dp[i + 1][k] = min(dp[i + 1][k], dp[j][k ^ 1] + 1);
                }
            }
        }
    }

    int ans = min(dp[s.size()][0], dp[s.size()][1]);
    if (ans == inf) {
        cout << "-1\n";
    } else {
        cout << ans << '\n';
    }

    return 0;
}

K. 区间和（卷积ntt优化）

因为要算区间和，所以我们可以先想到前缀和，前缀和两个下标\(pre_j - pre_i = 区间和\)，如果要求所有子区间和，我们需要对所有\(n^2\)个子区间都算一次，显然会超时。

定义数组\(cnt[i]\)为前缀和为\(i\)的个数，数组\(ans[i]\)为区间和为\(i\)的个数。可以发现，下标\(z = j - i\)，\(ans_z = cnt_j * cnt_i\)。

于是这样即可求出答案：

\[\sum_{i = 0}^n\sum_{j = i}^nans_{j - i} = cnt_j * cnt_i \]

（这样会多算一些东西，下面会讲）

这样是\(O(n^2)\)的，但不难发现，这种每个下标要和其他所有下标进行运算的形式，和多项式相乘很像，所以我们就可以往卷积ntt优化想了。

多项式相乘的卷积公式为：

\[f(x) = g(i) * h(x - i) \]

但这是\(i + (x - i) = x\)，是下标相加的形式，但我们需要的是下标相减的形式，所以我们稍微改造一下这个公式，

翻转h：

\[f(x) = g(i) * h(n + i - x) \]

整理一下：

\[f(n - x) = g(i) * h(n - x + i) \]

我们可以发现\((n - x + i) - i = n - x\)，是相减的形式，这样即得到满足条件的卷积。

注意：

  1. ntt要使用大模数
  2. 这样会把\(pre_i - pre_i\)这样的空集也算进\(ans_0\)中，并且会被算两次，所以最后要处理一下。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

template <class T>
T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
constexpr i64 mul(i64 a, i64 b, i64 p) {
    i64 res = a * b - i64(1.L * a * b / p) * p;
    res %= p;
    if (res < 0) {
        res += p;
    }
    return res;
}

template <i64 P>
struct MLong {
    i64 x;
    MLong() : x{} {}
    MLong(i64 x) : x{norm(x % P)} {}

    i64 norm(i64 x) {
        if (x < 0) x += P;
        if (x >= P) x -= P;
        return x;
    }
    i64 val() const { return x; }
    MLong inv() const {
        assert(x != 0);
        return power(*this, P - 2);
    }
    MLong &operator+=(const MLong &rhs) { return x = norm(x + rhs.x), *this; }
    MLong &operator-=(const MLong &rhs) { return x = norm(x - rhs.x), *this; }
    MLong &operator*=(const MLong &rhs) { return x = norm(mul(x, rhs.x, P)), *this; }
    MLong &operator/=(const MLong &rhs) { return *this *= rhs.inv(); }
    MLong operator+(const MLong &rhs) { return MLong(*this) += rhs; }
    MLong operator-(const MLong &rhs) { return MLong(*this) -= rhs; }
    MLong operator*(const MLong &rhs) { return MLong(*this) *= rhs; }
    MLong operator/(const MLong &rhs) { return MLong(*this) /= rhs; }
};
// 4179340454199820289
// 998244353
constexpr i64 P = 4179340454199820289;
constexpr int G = 3;
using Z = MLong<P>;

vector<int> rev;
vector<Z> roots{0, 1};
void dft(vector<Z> &a) {
    int n = a.size();

    if (int(rev.size()) != n) {
        int k = __builtin_ctz(n) - 1;
        rev.resize(n);
        for (int i = 0; i < n; i++)
            rev[i] = rev[i >> 1] >> 1 | (i & 1) << k;
    }

    for (int i = 0; i < n; i++)
        if (rev[i] < i)
            swap(a[i], a[rev[i]]);
    if (int(roots.size()) < n) {
        int k = __builtin_ctz(roots.size());
        roots.resize(n);
        while ((1 << k) < n) {
            Z e = power(Z(G), (P - 1) >> (k + 1));
            for (int i = 1 << (k - 1); i < (1 << k); i++) {
                roots[2 * i] = roots[i];
                roots[2 * i + 1] = roots[i] * e;
            }
            k++;
        }
    }
    for (int k = 1; k < n; k *= 2)
        for (int i = 0; i < n; i += 2 * k)
            for (int j = 0; j < k; j++) {
                Z u = a[i + j];
                Z v = a[i + j + k] * roots[k + j];
                a[i + j] = u + v;
                a[i + j + k] = u - v;
            }
}
void idft(vector<Z> &a) {
    int n = a.size();
    reverse(a.begin() + 1, a.end());
    dft(a);
    Z inv = (1 - P) / n;
    for (int i = 0; i < n; i++)
        a[i] = a[i] * inv;
}
vector<Z> operator*(vector<Z> a, vector<Z> b) {
    int sz = 1, tot = a.size() + b.size() - 1;
    while (sz < tot) sz *= 2;
    vector<Z> ca(sz), cb(sz);
    copy(a.begin(), a.end(), ca.begin());
    copy(b.begin(), b.end(), cb.begin());
    dft(ca);
    dft(cb);
    for (int i = 0; i < sz; ++i) ca[i] = ca[i] * cb[i];
    idft(ca);
    ca.resize(tot);
    return ca;
}

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

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> pre(n + 1);
    for (int i = 0; i < n; i++) {
        pre[i + 1] = pre[i] + a[i];
    }
    int mx = *max_element(pre.begin(), pre.end());
    vector<Z> g(mx + 1);
    for (int i = 0; i <= n; i++) {
        g[pre[i]] += 1;
    }
    auto h = g;
    reverse(h.begin(), h.end());

    auto f = g * h;
    vector<i64> num(mx + 1);
    for (int i = 0; i <= mx; i++) {
        num[i] = f[i + mx].x;
    }
    num[0] = (num[0] - (n + 1)) / 2;
    for (int i = 1; i < num.size(); i++) {
        num[i] += num[i - 1];
    }

    int m;
    cin >> m;
    while (m--) {
        i64 k;
        cin >> k;

        int ans = lower_bound(num.begin(), num.end(), k) - num.begin();
        cout << ans << '\n';
    }

    return 0;
}

L. 彩色的树（启发式合并）

一眼启发式合并，用map维护每个点的子树的颜色，一边向上合并一边记录每个点的答案，最后询问的时候直接\(O(1)\)输出答案就完事了！

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

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

    int n, k;
    cin >> n >> k;
    vector<int> c(n);
    for (int i = 0; i < n; i++) {
        cin >> c[i];
    }
    vector<vector<int>> adj(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<vector<int>> ho(n);
    vector<map<int, int>> mp(n);
    vector<int> dep(n), ans(n);
    function<void(int, int)> dfs = [&](int u, int pa) {
        ho[dep[u]].push_back(u);
        for (auto v : adj[u]) {
            if (v == pa) continue;
            dep[v] = dep[u] + 1;
            dfs(v, u);
            if (mp[v].size() > mp[u].size()) swap(mp[v], mp[u]);
            for (auto [x, y] : mp[v]) {
                mp[u][x] += y;
            }
        }
        mp[u][c[u]]++;
        if (dep[u] + k + 1 < n) {
            for (auto x : ho[dep[u] + k + 1]) {
                if (--mp[u][c[x]] == 0) {
                    mp[u].erase(c[x]);
                }
            }
            ho[dep[u] + k + 1].clear();
        }
        ans[u] = mp[u].size();
    };
    dfs(0, -1);

    int m;
    cin >> m;
    while (m--) {
        int x;
        cin >> x;
        x--;
        cout << ans[x] << '\n';
    }

    return 0;
}