2024牛客暑期多校训练营3

难度梯度 LB AJD EH KCI FG

A Bridging the Gap 2

题意

有 \(n\) 个人在左岸，每个人有体力 \(h_i\)，

有一艘船，每次可以载 \([L,R]\) 人到对岸，这些人的体力都要减 \(1\)，体力为 \(0\) 的人不能坐船。

问能否让所有人都到右岸。

解题思路

我们可以知道我们要将 \(n\) 个人全部送到对岸，至少要来回 \(\lceil\dfrac{n-R}{R-L}\rceil\) 轮。

令 \(S=\lceil\dfrac{n-R}{R-L}\rceil\)。

第 \(i\) 个人可以来回 \(d_i=\lfloor\dfrac{h_i-1}{2}\rfloor\) 轮，但是如果 \(d_i>S\)，此时这个人的贡献是 \(S\)，不然这个人会一个人抵多个人。

所以每个人的贡献为 \(s_i=\min(d_i,S)\)，

然后 \(S\) 轮，那么一共需要 \(S*L\) 个贡献。

所以当 \(\sum_{i=1}^ns_i\ge S*L\) ，则一定能将所有人送到对岸。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int h[500005];
int main() {
    int n, L, R;
    cin >> n >> L >> R;
    for (int i = 1 ; i <= n ; i++) {
        cin >> h[i];
    }
    i64 S = ((n - R) + (R - L) - 1) / (R - L);
    i64 sum = 0;
    for (int i = 1 ; i <= n ; i++) {
        sum += min<i64>((h[i] - 1) / 2, S);
    }
    if (sum >= S * L) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
    return 0;
}

B Crash Test

题意

给出两个正整数 \(n,D\)。

现在有 \(n\) 个数，为 \(h_i\)。

可以进行任意次操作，每次操作选择一个下标 \(i\)，使 \(D=|D-h_i|\)。

问 \(D\) 最小能达到多少。

\(1\le n\le100\)

\(1\le h,D\le10^{18}\)

解题思路

其实可以知道对于每个下标，都可以使得 \(D=D\%h_i\) 或 \(D=D-D\%h_i\)

令 \(g=\gcd(h_1,h_2,…,h_n)\)。

由裴蜀定理可得，一定存在一些操作，可以得到 \(D\%g\)

当我们再进行一系列操作可以通过绝对值得到 \(g-D\%g\)。

我们答案对这两种情况取 \(\min\) 即可，即 \(ans=\min(D\%g,g-D\%g)\)

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    i64 D;
    cin >> n >> D;
    i64 g = 0;
    for (int i = 0 ; i < n ; i++) {
        i64 x;
        cin >> x;
        g = __gcd(g, x);
    }
    D %= g;
    cout << min(D, (g - D));
    return 0;
}

D Dominoes!

题意

有 \(n\) 个卡片，每个卡片左右数字分别为 \(a_i,b_i\)，你可以交换同一个卡片上的两个数字。

问你是否可以随机排列这 \(n\) 张卡片为一行，保证相邻卡片左边卡片的右边数字与右边卡片的左边数字不同。

如果可以请输出顺序，否则输出 "No"。

解题思路

首先我们可以发现，不好处理的是 \(a_i=b_i\) 的卡片。

所以我们先处理 \(a_i=b_i\) 的卡片。

我们可以使用一种贪心，将卡片按照数量放入堆，

每次取数量最多的卡片，看是否能接，如果不能接，就取数量次多的卡片。

如果有解，一定剩下 \(\le1\) 种卡片。

接下来，我们只需要依次从 \(a_i\neq b_i\) 的卡片中，取一个接过来，然后再看能否把 \(a_i=b_i\) 的这一种接后面。

一直循环到所有 \(a_i\neq b_i\) 的卡片都接完之后。

如果我们接的卡片恰好有 \(n\) 个，那么说明有解，按顺序输出。否则输出 "No"。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int main() {
    int n;
    cin >> n;
    vector<array<int, 2>> vec;
    map<int, int> sa;
    for (int i = 0 ; i < n ; i++) {
        int x, y;
        cin >> x >> y;
        if (x > y) swap(x, y);
        if (x == y) {
            sa[x]++;
        } else {
            vec.push_back({x, y});
        }
    }
    priority_queue<array<int, 2>> que;
    for (auto &[x, y] : sa) {
        que.push({y, x});
    }
    vector<array<int, 2>> ans;
    while (!que.empty()) {
        auto [x1, y1] = que.top();
        que.pop();
        if (ans.empty() || ans.back()[1] != y1) {
            ans.push_back({y1, y1});
            x1--;
            if (x1 > 0) {
                que.push({x1, y1});
            }
        } else {
            if (que.empty()) {
                if (x1 > 0) {
                    que.push({x1, y1});
                }
                break;
            }
            auto [x2, y2] = que.top();
            que.pop();
            ans.push_back({y2, y2});
            x2--;
            if (x1 > 0) {
                que.push({x1, y1});
            }
            if (x2 > 0) {
                que.push({x2, y2});
            }
        }
    }
    while (!vec.empty()) {
        auto [x, y] = vec.back();
        vec.pop_back();
        if (!ans.empty() && ans.back()[1] == x) {
            swap(x, y);
        }
        ans.push_back({x, y});
        if (!que.empty()) {
            auto [x1, y1] = que.top();
            que.pop();
            if (ans.empty() || ans.back()[1] != y1) {
                ans.push_back({y1, y1});
                x1--;
            }
            if (x1 > 0) {
                que.push({x1, y1});
            }
        }
    }
    if (ans.size() == n) {
        cout << "Yes\n";
        for (auto &[x, y] : ans) {
            cout << x << " " << y << "\n";
        }
    } else {
        cout << "No\n";
    }
    return 0;
}

E Malfunctioning Typewriter

题意

有一个 \(01\) 打字机，每次输入 \(0\) 或 \(1\)，有 \(p\) 的概率打出正确的数字，\(1-p\) 的概率打出错误的数字。

给定 \(n\) 个长度为 \(m\) 的 \(01\) 串，要求用打字机以任意顺序输出者 \(n\) 个串，问最大成功概率。

解题思路

我们对 \(n\) 个串建立 \(trie\)。

按题目的要求，我们应该是在 \(trie\) 上走 \(n\) 轮。

每轮走完之后，删掉对应的节点。

如果要成功的走 \(n\) 轮，那么对于 \(trie\) 上的每个节点，若左儿子数量为 \(x\)，右儿子数量为 \(y\)，

则我们一定恰好经过该节点 \(x+y\) 次，等价于打出\(x\) 次 \(0\)，和 \(y\) 次 \(1\)。

所以我们的答案为 \(\prod_u f(sz(ls_u),sz(rs_u))\)。

\(f(x,y)\) 表示为恰好打出 \(x\) 个 \(0\) 和 \(y\) 个 \(1\) 的最大概率。

当 \(x,y\ge1\) 有 \(f(x,y)=p*\max(f(x-1,y),f(x,y-1))+(1-p)*\min(f(x-1,y),f(x,y-1))\)。

当 \(y=0\) 有 \(f(x,0)=p*f(x-1,0)\)。

当 \(x=0\) 有 \(f(0,y)=p*f(0,y-1)\)。

通过递推即可算出 \(f(x,y)\)。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int tr[1000005][2], tot, cnt[1000005][2];
double f[1005][1005];
void insert(string str) {
    int p = 0;
    int len = str.size();
    for (int i = 0 ; i < len ; i++) {
        int k = str[i] - '0';
        if (!tr[p][k]) tr[p][k] = ++tot;
        cnt[p][k]++;
        p = tr[p][k];
    }
}
int main() {
    int n, m;
    double p;
    cin >> n >> m >> p;
    for (int i = 1 ; i <= n ; i++) {
        string str;
        cin >> str;
        insert(str);
    }
    double q = 1 - p;
    f[0][0] = 1;
    for (int i = 1 ; i <= n ; i++) {
        f[i][0] = f[i - 1][0] * p;
        f[0][i] = f[0][i - 1] * p;
    }
    for (int i = 1 ; i <= n ; i++) {
        for (int j = 1 ; j <= n ; j++) {
            f[i][j] = p * max(f[i - 1][j], f[i][j - 1]) + q * min(f[i - 1][j], f[i][j - 1]);
        }
    }
    double ans = 1;
    for (int i = 0 ; i <= tot ; i++) {
        ans *= f[cnt[i][0]][cnt[i][1]];
    }
    cout << fixed << setprecision(12) << ans << "\n";
    return 0;
}

H Rectangle Intersection

题意

在一个 \(n*m\) 的方格中，给了你 \(k\) 个矩形。

问任意 \(\ge1\) 个矩形相交的矩形面积的最小值。

解题思路

普遍来讲，多个矩形的交一定是一个矩形。

而且这个矩形的左上角的点，一定在其中矩形的上界线和左界线上，同理其他点也是。

所以我们只要枚举所有点是否可以作为这个交的左上角的点，如果可以，就确定了上界线和左界线，

那么我们只需要找到最近的下界线和左界线就可以计算出这个交的面积了。

对所有的面积取 \(\min\) 即可算出答案。

这里只要我们添加一个全覆盖的矩形，就可以处理单个矩形的情况了。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int su[2005][2005], sd[2005][2005], sl[2005][2005], sr[2005][2005];
int fu[2005][2005], fd[2005][2005], fl[2005][2005], fr[2005][2005];
void add(int x1, int y1, int x2, int y2) {
    su[x1][y1]++; su[x1][y2 + 1]--;
    sd[x2][y1]++; sd[x2][y2 + 1]--;
    sl[x1][y1]++; sl[x2 + 1][y1]--;
    sr[x1][y2]++; sr[x2 + 1][y2]--;
}
int main() {
    int n, m, k;
    cin >> n >> m >> k;
    add(1, 1, n, m);
    for (int i = 1 ; i <= k ; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        add(x1, y1, x2, y2);
    }
    for (int i = 1 ; i <= n ; i++) {
        for (int j = 1 ; j <= m ; j++) {
            su[i][j] += su[i][j - 1];
            sd[i][j] += sd[i][j - 1];
            sl[i][j] += sl[i - 1][j];
            sr[i][j] += sr[i - 1][j];
        }
    }
    for (int i = 1 ; i <= n ; i++) {
        for (int j = 1 ; j <= m ; j++) {
            fu[i][j] = su[i][j] ? i : fu[i - 1][j];
            fl[i][j] = sl[i][j] ? j : fl[i][j - 1];
        }
    }
    for (int i = n ; i >= 1 ; i--) {
        for (int j = m ; j >= 1 ; j--) {
            fd[i][j] = sd[i][j] ? i : fd[i + 1][j];
            fr[i][j] = sr[i][j] ? j : fr[i][j + 1];
        }
    }
    i64 ans = 0X7fffffffffffffff;
    for (int i = 1 ; i <= n ; i++) {
        for (int j = 1 ; j <= m ; j++) {
            if (fu[i][j] == i && fl[i][j] == j) {
                ans = min(ans, 1LL * (fd[i][j] - fu[i][j] + 1) * (fr[i][j] - fl[i][j] + 1));
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

J Rigged Games

题意

有 \(A,B\) 两个玩家，他们再进行一个大比赛，这个大比赛的规则是，谁先赢得 \(b\) 场，谁就获胜。

每个大比赛又由若干小比赛组成，小比赛的规则是，谁先赢得 \(a\) 场，谁就获胜。

给了一个 \(01\) 串，\(0\) 代表 \(A\) 失败，\(1\) 代表 \(A\) 获胜。

问从第 \(i\) 个位置循环，确定小比赛中每一轮的胜负，问最终大比赛 \(A\) 的胜负情况。

解题思路

我们可以知道，我们要先确定小比赛的胜负，那么我们需要从第 \(i\) 个位置开始，进行一次小比赛，谁获胜了，到第几个位置开始下一轮比赛。

这里我们定义 \(nxt_{i,j}\) 为从第 \(i\) 个位置开始，进行 \(2^j\) 轮小比赛后，下一轮小比赛开始的位置。

定义 \(f_{i,j}\) 为从第 \(i\) 个位置开始，进行 \(2^j\) 轮小比赛后，\(A,B\) 的获胜情况。

我们可以使用双指针求出 \(f_{i,0}\) 和 \(nxt_{i,0}\)，后通过倍增求出 \(f_{i,j}\) 和 \(nxt_{i,j}\)。

最后对每个起点进行倍增快速计算 \(A\) 是否胜利即可。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int nxt[300005][20];
array<int, 2> f[300005][20];
string ans;
int main() {
    int n, a, b;
    cin >> n >> a >> b;
    string s;
    cin >> s;
    while ((int) s.size() <= (n + 2 * a - 1)) {
        s = s + s;
    }
    { // 双指针暴力初始状态
        int L = 0, R = 0, x = 0, y = 0;
        while (L < n && R < (int) s.size()) {
            if (s[R] == '1') {
                x++;
            } else {
                y++;
            }
            while (x == a || y == a) {
                nxt[L][0] = (R + 1) % n;
                f[L][0] = {x == a, y == a};
                if (s[L] == '1') {
                    x--;
                } else {
                    y--;
                }
                L++;
            }
            R++;
        }
    }
    { // 倍增
        for (int j = 1 ; j < 20 ; j++) {
            for (int i = 0 ; i < n ; i++) {
                nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
                f[i][j] = {f[i][j - 1][0] + f[nxt[i][j - 1]][j - 1][0], f[i][j - 1][1] + f[nxt[i][j - 1]][j - 1][1]};
            }
        }
    }
    for (int i = 0 ; i < n ; i++) {
        int pos = i, x = 0, y = 0;
        for (int j = 19 ; j >= 0 ; j--) {
            auto [dx, dy] = f[pos][j];
            if (x + dx >= b || y + dy >= b) {
                continue;
            }
            x += dx;
            y += dy;
            pos = nxt[pos][j];
        }
        x += f[pos][0][0];
        y += f[pos][0][1];
        if (x >= b) {
            ans += '1';
        } else {
            ans += '0';
        }
    }
    cout << ans;
    return 0;
}

K Slay the Spire: Game Design

题意

\(n\) 个点 \(m\) 条边的有向无环图。

没有入度的点为源点，没有出度的点为汇点。

你可以在任意非源点和非汇点放一个怪物。

要你保证从任意源点出发，到任意汇点结束，路径中至少遇到 \(k\) 只怪物。

问放的怪物的最少数量，和放在哪些点。无论如何都无法满足输出 \(-1\)。

\(2\le n\le1000,1\le m\le5000,1\le k\le5\)。

解题思路

我们考虑最小割。

将每个点先分成 \(k\) 个点分别代表遇到不超过 \(0,1,2,…,k-1\) 只怪物，然后再将每个点分为入点和出点。

对于编号为 \(1\) 的点，表示为 \(1(0,0),1(1,0),1(k-1,0),1(0,1),1(1,1),1(k-1,1)\)

对非源点和非汇点 \(x\)，将入点 \(x(y,0)\) 向出点 \(x(y,1)\) 连一条容量为 \(1\) 的边，相当于经过这个点且这个点有一只怪物。

对点 \(x\)，将入点 \(x(y,0)\) 向出点 \(x(y+1,1)\) 连一条容量为 \(\infty\) 的边，相当于经过这个点且这个点没有怪物。

对边 \((x,y)\)，我们有 \(x\) 的出点 \(x(z,1)\) 向 \(y\) 的入点 \(y(z,0)\) 之间连一条容量为 \(\infty\) 的边，相当于我们我们从 \(x\) 点走向 \(y\) 点。

对于源点 \(x\)，将超级源点 \(S\) 向出点 \(x(0,1)\) 连一条容量为 \(\infty\) 的边，相当于从任意源点出发。

对于汇点 \(x\)，将入点 \(x(k-1,0)\) 向超级汇点 \(T\) 连一条容量为 \(\infty\) 的边，相当于从任意汇点结束。

当我们建立的图不连通时，最小割为 \(0\)，此时无解。

当我们建立的图联通，但是最小割为 \(\infty\) 时，此时无解。

剩余的情况就是有解的，但是点的个数并不是最小割，

对于每个非源点和非汇点，我们都连了 \(k\) 条边来判断这个点上是否会有怪物。

最小割可能割掉其中一条边，但是也可能割掉其中多条边，所以我们还需要遍历所有的边，将点加入集合中去重。

最后输出即可。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
template <class T>
struct Flow {
    const int n;
    vector<pair<int, T>> edges;
    vector<vector<int>> adj;
    vector<int> cur, dep;
    Flow(int n) : n(n), adj(n) {}
    bool bfs(int s, int t) {
        dep.assign(n, -1);
        queue<int> q;
        dep[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto &idx : adj[u]) {
                auto [to, w] = edges[idx];
                if (w > 0 && dep[to] == -1) {
                    dep[to] = dep[u] + 1;
                    if (to == t) {
                        return true;
                    }
                    q.push(to);
                }
            }
        }
        return false;
    }
    T dfs(int u, int t, T f) {
        if (u == t) {
            return f;
        }
        T res = f;
        for (int &i = cur[u] ; i < (int) adj[u].size() ; i++) {
            int idx = adj[u][i];
            auto [to, w] = edges[idx];
            if (w > 0 and dep[to] == dep[u] + 1) {
                T out = dfs(to, t, min(res, w));
                edges[idx].second -= out;
                edges[idx ^ 1].second += out;
                res -= out;
                if (res == 0) {
                    return f;
                }
            }
        }
        return f - res;
    }
    void add(int u, int v, T c) {
        adj[u].push_back(edges.size());
        edges.push_back({v, c});
        adj[v].push_back(edges.size());
        edges.push_back({u, 0});
    }

    T dinic(int s, int t) {
        T ans = 0;
        while (bfs(s, t)) {
            cur.assign(n, 0);
            ans += dfs(s, t, numeric_limits<T>::max());
        }
        return ans;
    }
}; // Flow
int tot = 0;
int idx[1005][5][2];
int din[1005], dout[1005];
int main() {
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1 ; i <= n ; i++) {
        for (int j = 0 ; j < k ; j++) {
            for (int x = 0 ; x <= 1 ; x++) {
                idx[i][j][x] = ++tot;
            }
        }
    }
    int superS = ++tot, superT = ++tot;
    Flow<i64> flow(tot + 1);
    for (int i = 0 ; i < m ; i++) {
        int u, v;
        cin >> u >> v;
        dout[u]++; din[v]++;
        for (int j = 0 ; j < k ; j++) {
            flow.add(idx[u][j][1], idx[v][j][0], 1e9);
        }
    }
    for (int i = 1 ; i <= n ; i++) {
        if (din[i] == 0) {
            flow.add(superS, idx[i][0][1], 1e9);
        } else if (dout[i] == 0) {
            flow.add(idx[i][k - 1][0], superT, 1e9);
        } else {
            for (int j = 0 ; j < k ; j++) {
                flow.add(idx[i][j][0], idx[i][j][1], 1);
            }
            for (int j = 1 ; j < k ; j++) {
                flow.add(idx[i][j - 1][0], idx[i][j][1], 1e9);
            }
        }
    }
    i64 res = flow.dinic(superS, superT);
    if (res == 0 || res >= 1e9) {
        cout << "-1\n";
    } else {
        set<int> ans;
        for (int i = 1 ; i <= n ; i++) {
            for (int j = 0 ; j < k ; j++) {
                if (flow.dep[idx[i][j][0]] == -1) continue;
                for (auto &id : flow.adj[idx[i][j][0]]) {
                    int to = flow.edges[id].first;
                    if (to == idx[i][j][1] && flow.dep[to] == -1) {
                        ans.insert(i);
                    }
                }
            }
        }
        cout << ans.size() << "\n";
        for (auto &x : ans) {
            cout << x << " ";
        }
    }
    return 0;
}

L Sudoku and Minesweeper

题意

给出一个 \(9*9\) 的数独，你可以选择任意数量的任意点变成地雷 '*' (不可以全选)

请构造出最终结果的数字对应的是周围八格地雷个数的 \(9*9\) 方阵。

解题思路

可以知道每一行每一列都至少存在一个 \(8\)，而 \(8\) 的周围可以全是地雷。

那么我们只需要选一个不在第一行/第一列/最后一行/最后一列的 \(8\) ，除了这个 \(8\) 以外都放地雷即可。

解题代码

代码

Text Only

```c++
#include <bits/stdc++.h>
using namespace std;
string g[10];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for (int i = 1 ; i <= 9 ; i++) {
        cin >> g[i];
        g[i] = " " + g[i];
    }
    int x, y;
    for (int i = 2 ; i <= 8 ; i++) {
        for (int j = 2 ; j <= 8 ; j++) {
            if (g[i][j] == '8') {
                x = i;
                y = j;
                for (int i = 1 ; i <= 9 ; i++) {
                    for (int j = 1 ; j <= 9 ; j++) {
                        if (i != x || j != y) {
                            cout << "*";
                        } else {
                            cout << "8";
                        }
                    }
                    cout << "\n";
                }
                return 0;
            }
        }
    }
    return 0;
}
```