2022 CCPC Mianyang Onsite

A. Ban or Pick, What’s the Trick

题目大意

两个队伍分别有$n$个英雄可以选择，价值分别为$a_1, \cdots, a_n$和$b_1, \cdots, b_n$
两队轮流操作，每次可以选己方英雄池内$1$个英雄或者禁用对方英雄池内$1$个英雄
最终每方得分为选取英雄价值前$k$大的价值和，对于一方来说，得分差越大方案越优，求双方在最优策略下，两队得分差

解题思路

两个显然的贪心：
$1.$选英雄一定选己方英雄池价值最大的，禁英雄一定禁对方英雄池价值最大的
$2.$当一方选满$k$个英雄后肯定不会再选英雄，只会禁英雄
由贪心性质可知状态数只有$O(nk^2)$个，所以可以记忆化搜索$dp(x,i,j)$表示当前双方共操作$x$轮，分别已选取$i$，$j$个英雄时的答案
一个重要的点是确定$(x,i,j)$后，双方已经被选/禁的英雄个数$p$，$q$是可以确定的
$p=\lfloor\frac{x}{2}\rfloor+i-j$
$q=\lfloor\frac{x+1}{2}\rfloor-i+j$

具体代码

#include <bits/stdc++.h>
using ll = long long;
using PII = std::pair<int, int>;
const int N = 2e5 + 10;
const int M = 15;
const ll INF = 0x7f7f7f7f7f7f7f7f;
ll a[N], b[N];
ll dp[N][M][M];
ll n, k;
ll dfs(int round, int cura, int curb)
{
    if (round == 2 * n)
        return 0;
    if (dp[round][cura][curb] != -1)
        return dp[round][cura][curb];
    int nowa = round / 2 - curb + cura; 
    int nowb = (round + 1) / 2 - cura + curb;
    if (round % 2 == 0)
    {
        ll ans = -INF;
        if (cura != k && nowa != n)
            ans = std::max(ans, dfs(round + 1, cura + 1, curb) + a[nowa + 1]);
        ans = std::max(ans, dfs(round + 1, cura, curb));
        return dp[round][cura][curb] = ans;
    }
    else
    {
        ll ans = INF;
        if (curb != k && nowb != n)
            ans = std::min(ans, dfs(round + 1, cura, curb + 1) - b[nowb + 1]);
        ans = std::min(ans, dfs(round + 1, cura, curb));
        return dp[round][cura][curb] = ans;
    }
}
void solve()
{
    memset(dp, -1, sizeof dp);
    std::cin >> n >> k;
    for (int i = 1; i <= n; ++i)
        std::cin >> a[i];
    for (int i = 1; i <= n; ++i)
        std::cin >> b[i];
    std::sort(a + 1, a + n + 1, std::greater<ll>());
    std::sort(b + 1, b + n + 1, std::greater<ll>());
    ll ans = dfs(0, 0, 0);
    std::cout << ans << '\n';
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T = 1;
    // std::cin >> T;
    while (T--)
        solve();
    return 0;
}

C. Catch You Catch Me

题目大意

一颗树，根节点是$1$号，除了根节点以外每个节点上初始都有一个蝴蝶，根节点是出口，每一秒所有蝴蝶都会朝着根节点逃跑(跑到父亲节点)，问拦截所有蝴蝶的最少操作次数，每次操作可以瞬移到一个节点，抓住该节点上的所有蝴蝶

解题思路

容易注意到答案是$1$号节点的所有孩子的子树深度之和

具体代码

#include <bits/stdc++.h>
using ll = long long;
using PII = std::pair<int, int>;
const int N = 2e5 + 10;
const int M = 10;
const ll INF = 0x7f7f7f7f7f7f7f7f;
int n;
std::vector<int> e[N];
ll dfs(int u, int fa, int d)
{
    if (e[u].size() == 1)
        return d;
    ll res = 0;
    for (auto v : e[u])
    {
        if (v == fa)
            continue;
        res = std::max(dfs(v, u, d + 1), res);
    }
    return res;
}
void solve()
{
    std::cin >> n;
    for (int i = 1; i <= n - 1; ++i)
    {
        int u, v;
        std::cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    ll ans = 0;
    for (auto v : e[1])
        ans += dfs(v, 1, 1);
    std::cout << ans << '\n';
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T = 1;
    // std::cin >> T;
    while (T--)
        solve();
    return 0;
}

D. Gambler’s Ruin

题目大意

曼联和曼城比赛，你作为开盘手要给两个队设置赔率
有$n$个赌怪，第$i$个赌怪对曼联的胜率预测是$p_i$
若你设曼联的赔率为$x$，曼城的赔率为$y$，那么对于第$i$个赌怪：
若$p_i\cdot x\gt 1$，这个人会押$c_i$的钱在曼联
否则，若$(1-p_i)\cdot y\gt 1$，这个人会押$c_i$的钱在曼城
记赌怪们在曼联上的下注总和是$s_x$，在曼城上的下注总和是$s_y$，如果曼联赢了，博彩公司要付$s_x\cdot x$这么多钱，如果曼城赢了要付$s_y\cdot y$这么多钱
最坏情况下，博彩公司的利润是$s_x+s_y-max(s_x\cdot x, s_y\cdot y)$
现在你要设置$x$，$y$最大化最坏情况下博彩公司的利润

解题思路

以$p_i$为关键字从大到小对赌怪排序，那么所有$p_i\geq \frac{1}{x}$的赌怪都会下注曼联，那么$s_x$是一个前缀和形式
同理，$s_y$会是一个后缀和形式
记排序后$c_i$的前缀和为$pre_i$，后缀和为$suf_i$
有一个贪心性质：
假设前缀与后缀已经固定，$i$为下注曼联的前缀的最后一个人的指针，$j$为下注曼城的后缀的第一个人的指针，也就是固定了$s_x$和$s_y$，同时有$\frac{1}{p_i}\leq x\lt \frac{1}{p_{i+1}}$，$\frac{1}{1-p_j}\leq y\lt \frac{1}{1-p_{j-1}}$
那么为了最大化$res=s_x+s_y-max(s_x\cdot x, s_y\cdot y)$，令$x=\frac{1}{p_i}$，$y=\frac{1}{1-p_j}$显然最优
此时，$res$可改写为$res=pre_i+suf_j-max(\frac{pre_i}{p_i},\frac{suf_j}{1-p_j})$
注意$max$中的两个值，前者随着$i$增大在增大，后者随着$j$减小在增大
若固定$i$，一定存在$p$，使得$j\leq p$时有$\frac{pre_i}{p_i}\leq\frac{suf_j}{1-p_j}$，且$res=pre_i+suf_j-\frac{suf_j}{1-p_j}$此时随$j$增大而增大
同时$j\geq p+1$时有$\frac{pre_i}{p_i}\gt\frac{suf_j}{1-p_j}$，且$res=pre_i+suf_j-\frac{pre_i}{p_i}$此时随$j$增大而减小
因此固定$i$时，最大的$res$出现在$j=p$或$j=p+1$处
因为随着$i$的增大，$p$的值会不断减小，所以可以双指针维护$p$
还有另外两个点
一个点是，对于$p_i$相同的人，可以去重当作一个人
另一个点是，前缀与后缀不应有重叠部分，否则重叠的赌怪两边都押，他赌赢钱的期望是正的，也就是要求$\frac{1}{x}+\frac{1}{y}\leq 1$，虽然这个不等式和代码没关系，但是不应重叠和代码有关系($break$处)

具体代码

#include <bits/stdc++.h>
using ll = long long;
using PLL = std::pair<ll, ll>;
const int N = 1e6 + 10;
const double eps = 1e-10;
int n;
std::pair<double, ll> g[N];
ll pre[N], suf[N];
void solve()
{
    std::cin >> n;
    for (int i = 1; i <= n; ++i)
        std::cin >> g[i].first >> g[i].second;
    std::sort(g + 1, g + n + 1, std::greater<std::pair<double, ll>>());
    int m = 0;
    for (int i = 1; i <= n; ++i)
        if (i == 1 || fabs(g[i].first - g[i - 1].first) > eps)
            ++m, g[m] = g[i];
        else
            g[m].second += g[i].second;
    for (int i = 1; i <= m; ++i)
        pre[i] = pre[i - 1] + g[i].second;
    for (int i = m; i >= 1; --i)
        suf[i] = suf[i + 1] + g[i].second;
    double ans = 0.0;
    for (int i = 1, p = m; i <= m; ++i)
    {
        while (p > i && pre[i] / g[i].first > suf[p] / (1 - g[p].first))
            --p;
        ans = std::max(ans, pre[i] + suf[p + 1] - pre[i] / g[i].first);
        if (i >= p)
            break;
        ans = std::max(ans, pre[i] + suf[p] - suf[p] / (1 - g[p].first));
    }
    std::cout << std::fixed << std::setprecision(10) << ans << '\n';
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T = 1;
    // std::cin >> T;
    while (T--)
        solve();
    return 0;
}

E. Hammer to Fall

题目大意

$n$个点$m$条边的无向有权图，每个点上有$a_i$个居民
这个图上会下$q$天锤子雨，第$i$天下锤子雨的地点是$b_i$
作为国王，每天前都可以将若干人从一个城市转移到相邻的城市，代价是转移人数和边权的乘积
问在无人受伤的情况下的最小代价

解题思路

对于单个居民，他对最后答案的贡献只与初始所在点有关
令$dp_k(u)$表示一个居民在第$k$天处于点$u$时对答案的贡献
倒着对$k=q,q-1,\cdots,1$更新$dp$值
每次只有下锤子雨的地点$u$的$dp$值需要更新
容易写出如下朴素代码

void solve()
{
    std::cin >> n >> m >> q;
    for (int i = 1; i <= n; ++i)
        std::cin >> a[i];
    for (int i = 1; i <= m; ++i)
    {
        int u, v, w;
        std::cin >> u >> v >> w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    for (int i = 1; i <= q; ++i)
        std::cin >> b[i];
    for (int i = q; i >= 1; --i)
    {
        int u = b[i];
        dp[u] = INF;
        for (auto [v, w] : e[u])
            dp[u] = std::min(dp[u], dp[v] + w);
    }
    ll ans = 0;
    for (int i = 1; i <= n; ++i)
        ans = (ans + a[i] * dp[i]) % MOD;
    std::cout << ans << '\n';
}

上述时间复杂度瓶颈在于，如果每天下锤子雨的地方都是同一个度数很大的点，那么每次都要遍历很多边来更新这个点的$dp$值，最坏复杂度为$O(qm)$
考虑根号分治，令$deg_u$为$u$点的度数，$B$为根号分治的阈值
若$deg_x\leq B$，还是暴力更新即可
若$deg_x\leq B$，注意到这样的点不会超过$\frac{2m}{B}$个(所有点度数之和为$2m$)，也就是不会超过根号级别个
对于每一个这样的点，可以用一个$multiset$维护其相邻点的$dp_v+w$
在每一个小度数点$dp_v$更新后，找到$v$相邻的所有大度数点，把他们的$multiset$里原本的$dp_v+w$删除，换成新的值
而更新大度数点时，只需要直接取出这个点的$multiset$中最小的值，注意大度数点也可能连着若干个个大度数点，所以更新完大度数点的$dp$值后，也需要找到其相邻的所有大度数点，把他们的$multiset$里的旧值换成新值

具体代码

#include <bits/stdc++.h>
using ll = long long;
using PLL = std::pair<ll, ll>;
const int N = 1e5 + 10;
const int B = 600;
const ll MOD = 998244353;
const ll INF = LLONG_MAX;
int n, m, q;
ll a[N], b[N];
ll dp[N];
int deg[N];
std::multiset<PLL> ms[N];
std::vector<PLL> e[N];
std::vector<PLL> big[N];
void solve()
{
    std::cin >> n >> m >> q;
    for (int i = 1; i <= n; ++i)
        std::cin >> a[i];
    for (int i = 1; i <= m; ++i)
    {
        ll u, v, w;
        std::cin >> u >> v >> w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
        ++deg[u], ++deg[v];
    }
    for (int i = 1; i <= q; ++i)
        std::cin >> b[i];
    for (int u = 1; u <= n; ++u)
        for (auto [v, w] : e[u])
        {
            if (deg[v] > B)
            {
                big[u].push_back({v, w});
                ms[v].insert({w, u});
            }
        }
    for (int i = q; i >= 1; --i)
    {
        int u = b[i];
        ll backup = dp[u];
        if (deg[u] <= B)
        {
            dp[u] = INF;
            for (auto [v, w] : e[u])
                dp[u] = std::min(dp[u], dp[v] + w);
        }
        else
            dp[u] = (*ms[u].begin()).first;

        for (auto [v, w] : big[u])
        {
            if (deg[v] > B)
            {
                ms[v].erase({backup + w, u});
                ms[v].insert({dp[u] + w, u});
            }
        }
    }
    ll ans = 0;
    for (int i = 1; i <= n; ++i)
        ans = (ans + a[i] * dp[i]) % MOD;
    std::cout << ans << '\n';
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T = 1;
    // std::cin >> T;
    while (T--)
        solve();
    return 0;
}

G. Let Them Eat Cake

题目大意

$Bobo$给站成一排的$n$个人发蛋糕，第$i$个人有标签$a_i$，每个标签都两两不同，且值都在$1\sim n$间，现在按下列规则发蛋糕，问发蛋糕的轮数
规则$1$：只剩一个人时，给这个人蛋糕，到此结束(这不记作一轮)
规则$2$：找到每一个标签值比左边或右边的人小的人，让他们拿到蛋糕，然后同时退出队伍，然后队伍自动紧缩。这记作一轮

解题思路

因为标记值两两不同，所以每一轮队伍里都会少掉一半的人，所以最多进行$log$轮，所以每一轮内部直接$O(n)$模拟

具体代码

#include <bits/stdc++.h>
using ll = long long;
using PLL = std::pair<ll, ll>;
const int N = 2e5 + 10;
int n;
void solve()
{
    std::cin >> n;
    std::vector<int> a;
    for (int i = 1; i <= n; ++i)
    {
        int x;
        std::cin >> x;
        a.push_back(x);
    }
    int round = 0;
    while (true)
    {
        if (a.size() <= 1)
            break;
        ++round;
        std::vector<int> b;
        for (int i = 0; i < a.size(); ++i)
        {
            bool get_cake = false;
            if (i - 1 >= 0 && a[i] < a[i - 1])
                get_cake = true;
            if (i + 1 < a.size() && a[i] < a[i + 1])
                get_cake = true;
            if (!get_cake)
                b.push_back(a[i]);
        }
        std::cout << '\n';
        a.swap(b);
    }
    std::cout << round << '\n';
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T = 1;
    // std::cin >> T;
    while (T--)
        solve();
    return 0;
}

H. Life is Hard and Undecidable, but

题目大意

给定$k$，构造一个$Life\ Game$的初始状态(视作第$0$代)，使得恰好在第$k$代没有存活的细胞
$Life\ Game$规则：
$1.$如果一个离世状态的点周围八格范围内恰好有$3$个存活的点，那么这个点在下一秒就会变成一个存活的点
$2.$如果一个存活状态的点周围八格内恰好有$2$或$3$个存活的点，那么这个点在下一秒仍然是存活的点，否则会变成离世的点

解题思路

对角线，每一代只有对角线两个端点死掉

具体代码

#include <bits/stdc++.h>
using ll = long long;
using PLL = std::pair<ll, ll>;
const int N = 2e5 + 10;
int k;
void solve()
{
    std::cin >> k;
    std::cout << 2 * k - 1 << '\n';
    int posx = 300, posy = 300;
    for (int i = 1; i <= 2 * k - 1; ++i)
    {
        std::cout << posx << ' ' << posy << '\n';
        --posx, --posy;
    }
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T = 1;
    // std::cin >> T;
    while (T--)
        solve();
    return 0;
}

J. Middle Race

题目大意

给定三个正整数$A,B,C$
$BoBo,oBoB$和你三者进行$n$轮游戏，每轮游戏我先选择$A,B,C$中的一个数，然后$BoBo,oBoB$各自从剩下的数里选一个数
设$n$轮游戏结束后你，$BoBo,oBoB$选择的数的总和依次为$X,Y,Z$，求出一种方案使得$\min(Y,Z)\leq X\leq \max(Y,Z)$或者判断不存在

解题思路

设$S=n(A+B+C)$，结论是只要找到让$X$最接近$\frac{S}{3}$的方案即可，此时一定有$\min(Y,Z)\leq X\leq \min(Y,Z)$
结论的证明：
$(1)Y\leq Z\leq X$
因为$X$在三者中最大，肯定有$X\geq \frac{S}{3}$，所以只需证明$|S-3X|$和$|S-3Z|$的大小关系
那么$|S-3X|=|X+Y+Z-3X|=|Y+Z-2X|=2X-Y-Z$
$|S-3Z|=|X+Y+Z-3Z|=|X+Y-2Z|$
$|S-3X|-|S-3Z|=\max(2X-Y-Z-(X+Y-2Z),2X-Y-Z+(X+Y-2Z))=\max(X+Z-2Y,3X-3Z)\gt 0$
就是说在$Y\leq Z\lt X$的情况下，$Z$是最接近$\frac{S}{3}$的
$(2)X\leq Y\leq Z$
和$(1)$同理，对称地写式子，能推出$Y$是最接近$\frac{S}{3}$的
$(3)Y\leq X\leq Z$和$(4)Z\leq X\leq Y$
同理，推出$X$是最接近$\frac{S}{3}$的
证毕
有了结论只需考虑如何找到该方案
不妨令$A\gt B\gt C$，假设$X$由$a$个$A$，$b$个$B$，$c$个$C$组成，那么有$X=aA+bB+cC=aA+bB+(n-a-b)C=a(A-C)+b(B-C)+nC$，在数据允许的$O(nlogn)$的时间复杂度内，可以通过枚举来固定$a$的数量，然后二分$b$的个数找到使得$3X-S$的正负性改变的位置，从而找到最佳方案

具体代码

#include <bits/stdc++.h>
using ll = long long;
const ll MOD = 998244353;
ll n, A, B, C;
ll calc(ll a, ll b)
{
    return a * (A - C) + b * (B - C) + n * C;
}
void solve()
{
    std::cin >> n >> A >> B >> C;
    if (A < B)
        std::swap(A, B);
    if (A < C)
        std::swap(A, C);
    if (B < C)
        std::swap(B, C);
    ll s = n * (A + B + C);
    ll min_gap = LLONG_MAX, cnta = -1, cntb = -1;
    for (int i = 0; i <= n; ++i)
    {
        int l = 0, r = n - i;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (calc(i, mid) * 3 >= s)
                r = mid;
            else
                l = mid + 1;
        }
        if (l >= 1 && abs(calc(i, l) * 3 - s) > abs(calc(i, l - 1) * 3 - s))
            --l;
        ll t = abs(calc(i, l) * 3 - s);
        if (t < min_gap)
            min_gap = t, cnta = i, cntb = l;
    }
    for (int i = 1; i <= n; ++i)
    {
        if (i <= cnta)
            std::cout << A << std::endl;
        else if (i <= cnta + cntb)
            std::cout << B << std::endl;
        else
            std::cout << C << std::endl;
        int x, y;
        std::cin >> x >> y;
    }
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T;
    std::cin >> T;
    while (T--)
        solve();
    return 0;
}

M. Rock-Paper-Scissors Pyramid

题目大意

有一个长度为$n$的石头剪刀布序列，每个元素是$RPS$(石头、布、剪刀)中的一个，我们需要用这个序列构造一个三角，三角的底层为这个序列，第
$i$层的第$j$个元素为下一层第$j$和第$j+1$个元素中不会失败的那一方
求三角的顶端是什么

解题思路

考虑已经有了前$n-1$位的序列生成的三角形，如何推出$n$位序列生成的三角$Q$
显然第$n$位的元素应该自底向上和$P$的每一层的最后一个元素一一比较，如果能战胜，就在上一层的末尾放上自己，直到遇到一个不能战胜的元素，再向上的每层最后一个元素和下一层之前的最后一个元素相同
这个过程里只有每层的最后一个元素有用，所以只维护每层最后一个元素即可
维护的序列$S$中连续相同位的比较结果一定相同，所以可以把连续的相同位视作一位
这样，由$P$得到$Q$的过程，等价于在$S$末尾删除所有可以被新元素战胜的元素，然后把新元素压入$S$末尾
这是一个栈结构，最后输出栈底即可

具体代码

#include <bits/stdc++.h>
using ll = long long;
using PII = std::pair<int, int>;
const int N = 2e5 + 10;
const int M = 3;
const ll INF = 0x7f7f7f7f7f7f7f7f;
bool win(char s, char t)
{
    if (s == 'R' && t == 'S')
        return true;
    if (s == 'S' && t == 'P')
        return true;
    if (s == 'P' && t == 'R')
        return true;
    return false;
}
void solve()
{
    std::string str;
    std::cin >> str;
    std::stack<int> sta;
    int n = str.size();
    for (int i = 0; i < n; ++i)
    {
        while (!sta.empty() && !win(str[sta.top()], str[i]))
            sta.pop();
        sta.push(i);
    }
    int ans = 0;
    while (!sta.empty())
        ans = sta.top(), sta.pop();
    std::cout << str[ans] << '\n';
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T = 1;
    std::cin >> T;
    while (T--)
        solve();
    return 0;
}