2024牛客暑期多校训练营6

难度梯度 HB ADF IJ KC GE

A Cake

题意

Grammy 和 Oscar 两人正在进行游戏。

游戏 ①

有一个 \(n\) 个节点的树，点 \(1\) 为树的根，每条边都有一个权值(0/1)。
每次操作者可以选择当前节点的一个儿子 \(v\)，走到点 \(v\)。
两人轮流操作，Grammy 先手。
到叶子节点则游戏结束。
最终的路径为一个 \(01\) 串。

游戏②

令游戏①得到的 \(01\) 串为 \(S\)，长度为 \(m\)。
Oscar 可以将一块蛋糕分成 \(m\) 个部分（可以为空）。
两人根据 \(S\) 拿取 \(m\) 轮，每轮拿一部分蛋糕。
若 \(S_i=0\) 则第 \(i\) 轮由 Oscar 拿，否则由 Grammy 拿。

若两个人都想拿到尽可能多的蛋糕，问最终 Grammy 能拿多少蛋糕。

解题思路

首先，我们先看游戏①，对于每个节点，如果深度是奇数，说明是 Grammy 操作，否则是 Oscar 操作。

两人都会选择使自己最优的路线。即 Grammy 和 Oscar 均选择所有节点中，能使自己收益最大化的。

然后可以知道 Grammy 和 Oscar 的收益总和为 \(1\)。

我们可以定义 \(f_i\) 为点 \(i\) 对于 Oscar 的最大收益。

那么 \(f_i\) 需要根据游戏②来求。

对于游戏②，我们可以知道，如果有空的部分，那么空的部分一定是最后选择（每个人都想拿尽可能多的蛋糕）。

所以说后面的部分是空的，相当于可以把蛋糕分成 \(\le m\) 个不为空的部分。

因为大的一定先被拿，所以我们只能均分。

当我们将蛋糕均分时，Oscar 可以得到的最大收益，一定是前缀 \(0\) 的最大比例。

所以 \(f_i\) 的计算方式解决了，对于叶子节点 \(i\)，我们使 \(f_i\) 为路径的前缀 \(0\) 的最大比例。

对于非叶子节点 \(i\)，如果深度为奇数，那么 Grammy 一定选择 \(i\) 的子节点 \(j\)，使 \(f_j\) 最小。

如果深度为偶数，那么 Oscar 一定选择 \(i\) 的子节点 \(j\)，使 \(f_j\) 最大。

最终答案为 \(1-f_1\)。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
vector<array<int, 2>> adj[200005];
array<i64, 2> f[200005];
void dfs(int u, int fa, int deep, array<i64, 2> premx, array<i64, 2> pre) {
    for (auto &[to, w] : adj[u]) {
        if (to == fa) continue;
        array<i64, 2> tpremx, tpre;
        tpre = {pre[0] + !w, pre[1] + 1};
        if (premx[0] * tpre[1] < premx[1] * tpre[0]) {
            tpremx = tpre;
        } else {
            tpremx = premx;
        }
        dfs(to, u, deep + 1, tpremx, tpre);
    }
    bool flag = true;
    for (auto &[to, w] : adj[u]) {
        if (to == fa) continue;
        flag = false;
        if (f[u][1] == 0) {
            f[u] = f[to];
            continue;
        }
        if (deep & 1) {
            if (f[u][0] * f[to][1] > f[to][0] * f[u][1]) {
                f[u] = f[to];
            }
        } else {
            if (f[u][0] * f[to][1] < f[to][0] * f[u][1]) {
                f[u] = f[to];
            }
        }
    }
    if (flag) {
        f[u] = premx;
    }
}
void solve() {
    int n;
    cin >> n;
    for (int i = 1 ; i <= n ; i++) {
        adj[i].resize(0);
        f[i] = {0, 0};
    }
    for (int i = 1 ; i < n ; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    dfs(1, 1, 1, {0, 1}, {0, 0});
    cout << fixed << setprecision(12) << 1 - f[1][0] * 1.0 / f[1][1] << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--) {
        solve();   
    }
    return 0;
}

B Cake 2

题意

一个正 \(n\) 边形，若每个点都与它顺时针方向的第 \(k\) 个点相连，问能划分出几个区域。

\(4\le n\le10^6,2\le k\le n-2\)

解题思路

解题代码

代码

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);
    i64 n, k;
    cin >> n >> k;
    if (n == 2 * k) {
        cout << n << "\n";
        return 0;
    }
    k = min(k, n - k);
    i64 ans = n * k + 1;
    cout << ans << "\n";
    return 0;
}

D Puzzle: Wagiri

题意

\(n\) 个点 \(m\) 条边的无向图，每条边要么是 "Lun" 要么是 "Qie"。

每条 "Lun" 边都必须在环上，每条 "Qie" 边都必须在非环上。

你可以删掉任意多条边，使得整个图联通，请输出一种合法的剩余的边。

解题思路

可以知道所有环上的边，一定不会是桥，所以我们可以先把所有 "Lun" 边拿出来，跑 tarjan 求桥。

然后删去所有的桥，最后使用并查集将 "Qie" 边依次并入即可。

最后输出存在的边。如果所有点没有联通则说明无解。

解题代码

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;
}();
struct Graph {
    int n, tot, ccnt;
    vector<vector<int>> adj;
    vector<int> dfn, low, bridge;
    vector<array<int, 2>> edges;
    Graph(int n) : n(n), adj(n + 1), dfn(n + 1), low(n + 1), tot(0), ccnt(0) { }
    void addEdge(int u, int v) {
        adj[u].push_back(edges.size());
        edges.push_back({u, v});
        adj[v].push_back(edges.size());
        edges.push_back({v, u});
    }
    void tarjan(int u, int e) {
        dfn[u] = low[u] = ++tot;
        for (auto idx : adj[u]) {
            int to = edges[idx][1];
            if (!dfn[to]) {
                tarjan(to, idx);
                low[u] = min(low[u], low[to]);
                if (low[to] > dfn[u]) {
                    bridge.push_back(idx);
                }
            } else if (dfn[to] < dfn[u] && idx != (e ^ 1)) {
                low[u] = min(low[u], dfn[to]);
            }
        }
    }
    void cutEdge() {
        for (int i = 1 ; i <= n ; i++) {
            if (!dfn[i]) {
                tarjan(i, -1);
                ccnt++;
            }
        }
    }
}; // Graph
// 定义 Graph g(n) 表示一个 n 个点的无向图.
// 使用 g.addEdge(u, v) 进行添加无向边 (u, v).
// 使用 g.cutEdge() 即可进行割边.
// bridge 表示所有桥边的编号.
vector<array<int, 2>> edges;
int flag[200005];
int f[200005];
int find(int x) {
    return f[x] == x ? x : f[x] = find(f[x]);
}
int main() {
    int n, m;
    cin >> n >> m;
    Graph g(n);
    set<array<int, 2>> st;
    for (int i = 0 ; i < m ; i++) {
        int u, v;
        cin >> u >> v;
        if (u > v) swap(u, v);
        string type;
        cin >> type;
        if (type == "Lun") {
            flag[i] = 1;
            g.addEdge(u, v);
            st.insert({u, v});
        } else {
            flag[i] = 0;
        }
        edges.push_back({u, v});
    }
    g.cutEdge();
    for (auto &x : g.bridge) {
        auto [u, v] = g.edges[x];
        st.erase({u, v});
        st.erase({v, u});
    }
    iota(f, f + n + 1, 0);
    for (auto &[u, v] : st) {
        int tu = find(u);
        int tv = find(v);
        if (tu == tv) continue;
        f[tu] = tv;
    }
    for (int i = 0 ; i < m ; i++) {
        if (flag[i] == 0) {
            auto [u, v] = edges[i];
            int tu = find(u);
            int tv = find(v);
            if (tu == tv) continue;
            f[tu] = tv;
            st.insert({u, v});
        }
    }
    for (int i = 2 ; i <= n ; i++) {
        if (find(1) != find(i)) {
            cout << "NO\n";
            return 0;
        }
    }
    cout << "YES\n";
    cout << st.size() << "\n";
    for (auto &[u, v] : st) {
        cout << u << " " << v << "\n";
    }
    return 0;
}

F Challenge NPC 2

题意

给出一颗 \(n\) 个点 \(m\) 条边的森林，问其补图的一条曼哈顿路径。

解题思路

可以知道，当森林中树的数量 \(>1\) 时，一定有解。

我们只要将每个颗树随便取一个点为根，然后将点按深度的奇偶进行分类。

然后按顺序依次输出每颗树深度为奇数的点和深度为偶数的点即可。

这里如果只有一颗树有深度为偶数的点，那么这棵树如果是最后一个的话会不符合条件。

所以我们需要把含有深度为偶数的点的树，放到第一个，就一定能符合条件。

然后我们考虑森林中只有一颗树的情况，

当树为菊花图的时候，一定不存在解。

当树不为菊花图的时候，树的直径一定 \(\ge4\)。

那么按照深度分类后，我们可以按照深度为 \(2,4,6,…\) 输出，再按照深度为 \(1,3,5,…\) 输出。

这样能保证符合条件。

总时间复杂度 \(O(n)\)。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int f[500005], deep[500005];
bool vis[500005];
int find(int x) {
    return f[x] == x ? x : f[x] = find(f[x]);
}
vector<int> adj[500005];
vector<int> dep[500005][2];
void dfs1(int u, int p, int idx) {
    deep[u] = deep[p] + 1;
    dep[idx][deep[u] % 2].push_back(u);
    for (auto &to : adj[u]) {
        if (to == p) continue;
        dfs1(to, u, idx);
    }
}
void dfs2(int u, int p) {
    deep[u] = deep[p] + 1;
    for (auto &to : adj[u]) {
        if (to == p) continue;
        dfs2(to, u);
    }
}
vector<int> sdep[500005];
int deg[500005];
void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 0 ; i <= n ; i++) {
        f[i] = i;
        adj[i].resize(0);
        vis[i] = false;
        deep[i] = 0;
        dep[i][0].resize(0);
        dep[i][1].resize(0);
        sdep[i].resize(0);
        deg[i] = 0;
    }
    for (int i = 1 ; i <= m ; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        deg[u]++;
        deg[v]++;
        int tu = find(u), tv = find(v);
        if (tu != tv) {
            f[tu] = tv;
        }
    }
    vector<int> vec;
    for (int i = 1 ; i <= n ; i++) {
        int x = find(i);
        if (vis[x]) continue;
        vis[x] = true;
        vec.push_back(i);
    }
    if (vec.size() > 1) {
        for (auto &x : vec) {
            dfs1(x, 0, x);
        }
        for (int i = 1 ; i < (int) vec.size() ; i++) {
            if (!dep[vec[i]][0].empty()) {
                swap(vec[i], vec[0]);
            }
        }
        for (auto &x : vec) {
            for (auto &y : dep[x][1]) {
                cout << y << " ";
            }
        }
        for (auto &x : vec) {
            for (auto &y : dep[x][0]) {
                cout << y << " ";
            }
        }
        cout << "\n";
        return;
    } else {
        bool flag = true;
        for (int i = 1 ; i <= n ; i++) {
            if (deg[i] == n - 1) {
                flag = false;
                break;
            }
        }
        if (flag) {
            dfs2(1, 0);
            int idx = 1;
            for (int i = 1 ; i <= n ; i++) {
                if (deep[idx] < deep[i]) {
                    idx = i;
                }
            }
            dfs2(idx, 0);
            for (int i = 1 ; i <= n ; i++) {
                sdep[deep[i]].push_back(i);
            }
            for (int i = 1 ; i <= n ; i++) {
                if (i % 2 == 0) {
                    for (auto &x : sdep[i]) {
                        cout << x << " ";
                    }
                }
            }
            for (int i = 1 ; i <= n ; i++) {
                if (i % 2 == 1) {
                    for (auto &x : sdep[i]) {
                        cout << x << " ";
                    }
                }
            }
            cout << "\n";
        } else {
            cout << "-1\n";
        }
        return;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

H Genshin Impact's Fault

题意

一个长度为 \(n\) 的字符串，由 3,4,5,U 组成。

问这个串是否满足以下条件：

条件① 连续十个字符不能只有 3。

条件② 连续九十个字符至少要有一个5或者U。

条件③ 去掉3,4之后不存在相邻的5。

解题思路

模拟即可。

条件①和②可以用双指针判断。

条件③可以把5和U单独拿出来，看相邻字符。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
    string str;
    cin >> str;
    int n = str.size();
    int cnt3 = 0;
    bool flag = true;
    vector<pair<char, int>> vec;
    int cnt5 = 0;
    for (int i = 0 ; i < n ; i++) {
        if (str[i] == '3') {
            cnt3++;
        }
        if (str[i] == '5') {
            cnt5++;
            vec.push_back({'5', i});
        }
        if (str[i] == 'U') {
            cnt5++;
            vec.push_back({'U', i});
        }
        if (cnt3 >= 10) {
            flag = false;
            break;
        }
        if (i >= 89) {
            if (cnt5 == 0) {
                flag = false;
                break;
            }
            if (str[i - 89] == '5') {
                cnt5--;
            }
            if (str[i - 89] == 'U') {
                cnt5--;
            }
        }
        if (i >= 9) {
            if (str[i - 9] == '3') {
                cnt3--;
            }
        }
    }
    int len = vec.size();
    for (int i = 1 ; i < len ; i++) {
        if (vec[i].first == '5' && vec[i - 1].first == '5') {
            flag = false;
            break;
        }
    }
    cout << (flag ? "valid" : "invalid") << "\n";
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

I Intersecting Intervals

题意

有 \(n\) 行 \(m\) 列的矩阵，

对于每一行选择一个区间，相邻两行的区间必须有交集。

问选择的区间的元素的和的最大值。

\(n*m\le10^6\)

解题思路

考虑到相邻两行区间必须有交集，所以我们可以定义一个数组 \(dp_{i,j}\) 为前 \(i\) 行交点含有 \(j\) 的和的最大值。

目前我们只考虑一行，那就是枚举中心，然后向左向右一直尽可能的扩大。

其实也就是处理一个以 \(j\) 结尾的前缀和的最大值 \(summxL\) 和以 \(j\) 为结尾的后缀和的最大值 \(summxR\)。

所以有 \(dp_{i,j}=dp_{i-1,j}+summxL_{i,j-1}+summxR_{i,j+1}-a_{i,j}\)。

但是交点含有，并不一定就是中心，所以我们还需要考虑中心在左侧和中心在右侧。

假设中心在左侧，那么一定是左边的一段加上以这个中心往右的最大后缀和。

也就是定义一个数组 \(dpL_{i,j}\) 表示第 \(i\) 行区间右端点为 \(j\) 的最大答案。

得到递推式：\(dpL_{i,j}=\max(dpL_{i,j-1}+a_{i,j},dp_{i-1,j}+summxL_{i,j})\)

同理 \(dpR_{i,j}\) 表示第 \(i\) 行区间左端点为 \(j\) 的最大答案。

最终得到 \(dp_{i,j}=\max(dp_{i-1,j}+summxL_{i,j-1}+summxR_{i,j+1}-a_{i,j},dpL_{i,j-1}+summxR_{i,j},dpR_{i,j+1}+summxL_{i,j})\)。

滚动优化空间即可。

总时间复杂度 \(O(n*m)\)。

解题代码

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;
}();
i64 a[1000005], dp[1000005], g[1000005];
i64 summxL[1000005], summxR[1000005];
i64 dpL[1000005], dpR[1000005];
void solve() {
    int n, m;
    cin >> n >> m;
    fill(dp, dp + m + 1, 0);
    for (int i = 1 ; i <= n ; i++) {
        for (int j = 1 ; j <= m ; j++) {
            cin >> a[j];
        }
        summxL[0] = -2e17;
        dpL[0] = -2e17;
        for (int j = 1 ; j <= m ; j++) {
            summxL[j] = max(summxL[j - 1] + a[j], a[j]);
            dpL[j] = max(dpL[j - 1] + a[j], dp[j] + summxL[j]);
        }
        summxR[m + 1] = -2e17;
        dpR[m + 1] = -2e17;
        for (int j = m ; j >= 1 ; j--) {
            summxR[j] = max(summxR[j + 1] + a[j], a[j]);
            dpR[j] = max(dpR[j + 1] + a[j], dp[j] + summxR[j]);
        }
        for (int j = 1 ; j <= m ; j++) {
            g[j] = max({dp[j] + summxL[j] + summxR[j] - a[j], dpL[j - 1] + summxR[j], dpR[j + 1] + summxL[j]});
        }
        for (int j = 1 ; j <= m ; j++) {
            dp[j] = g[j];
        }
    }
    i64 ans = -2e17;
    for (int i = 1 ; i <= m ; i++) {
        ans = max(ans, dp[i]);
    }
    cout << ans << "\n";
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

J Stone Merging

题意

有 \(n\) 堆石头，每堆石头只有一个编号为 \(a_i\) 石头。

有 \(k-1\) 台机器，编号为 \(2\sim k\)。

编号为 \(i\) 的机器可以合并 \(i\) 堆石头，

规则为，将所有编号为 \(i\) 的石头合并为一堆，其余的石头再合并为另一堆，在这之后编号为 \(i\) 的机器损坏，不可再次使用。

请构造出方案使得 \(n\) 个堆石头合并成一堆时候，无解输出 \(-1\)。

解题思路

首先我们可以知道，当\(n=k=a_1=a_2=2\) 时，使用机器 \(2\) 即可一次合并完成。

否则当编号 \(2\sim k\) 的石头都存在时，无论如何都不能将 \(n\) 堆石头合并成 \(1\) 堆石头。

接下来，我们找到一个编号 \(x\)，保证 \(x<k\) 且没有编号为 \(x\) 的石头。

每次使用机器 \(x\)，会使得石头数量减少 \(x-1\)。

那么当 \(n=z*(x-1)+1,z\in N^+\)，我们只需要机器 \(x\) 就能使所有石头合并成一堆。

当 \(n\ne z*(x-1)+1\) 时，我们需要把 \(n\) 减少为 \(z*(x-1)+1\)。

那么我们只需要减少 \((n-1)\mod(x-1)\) 个堆。

所以我们需要使用机器 \((n-1)\mod(x-1)+1\)。

令 \(y=(n-1)\mod(x-1)+1\)，

我们可以找到 \(y\) 个编号不为 \(y\) 的石头或者 \(y\) 个编号为 \(y\) 的石头，这样可以满足条件。

已知 \(y\le\frac{n}{2}\)，这样保证了要么存在至少 \(y\) 个编号不为 \(y\) 的石头，要么存在至少 \(y\) 个编号为 \(y\) 的石头。

最后使用机器 \(x\) 模拟即可。

解题代码

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 a[300005];
int cnt[100005];
void solve() {
    int n, k;
    cin >> n >> k;
    for (int i = 1 ; i <= n ; i++) {
        cnt[i] = 0;
    }
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        cnt[a[i]]++;
    }
    int x = -1;
    for (int i = 2 ; i <= k ; i++) {
        if (cnt[i] == 0) {
            x = i;
            break;
        }
    }
    if (n == 2 && cnt[2] == 2) {
        cout << "1\n2 1 2\n";
        return;
    }
    if (x == -1) {
        cout << -1 << "\n";
        return;
    }
    vector<vector<int>> ans;
    int y = (n - 1) % (x - 1) + 1;
    int tot = n;
    if (y > 1) {
        vector<int> vec;
        if (cnt[y] >= y) {
            for (int i = 1 ; i <= n ; i++) {
                if (a[i] == y) {
                    vec.push_back(i);
                    a[i] = 0;
                    if (vec.size() == y) {
                        break;
                    }
                }
            }
            a[++tot] = 1;
            a[++tot] = 0;
        } else {
            for (int i = 1 ; i <= n ; i++) {
                if (a[i] != y) {
                    vec.push_back(i);
                    a[i] = 0;
                    if (vec.size() == y) {
                        break;
                    }
                }
            }
            a[++tot] = 0;
            a[++tot] = 1;
        }
        ans.push_back(vec);
    }
    n -= y - 1;
    int r = 1;
    while (n > 1) {
        vector<int> vec;
        while (r <= tot) {
            if (a[r] != 0) {
                vec.push_back(r);
            }
            r++;
            if (vec.size() == x) {
                break;
            }
        }
        n -= x - 1;
        ans.push_back(vec);
        a[++tot] = 0;
        a[++tot] = 1;
    }
    cout << ans.size() << "\n";
    for (auto &vec : ans) {
        cout << vec.size() << " ";
        for (auto &x : vec) {
            cout << x << " ";
        }
        cout << "\n";
    }
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}