牛客春招刷题训练营-2025.5.23题解

3 活动地址： 牛客春招刷题训练营 - 编程打卡活动

简单题 小红吃药

模拟题。
字符串存小红当前的患病状态， 数组存每副药能治疗的症状， 数组存每副药带来的副作用。
服一副药：

1. 如果 且 ，将 设置成 。
2. 如果 且 ，将 设置成 。

服完一副药后输出 中 的个数。
时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int m;
    cin >> m;
    vector<string> z(m), f(m);
    for (int i = 0; i < m; i++)cin >> z[i] >> f[i];
    int q;
    cin >> q;
    while (q--) {
        int u;
        cin >> u;
        u--;
        for (int i = 0; i < n; i++) {
            if (s[i] == '1' && z[u][i] == '1')
                s[i] = '0';
            if (s[i] == '0' && f[u][i] == '1')
                s[i] = '1';
        }
        cout << count(s.begin(), s.end(), '1') << '\n';
    }
    return 0;
}

中等题 小红和小紫的取素因子游戏

发现该博弈论二人无论如何决策，并不能改变最终游戏结果，游戏结果只与 的质因数个数有关，如果素因子个数为奇数则小红赢，否则小紫赢。
使用 的算法对 分解质因数，求质因数个数即可。
时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin >> t;
    while (t--) {
        int x;
        cin >> x;
        int ans = 0;
        for (int i = 2; i <= sqrt(x); i++) {
            while (x % i == 0) {
                x /= i;
                ans++;
            }
        }
        if (x != 1)ans++;
        cout << (ans % 2 == 1 ? "kou\n" : "yukari\n");
    }
}

困难题 小红送外卖

看起来挺吓人，但题意要求小红外卖送到学校后必须返回美食城，每次只能送一个学校的订单，记 为 节点到 号节点的距离，那就是求 。
使用堆优化的 dijkstra 算法求出 数组，输出 即能通过本题。
时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<pair<int, long long>>> ver(n + 1);
    vector<long long> dis(n + 1, 1e18);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        ver[u].push_back({v, w});
        ver[v].push_back({u, w});
    }
    using PLLI = pair<long long, int>;
    priority_queue<PLLI, vector<PLLI>, greater<PLLI>> pq;
    pq.emplace(0, 1);
    dis[1] = 0;
    vector<int> vis(n + 1);
    while (!pq.empty()) {
        int x = pq.top().second;
        pq.pop();
        if (vis[x])
            continue;
        vis[x] = 1;
        for (auto [y, w] : ver[x]) {
            if (dis[y] > dis[x] + w) {
                dis[y] = dis[x] + w;
                pq.emplace(dis[y], y);
            }
        }
    }
    long long ans = 0;
    while (q--) {
        int a;
        cin >> a;
        ans += 2 * dis[a];
    }
    cout << ans << '\n';
    return 0;
}