首页 > 编程语言 >2022年中国大学生程序设计竞赛女生专场-比赛题解

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

时间：2023-04-20 21:58:11浏览次数：58  
标签：专场 int 题解 cin MLong i64 ++ vector 2022

比赛链接：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;
}

标签：专场,int,题解,cin,MLong,i64,++,vector,2022
From： https://www.cnblogs.com/blockche/p/17338472.html

相关文章

  • CF1797E 线段树 + 倍增 题解
    Preface有趣的一道ds，赛后不看题解做出来了。Solution首先有一个性质：\(\varphi(x)\)经过\(\mathcal{O}(\logx)\)次迭代后变为\(1\)。证明：若\(x\)为奇数，\(\varphi(x)=x\sum_{i=1}^{k}\frac{p_i-1}{p_i}\)，\(p_i\)为奇数，所以\(p_i-1\)为偶数，我们就能得到\(\varphi(x)......
  • LeetCode-Go：一个使用 Go 语言题解 LeetCode 的开源项目
    在中国的IT环境里，大多数场景下，学习算法的目的在于通过笔试算法题。但算法书林林总总，有时候乱花渐欲迷人眼。杜甫有诗云：读书破万卷，下笔如有神。不管选择哪本书，只要深入学习，分层次，逐层进阶，一定可以将算法攻克。笔者强烈推荐一个Github开源项目LeetCode-Go，你不仅可以把他当做......
  • 2022上半年系统集成项目案例分析真题解析（广东卷）
    2022上半年系统集成项目案例分析真题解析（广东卷）......
  • 2022上半年系统集成项目综合知识真题及解析（广东卷）
    ......
  • Vscode 卡顿、CPU 过高问题解决
    原则：非必要不要搞很多Vscode的插件，Vscode本身插件很强大，但是非必要不要使用很多插件。在VSCode扩展市场目前其实存在着不少下载量特别高但是不应该再被使用的扩展，显然官方是不可能直接给你标出来哪些扩展已经被废弃了，哪些有严重bug，纯靠扩展作者自觉。第一步：Ctrl+Shift+P：D......
  • （IDEA）spring项目导入本地jar包方法和项目打包时找不到引入本地jar包的问题解决方案
    转：（IDEA）spring项目导入本地jar包方法和项目打包时找不到引入本地jar包的问题解决方案 【Maven】理解maven的6大内置属性   ......
  • 2022年7月31日DAMA-CDGA/CDGP数据治理认证班开启！
    2022年7月31日DAMA-CDGA/CDGP数据治理认证班开启！【DAMA数据治理认证简介】为了便于国内广大数据从业者学习相关认证，DAMA中国以国际数据管理协会(简称“DAMA国际”)DAMA数据管理知识体系为基础，结合国内实际需求，对DAMA国际数据管理专业人员认证(CDMP)的考试语言、考试形式、考试内......
  • 2022年5月份深圳NPDP产品经理认证招生简章
    NPDP产品经理国际资格认证是国际公认的唯一的新产品开发专业认证，集理论、方法与实践为一体的全方位的知识体系，为公司组织层级进行规划、决策、执行提供良好的方法体系支撑。2022年5月份深圳NPDP产品经理认证招生简章【认证收益】权威国际认证：NPDP认证是产品管理领域历史最久、知名......
  • CDGA|2022年数字化落地需锻造长板 补齐短板 培养人才
    2022年政府工作报告指出，需大力提升关键软硬件技术创新和供给能力，道出了问题的关键。数字经济可为千行百业提供全新的发展动力和活力，只有牵住自主创新的“牛鼻子”，才能把数字经济自主权牢牢掌握在自己手里，让数字经济行稳致远。有专家认为，一方面，要瞄准传感器、量子信息等战略性前瞻性......
  • 2022年10月DAMA-CDGA/CDGP数据治理认证招生简章
    DAMA认证为数据管理专业人士提供职业目标晋升规划，彰显了职业发展里程碑及发展阶梯定义，帮助数据管理从业人士获得企业数字化转型战略下的必备职业能力，促进开展工作实践应用及实际问题解决，形成企业所需的新数字经济下的核心职业竞争能力。DAMA是全球唯一数据管理方面权威性认证，帮助......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99