首页 > 其他分享 >2022 China Collegiate Programming Contest (CCPC) Mianyang | 2022 CCPC 绵阳（MAEDJLB）

2022 China Collegiate Programming Contest (CCPC) Mianyang | 2022 CCPC 绵阳（MAEDJLB）

时间：2024-04-24 11:44:05浏览次数：26  
标签：MAEDJLB return int CCPC long blo 2022 using frac

搬运自本人知乎文章。

https://zhuanlan.zhihu.com/p/588646549

M. Rock-Paper-Scissors Pyramid

题目链接

Problem - M - Codeforces

题意

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

求三角的顶端是什么。

Solution

考虑我们已经有了前 \(n-1\) 位的序列生成的三角 \(P\)，我们从中推出 \(n\) 位应该得到的三角 \(P'\)。

很显然，第 \(n\) 位的元素应该会自底向上和 \(P\) 的每一层的最后一个元素一一比较，如果能战胜，那么就在上一层的末尾放上自己，直到遇到第一个不能战胜的元素就结束，再向上的每层最后一个元素和下一层之前的最后一个元素相同。

显然这个过程中，只有每层最后一个元素有用，所以我们只维护每层最后一个元素，假设我们维护的这个序列为 \(S\)。同时，因为 \(S\) 中连续相同位比较结果一定相同，我们可以把这些位看成一位。这样，由 \(P\) 得到 \(P'\) 的过程，等价于在 \(S\) 末尾删除所有可以被新元素战胜的元素，然后将新元素加入 \(S\) 末尾。

这个过程中 \(S\) 可以用栈来表示，最后只需要输出栈底即可。

Code

#include<bits/stdc++.h>
using namespace std;

constexpr int N = 1e6 + 7;

bool beat(char s, char t) {
    if (s == 'R' && t == 'S') return 1;
    if (s == 'S' && t == 'P') return 1;
    if (s == 'P' && t == 'R') return 1;
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        string s;
        cin >> s;
        stack<int> sk;
        int n = s.size();
        for (int i = 0; i < n; ++i) {
            while (!sk.empty() && !beat(s[sk.top()], s[i])) sk.pop();
            sk.push(i);
        }
        int ans = 0;
        while (!sk.empty()) ans = sk.top(), sk.pop();
        cout << s[ans] << '\n';
    }

    return 0;
}

A. Ban or Pick, What's the Trick

题目链接

Problem - A - Codeforces

题意

两个队伍分别可以选择 \(n\) 个英雄，每个队伍可选的英雄的分值分别是 \(\{a_n\}\) 和 \(\{b_n\}\)。双方轮流进行选择自己的英雄，或者禁用对方英雄池中的英雄。

最后双方各自最多选择自己挑选的英雄中的 \(k\) 个出战，各自的总得分为各自选择的最多 \(k\) 个影响的得分之和。双方都想最大化「己方得分 - 对方得分」，求出在双方各自最优策略下的最大分差。

Solution

显然，如果一个队伍挑选自己的英雄，他一定会选择自己池子中可选的分数最大英雄。同样，如果要禁用对方的英雄，那么他也一定会优先禁用对方池子中分数最大的英雄。

容易发现，如果一个队伍自己选满了 \(k\) 个英雄，那么接下来如果再选英雄不会增加自己的得分，因此此后的操作一定会是禁用对方的英雄。

因此，双方各自选择的英雄不会超过 \(k\) 个。

所以可以 DP。令 \(dp[i][c1][c2]\) 表示第 \(i\) 次操作前，第一队选择了 \(c1\) 个英雄，第二队选择了 \(c2\) 个英雄时，在接下来的过程中，能最大化的分差。

可以推出，在第 \(i\) 次操作前，第一队进行了 \(r1 = \lfloor \frac i2\rfloor\) 次操作，第二队进行了 \(r2 = \lfloor \frac {i-1}2\rfloor\)。因此双方各自被禁用了 \(ban1 = r2 - c2\) 和 \(ban2 = r1 - c1\) 个英雄，因此本次操作如果要选择英雄，应该选择第 \(p1 = c1 + ban1 + 1\) 和 \(p2 = c2 + ban2 + 1\) 大的英雄。

有了这些信息以后，直接枚举本次是自己选择英雄还是禁用对方的英雄转移即可。

注意对于第一队，如果 \(c1 >= k\) 或者 \(p1 > n\) 都意味着不能再选择自己的英雄了，而如果 \(p2 > n\) 就不能禁用对方的英雄了。对于第二队同理。

可以使用记忆化搜索实现会更方便，时间复杂度 \(O(nk^2)\)。

Code

#include <bits/stdc++.h>
using namespace std;

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second

using ll = long long; using ull = unsigned long long; using pii = pair<int, int>;

template <typename A, typename B> bool smax(A &a, const B &b) { return a < b ? a = b, 1 : 0; }
template <typename A, typename B> bool smin(A &a, const B &b) { return b < a ? a = b, 1 : 0; }

constexpr int N = 2e5 + 7;
constexpr int M = 13;
constexpr ll INF = LLONG_MAX / 2;

int n, k;
int a[N], b[N];
ll dp[N][M][M];
bool vis[N][M][M];

ll dfs(int x, int c1, int c2) {
    if (x == n * 2 + 1) return 0;
    if (vis[x][c1][c2]) return dp[x][c1][c2];
    vis[x][c1][c2] = 1;
    ll &ans = dp[x][c1][c2];
    int r1 = x / 2, r2 = (x - 1) / 2;
    int ban1 = r2 - c2, ban2 = r1 - c1;
    int p1 = c1 + ban1 + 1, p2 = c2 + ban2 + 1;
    if (x & 1) ans = max(p2 <= n ? -dfs(x + 1, c1, c2) : -INF, p1 <= n && c1 < k ? a[p1] - dfs(x + 1, c1 + 1, c2) : -INF);
    else ans = max(p1 <= n ? -dfs(x + 1, c1, c2) : -INF, p2 <= n && c2 < k ? b[p2] - dfs(x + 1, c1, c2 + 1) : -INF);
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i];
    sort(a + 1, a + n + 1, greater<int>());
    sort(b + 1, b + n + 1, greater<int>());

    cout << dfs(1, 0, 0) << endl;
    
    return 0;
}

E. Hammer to Fall

题目链接

Problem - E - Codeforces

题意

有一个 \(n\) 个点 \(m\) 条边的无向图，每个点上有 \(a_i\) 个人。

在 \(q\) 天内，每天都会有一个点 \(b_i\) 发生爆炸，而我们每天前都可以将若干人从一个城市转移到相邻的城市，代价是转移人数和边权的乘积。

我们需要最小化在不发生人员伤亡（保证爆炸时点上没有人）的情况下的最小代价和。

Solution

被转移的始终是人，而不同的人之间其实不会相互影响，所以我们可以计算单个人的代价。

只有每一天每个人在什么位置会对结果有影响，所以我们可以设 \(dp_{i, x}\) 表示一个人第 \(i\) 天在 \(x\) 点时，在以后的时间中，保护这个人不受伤的最小代价。显然有

\[dp_{i, x} = \begin{cases} dp_{i+1, x}&, x \neq b_i\\ \min\limits_{(x, y, w) \in G} dp_{i+1, y} + w&, x = b_i \end{cases}\\ \]

可以发现，如果在空间上省略第一维的天数，那么每天只会有一个点的答案发生改变，其余答案都可以直接继承。

我们考虑直接算出第 \(i\) 天 \(b_i\) 点的答案。这个答案需要从和这个点相邻的点中求得。但是暴力枚举所有的邻边最坏情况下是 \(O(qn)\) 的。

对于这一类问题，有一种常用的方法是根号分治。令 \(deg_x\) 为 \(x\) 点的度数，假设 \(blo\) 是我们分治的临界标准。

如果 \(deg_x \leq blo\)，那么我们暴力枚举和 \(x\) 相邻的点即可直接计算出新的 \(dp_{b_i}\)。

如果 \(deg_x > blo\)，那么这样的点显然不会超过 \(\frac{2m}{blo}\) 个（所有点度数之和为 \(2m\)）。对于每一个这样的 \(x\)，我们都可以用一个 multiset 维护其相邻点的 \(dp_{y} + w\)。在每一次更新了 \(dp_{y}\) 时，就枚举所有的 \(x\)，如果 \(x, y\) 相邻，从 \(x\) 的 multiset 中把之前的 \(dp_y + w\) 删除，加入新的值即可。在第 \(i\) 天的时候，取出 \(b_i\) 的 multiset 中最小的值就是新的 \(dp_{b_i}\)。

时间复杂度 \(O(q(blo + \frac{2m}{blo}\log n))\)，当 \(blo = \sqrt{2m\log n}\) 时，最优复杂度为 \(O(q\sqrt{2m\log n})\)。

上面就是我们队在 vp 的时候现场的写法。但是这种写法并不是最优的。

如果在根号分治的同时带上时间分块的思想，可以避免 multiset 的使用。

时间分块的思想就是，我们如果每隔 \(blo\) 天更新一次总体的信息，在此期间，我们特殊处理 \(blo\) 天内的新信息，这样的新信息的规模不会超过 \(O(blo)\) 个。

在此题中，我们在最近的 \(blo\) 天内，最多会发生 \(blo\) 个点的信息改变，而每个点的 \(dp\) 值只有可能变大不会变小，因此 \(blo\) 天内，每个 \(deg_x > blo\) 的点的更新来源只可能是相邻的 \(y\) 中在上一次整 \(blo\) 倍天时 \(dp_y + w\) 最小的 \(blo + 1\) 个。

所以我们新的算法就是：

每到整 \(blo\) 倍天，暴力求出每一个点 \(x\) 的 \(dp_y + w\) 最小的 \(blo + 1\) 个邻居。可以使用 nth_element \(O(deg_x)\) 地计算，这一步的总复杂度为 \(\frac{q}{blo}m\)。

如果 \(deg_x\leq blo\)，方法不变，仍然是暴力枚举和 \(x\) 相邻的点计算 \(dp_{b_i}\)。

如果 \(deg_x > blo\)，那么暴力枚举之前维护好的 \(x\) 个 \(blo+1\) 个邻居，由它们更新 \(dp_{b_i}\)。

时间复杂度 \(O(q\cdot blo + \frac{qm}{blo})\)，当 \(blo = \sqrt m\) 时有最小值 \(O(q\sqrt m)\)。

Code

#include <bits/stdc++.h>
using namespace std;

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second

using ll = long long; using ull = unsigned long long; using pii = pair<int, int>;

template <typename A, typename B> bool smax(A &a, const B &b) { return a < b ? a = b, 1 : 0; }
template <typename A, typename B> bool smin(A &a, const B &b) { return b < a ? a = b, 1 : 0; }

constexpr int N = 1e5 + 7;
constexpr int M = 460 + 7;
constexpr ll INF = LLONG_MAX;
constexpr int P = 998244353;

int n, m, q, blo;
int deg[N], a[N], b[N];
ll dp[N];
bool mk[N];
vector<pii> g[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    
    cin >> n >> m >> q;
    blo = sqrt(m);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1, x, y, z; i <= m; ++i) cin >> x >> y >> z, g[x].emplace_back(y, z), g[y].emplace_back(x, z), ++deg[x], ++deg[y];
    for (int i = q; i; --i) cin >> b[i];

    for (int i = 1; i <= n; ++i) if (deg[i] > blo)
        nth_element(g[i].begin(), g[i].begin() + blo, g[i].end(),
            [](const pii &x, const pii &y) { return dp[x.fi] + x.se < dp[y.fi] + y.se; });
    for (int i = 1; i <= q; ++i) {
        int x = b[i];
        dp[x] = INF;
        for (int i = 0; i < min(blo, deg[x]); ++i) smin(dp[x], dp[g[x][i].fi] + g[x][i].se);
        if (i % blo == 0) {
            for (int i = 1; i <= n; ++i) if (deg[i] > blo)
                nth_element(g[i].begin(), g[i].begin() + blo, g[i].end(),
                    [](const pii &x, const pii &y) { return dp[x.fi] + x.se < dp[y.fi] + y.se; });
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i) ans = (ans + a[i] * dp[i]) % P;
    cout << ans << endl;
    
    return 0;
}

D. Gambler's Ruin

题目链接

Problem - D - Codeforces

题意

两个队伍打比赛，有 \(n\) 个下注者，每个下注者对双方（BU 和 BC）胜率估计有一个预测 \(p_i : 1-p_i\)。

我们作为庄家要为两队开设赔率，BU 赢陪 \(x\)，BC 赢陪 \(y\)，如果一个下注者 \(i\) 发现在他的胜率预测下，赌 BU 赢会期望赚钱（即 \(p_ix \geq 1\)），他就会给 BU 下注 \(c_i\) 。否则，如果堵 BC 赢会期望赚钱，那么他就会给 \(BC\) 下注 \(c_i\)。

我们需要最大化“最坏情况下”（两队中某队获胜）的收益，即若 \(s_x, s_y\) 分别为 BU 和 BC 被下注总额，最大化 \(s_x + s_y - \max\{s_xx, s_yy\}\)。

Solution

即然只要 \(p_ix\geq 1\)，\(i\) 就会给 \(BU\) 下注，那么当 \(x\) 确定，所有 \(p_i \geq \frac 1x\) 的人就都会给 BU 下注。因此如果将所有下注者按照 \(p_i\) 从大到小排序，那么下注 BU 的人一定是一个前缀。

同理，下注 BC 的人一定是一个后缀。

我们令 \(pres_i\) 为排序后 \(c_i\) 的前缀和，\(sufs_i\) 为 \(c_i\) 的后缀和。

那么我们枚举 \(i\) 表示下注 BU 的前缀中最后一个人的指针，\(j\) 为下注 BC 后缀中最前一个人的指针。那么最优情况下有 \(x = \frac 1{p_i}, y = \frac 1{1 - p_j}\)。

那么，收益 \(pf\) 可以被写为

\[pres_i + sufs_j - \max\{ \frac{pres_i}{p_i}, \frac{sufs_j}{1 - p_j} \}\\ \]

我们注意观察 \(\max\) 中两个值，随着 \(i\) 增大，\(pres_i\) 在增大，\(p_i\) 在减小，因此 \(\frac{pres_i}{p_i}\) 一定会增大。

同时，随着 \(j\) 增大，\(sufs_j\) 在减小，\(1 - p_j\) 在增大，因此 \(\frac{sufs_j}{1 - p_j}\) 一定在减小。

因此，如果我们固定 \(i\)，一定会存在一个点 \(p\)，使得 \(j \leq p\) 时 \(\frac{pres_i}{p_i} \leq \frac{sufs_j}{1 - p_j}\)，则在这一段内 \(pf = pres_i - sufs_j \frac{p_j}{1 - p_j}\) 一定也在随 \(j\) 增大而增大。

同时 \(j > p\) 时 \(\frac{pres_i}{p_i} > \frac{sufs_j}{1 - p_j}\)，则这一段内 \(pf = pres_i + sufs_j - \frac{pres_i}{p_i}\) 在随着 \(j\) 的增大而减小。

也就是说，如果固定 \(i\)，那么最大的收益一定出现在 \(j = p\) 或者 \(j = p+1\) 上。

且，随着 \(i\) 的增大，\(p\) 的值应该会不断地减小，所以我们用双指针来维护 \(p\) 的位置。

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

这个题有一个需要注意的点是，根据题意的要求，拥有相同的 \(p_i\) 的人，一定会下注同一个队伍，因此我们可以把 \(p_i\) 相同的人合并为一个人。

Code

#include <bits/stdc++.h>
using namespace std;

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second

using ll = long long; using ull = unsigned long long; using pii = pair<int, int>;

template <typename A, typename B> bool smax(A &a, const B &b) { return a < b ? a = b, 1 : 0; }
template <typename A, typename B> bool smin(A &a, const B &b) { return b < a ? a = b, 1 : 0; }

constexpr int N = 1e6 + 7;
constexpr double eps = 1e-10;

int n;
pair<double, ll> a[N];
ll pres[N], sufs[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i].fi >> a[i].se;

    sort(a + 1, a + n + 1, greater<pair<double, int>>());
    int cnt = 0;
    for (int i = 1; i <= n; ++i)
        if (i == 1 || fabs(a[i].fi - a[i - 1].fi) > eps) a[++cnt] = a[i];
        else a[cnt].se += a[i].se;
    n = cnt;
    for (int i = 1; i <= n; ++i) pres[i] = pres[i - 1] + a[i].se;
    for (int i = n; i; --i) sufs[i] = sufs[i + 1] + a[i].se;
    
    double ans = 0;
    for (int i = 1, p = n; i <= n; ++i) if (i == n || fabs(a[i].fi - a[i + 1].fi) > eps) {
        while (p > i && pres[i] / a[i].fi > sufs[p] / (1 - a[p].fi)) --p;
        smax(ans, pres[i] + sufs[p + 1] - pres[i] / a[i].fi);
        if (i >= p) break;
        smax(ans, pres[i] + sufs[p] - sufs[p] / (1 - a[p].fi));
    }
    
    cout << fixed << setprecision(10) << ans << '\n';
    
    return 0;
}

J. Middle Race

题目链接

Problem - J - Codeforces

题意

给定三个正整数 \(A, B, C\)。

我、BoBo 和 oBoB 进行 \(n\) 轮游戏，每轮游戏中我先选择 \(A, B, C\) 中的一个数，然后 BoBo 和 oBoB 各自从剩下的数中选一个数。

设最后我、BoBo 和 oBoB 三个人 \(n\) 轮选择的总和为 \(X, Y, Z\)，求出一种方案使得 \(\min\{Y, Z\} \leq X \leq \max\{Y, Z\}\) 或者判断不存在。

Solution

感觉题面好绕，读了好几遍才读懂……

我到现在都不知道这个题为什么要出成交互，分明只要传统题的思路就能做了。

这个题让我卡了好久……试了好几种猜想，所幸最后还是想到了正确的思路。

因为需要让 \(\min\{Y, Z\} \leq X \leq \max\{Y, Z\}\)，可以想到，我们应该让 \(X\) 尽可能地接近 \(\frac S3\)，其中 \(S = n(A + B + C) = X + Y + Z\)。

（因为这个题我试了两三种猜想都不对以后精神错乱，竟然写了一份直接让每一次的选择在向 \(\frac {i(A + B + C)}3\) 靠近的 sb 逼近方法去交了一发……）

很容易证明，只要我们能求出这个 \(X\) 最接近 \(\frac S3\) 的方案，那么一定有 \(\min\{Y, Z\} \leq X \leq \max\{Y, Z\}\)：

假设 \(Y \leq Z < X\)，那么

\[|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| =\)

\[\begin{align*} &\max\{ 2X - Y - Z - (X + Y - 2Z), 2X -Y - Z + (X + Y - 2Z) \}\\ = &\max\{ 2X - Y - Z - X - Y + 2Z), 2X -Y - Z + X + Y - 2Z \}\\ = &\max\{ X + Z - 2Y, 3X - 3Z\} > 0 \end{align*} \]

即，\(|S - 3X| > |S - 3Z|\)，则 \(X\) 不是最接近 \(\frac S3\) 的，与假设矛盾。

\(X < Y \leq Z\) 的假设和上面同理。

故只要 \(X\) 最接近 \(\frac S3\)，就一定符合题意，故不存在无解。

下面考虑如何求出 \(X\) 的构造方案。

不妨设 \(A > B > C\)，假设 \(X\) 由 \(a\) 个 \(A\)，\(b\) 个 \(B\) 和 \(c\) 个 \(C\) 构成，即 \(a + b + c = n\)

\[X = aA + bB + cC = aA + bB + (n - a - b)C = a(A - C) + b(B - C) + nC$$。我们可以枚举 $a$ 的数量，然后通过二分 $b$ 可以找到令 $3X - S$ 的正负性改变的位置，进而求出最少 $|3X - S|$ 的最小值和构造方案。 单组数据时间复杂度 $O(n\log n)$。 ### Code ```cpp #include<bits/stdc++.h> using namespace std; #define fi first #define se second using ll = long long; using ull = unsigned long long; int n, m; int main() { ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); int T; cin >> T; while (T--) { ll n, A, B, C; cin >> n >> A >> B >> C; if (A < B) swap(A, B); if (A < C) swap(A, C); if (B < C) swap(B, C); ll s = (A + B + C) * n; auto calc = [&](ll x1, ll x2) { return n * C + x1 * (A - C) + x2 * (B - C); }; ll sta = LLONG_MAX, x1 = -1, x2 = -1; for (int i = 0; i <= n; ++i) { int l = 0, r = n - i; while (l < r) { int mid = (l + r) / 2; if (calc(i, mid) * 3 < s) l = mid + 1; else r = mid; } if (!(l == 0 || abs(calc(i, l) * 3 - s) <= abs(calc(i, l - 1) * 3 - s))) --l; ll p = abs(calc(i, l) * 3 - s); if (p < sta) x1 = i, x2 = l, sta = p; } for (int i = 1; i <= n; ++i) { if (i <= x1) cout << A << endl; else if (i <= x1 + x2) cout << B << endl; else cout << C << endl; int x, y; cin >> x >> y; } } return 0; } ``` ## L. Por Una Cabeza ### 题目链接 [Problem - L - Codeforces](https://codeforces.com/gym/104065/problem/L) ### 题意 有 $n$ 个人，每个人会做出 $0/1$ 的投票。有 $m$ 台机器会处理投票结果，其接收奇数个输入，输入可以是人也可以是编号比它小的机器的输出，只要接受的输入中 $0$ 或 $1$ 的个数超过了应接收的输入的一半，机器就会直接给出输出。保证每个人的投票只会被一台机器直接处理，人按照编号顺序投票，可以认为机器的处理不需要时间。 每个人的投票 $a_i$ 已经给定了，我们可以花费 $b_i$ 使这个人改变他的投票，我们希望花费最少的钱来修改一些人的投票，使得每一个机器都只会在接收完所有输入以后才会输出结果。 有 $q$ 次操作，每次操作会修改一个投票人的 $a_i$ 和 $b_i$。输出修改后的最小花费。 ### Solution 假设一个机器的输入个数为 $l$，若要一个机器在接收完所有输入以后才会输出，那就要满足前 $l-1$ 个输入中，$0$ 和 $1$ 的数量都是 $\frac{l-1}2$。而在这样的条件下，机器的输出只会取决于最后输入的值。 因此，假设最后一个输入为 $p$，那么 $p$ 的值不影响在这个机器上的花费，但是可能会影响到这台机器输出的接收机器的花费，对于接收机器来说，输出机器可以直接看成 $p$ 在投票。 因此，如果我们只看一台机器需要的花费由哪些投票人组成，那么每一个投票人只会对一台机器产生贡献，$n$ 号投票人不对任何机器产生贡献。而机器之间的花费是相互独立的。 考虑如何计算一台机器的花费。假设这台机器关联的投票人有 $2k$ 个，其中有 $x$ 个 $0$ 和 $l - x$ 个 $1$。如果 $x > k$，那么我们需要将 $x - k$ 个投 $0$ 的人收买成 $1$。我们需要求出投 $0$ 的人中，花费最小的 $x - k$ 个的花费之和。对于 $x < k$ 来说也是同理。 因为 $x$ 每次变化量只可能为 $1$，所以可以使用两个对顶堆分别维护投 $0$ 和 $1$ 的人花费中前 $x - k$ 或 $k - x$ 小的部分。因为可能会修改单人花费，所以对顶堆中的每一个堆需要用可删除堆。 时间复杂度 $O(q\log n)$。 ### Code 这段代码由于我写的时候神智不清，写了一些很奇怪的东西。 传统的可删除堆应该是维护两个堆，其中一个堆专门存储被删除的数，但是我没有想起来可以这样搞，用了 `unordered_map` 来存储删除。 另外，对顶堆中其实只需要存储所有的花费，不必存储对应的投票人，所以不需要 `pair`，但是我一时没搞清楚所以多套了个 `pair`。 ```cpp #include <bits/stdc++.h> using namespace std; #define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to) #define dbg(...) fprintf(stderr, __VA_ARGS__) #define fi first #define se second using ll = long long; using ull = unsigned long long; using pii = pair<int, int>; template <typename A, typename B> bool smax(A &a, const B &b) { return a < b ? a = b, 1 : 0; } template <typename A, typename B> bool smin(A &a, const B &b) { return b < a ? a = b, 1 : 0; } constexpr int N = 1e5 + 7; int n, m, q; int a[N], b[N]; int rv[N], fa[N], sz[N], c1[N]; vector<int> g[N]; struct HashFunc { size_t operator () (const pii &p) const { return hash<ull>()(((ll)p.fi << 32) + p.se); } }; template <class _Tp, class _Container = vector<_Tp>, class _Compare = less<typename _Container::value_type>> struct Heap { priority_queue<_Tp, _Container, _Compare> q; unordered_set<_Tp, HashFunc> d; void re() { while (!q.empty() && d.count(q.top())) d.erase(q.top()), q.pop(); } void push(const _Tp &x) { if (d.count(x)) d.erase(x); else q.push(x); re(); } bool empty() { return q.empty(); } _Tp top() { return q.top(); } void pop() { q.pop(); re(); } void del(const _Tp &x) { d.insert(x), re(); } size_t size() { return q.size() - d.size(); } }; struct vHeap { int k; ll sum; Heap<pii> q; Heap<pii, vector<pii>, greater<pii>> nq; void ins(int x, int v) { q.push(pii(v, x)), sum += v; while (q.size() > k && !q.empty()) sum -= q.top().fi, nq.push(q.top()), q.pop(); } void del(int x, int v) { if (!q.empty() && pair(v, x) <= q.top()) { q.del(pii(v, x)), sum -= v; while (q.size() < k && !nq.empty()) sum += nq.top().fi, q.push(nq.top()), nq.pop(); } else nq.del(pii(v, x)); } void modify(int x, int v, int nv) { del(x, v), ins(x, nv); } void modify(int nk) { assert(abs(nk - k) <= 1); k = nk; while (q.size() > k && !q.empty()) sum -= q.top().fi, nq.push(q.top()), q.pop(); while (q.size() < k && !nq.empty()) sum += nq.top().fi, q.push(nq.top()), nq.pop(); } } h[N][2]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); cin >> n >> m >> q; for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i]; for (int i = 1; i <= m; ++i) { int l, mx = 0, &cnt1 = c1[i]; cin >> l; vector<int> t; for (int j = 0, x; j < l; ++j) { cin >> x; if (x < 0) x = rv[-x]; if (x > mx) mx && (t.push_back(mx), cnt1 += a[mx]), mx = x; else t.push_back(x), cnt1 += a[x]; } rv[i] = mx, sz[i] = l - 1; assert(~t.size() & 1); if (cnt1 < t.size() / 2) h[i][0].k = t.size() / 2 - cnt1; else h[i][1].k = cnt1 - t.size() / 2; for (int x : t) h[i][a[x]].ins(x, b[x]), fa[x] = i; } ll ans = 0; for (int i = 1; i <= m; ++i) ans += h[i][0].sum + h[i][1].sum; for (int i = 1; i <= q; ++i) { int x, y, z; cin >> x >> y >> z; int f = fa[x]; if (!f) goto end; ans -= h[f][0].sum + h[f][1].sum; if (y == a[x]) h[f][y].modify(x, b[x], z); else { h[f][a[x]].del(x, b[x]), h[f][y].ins(x, z); c1[f] += y - a[x]; h[f][0].modify(max(sz[f] / 2 - c1[f], 0)), h[f][1].modify(max(c1[f] - sz[f] / 2, 0)); } ans += h[f][0].sum + h[f][1].sum; end: a[x] = y, b[x] = z; cout << ans << '\n'; } return 0; } ``` ## B. Call Me Call Me ### 题目链接 [Problem - B - Codeforces](https://codeforces.com/gym/104065/problem/B) ### 题意 我们要邀请 $n$ 个人来参加会议。第 $i$ 个人会同意参加当且仅当区间 $[l_i , r_i]$ 内已经有 $k_i$ 个人同意参加。问最多能邀请多少个人来参加。 ### Solution 很显然的暴力做法就是类似于拓扑排序那样，先将所有的 $k_i = 0$ 的人入队，对于队列中的人 $x$，将所有的 $x\in[l_i, r_i]$ 的 $i$ 的 $k_i$ 减一，如果 $k_i$ 被减到了 $0$，就将 $i$ 入队。 考虑怎么优化这个过程，尤其是找到当前所有 $k_x = 0$ 的 $x$ 和找到 $x\in[l_i,r_i]$ 的 $i$ 的两个过程。 官方题解的做法非常神仙，我虽然大概能理解其思路，但是代码不是很好写。这里介绍的时间分治算法相比于官方题解，编写难度低了很多。 有一种很容易想出来的优化方法是结合线段树，将每一个人的区间 $[l_i, r_i]$ 挂到线段树上，分成 $O(\log n)$ 个区间，然后这样只需要 $O(\log n)$ 我们就可以找到所有的 $x\in[l_i, r_i]$ 的 $i$ 了。但是这样做只是加快了我们找到区间的时间，并没有可能找到的区间的个数，我们总共可能需要执行的 `--k[i]` 的次数在最坏情况下这依然是 $O(n^2)$ 的。 这是因为每一个区间都会被找到严格的 $k_i$ 次才能入队，我们需要一种方法，能够降低每个区间入队的次数。 可以考虑对时间分治，假设我们每 $blo$ 的时间整理一次数据。可以发现，我们在整 $blo$ 倍的时间后面长度为 $blo$ 的时间块中，最多有 $blo$ 个新处理（这里的处理指的是我们从队列中取出了一个人）的人，所以一个人有可能在接下来的 $blo$ 时间内入队，那么必须要满足当前的 $[l_i, r_i]$ 区间内已经处理过的人数 $+ blo \geq k_i$。我们把一个人在这个时候挂上线段树，他最多在线段树上被访问的次数不超过 $blo$ 次。 在整 $blo$ 倍的时间时，处理新挂上线段树的人的总复杂度 $O(\frac n{blo} n\log n)$。 被挂上线段树的人，最多在线段树上被访问的次数为 $O(n\cdot blo\log n)$。 当 $blo = \sqrt n$ 时复杂度最优，总复杂度为 $O(n\sqrt n\log n)$。 考虑到 $15s$ 的时间限制，勉强可以通过本题。 实际上线段树的 $\log n$ 和 $blo$ 次访问都很难跑满，所以总体上还是很快的。 官方题解里的分治+线段树的标算有空再慢慢写…… ### Code ```cpp #include <bits/stdc++.h> using namespace std; #define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to) #define dbg(...) fprintf(stderr, __VA_ARGS__) #define fi first #define se second using ll = long long; using ull = unsigned long long; using pii = pair<int, int>; template <typename A, typename B> bool smax(A &a, const B &b) { return a < b ? a = b, 1 : 0; } template <typename A, typename B> bool smin(A &a, const B &b) { return b < a ? a = b, 1 : 0; } constexpr int N = 4e5 + 7; constexpr int M = 640; constexpr int LOG = 19; int n, blo; struct Peo { int l, r, k; } a[N]; int s[N], vis[N], intr[N]; queue<int> q; #define lc o << 1 #define rc o << 1 | 1 vector<int> t[N << 2]; void qins(int o, int L, int R, int l, int r, int k) { if (l <= L && R <= r) return t[o].push_back(k); int M = (L + R) / 2; if (l <= M) qins(lc, L, M, l, r, k); if (r > M) qins(rc, M + 1, R, l, r, k); } void del(int o) { vector<int> v; for (int i : t[o]) if (a[i].k) { --a[i].k; if (a[i].k) v.push_back(i); else q.push(i); } swap(t[o], v); } void qdel(int o, int L, int R, int x) { del(o); if (L == R) return; int M = (L + R) / 2; if (x <= M) qdel(lc, L, M, x); else qdel(rc, M + 1, R, x); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); cin >> n; blo = sqrt(n); for (int i = 1; i <= n; ++i) cin >> a[i].l >> a[i].r >> a[i].k; for (int i = 1; i <= n; ++i) if (!a[i].k) q.push(i), intr[i] = 1; int cnt = 0; while (!q.empty()) { int x = q.front(); q.pop(); if (cnt % blo == 0) { for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + vis[i]; for (int i = 1; i <= n; ++i) if (!intr[i] && s[a[i].r] - s[a[i].l - 1] + blo >= a[i].k) { a[i].k -= s[a[i].r] - s[a[i].l - 1]; qins(1, 1, n, a[i].l, a[i].r, i); intr[i] = 1; } } ++cnt; qdel(1, 1, n, x), vis[x] = 1; } cout << cnt << endl; return 0; } ``` \]

标签：MAEDJLB,return,int,CCPC,long,blo,2022,using,frac
From： https://www.cnblogs.com/hankeke303/p/18154718/ccpc2022mianyang

相关文章

  • The 2022 ICPC Asia Xian Regional Contest
    The2022ICPCAsiaXianRegionalContestJ.StrangeSum题意：给定n个数，选定最多不超过两个数字的和的最大值思路：签到voidsolve(){lln;cin>>n;vector<ll>a(n+1);for(inti=1;i<=n;i++)cin>>a[i];llans=0;sort(a.begin()......
  • winform打包成安装包文件 vs2022
    项目目录里生成的exe文件，放到其他人电脑上用不了，网上找了下打包的文章，写下来以备以后再次使用1.直接右键点击项目的发布，发布的是本地安装模式。如果需要在其他电脑上安装，需要安装一个微软官方的扩展包才可以2.点击菜单栏-扩展-管理扩展 2.安装VisualStudioInstallerProjec......
  • 洛谷 P8818 [CSP-S 2022] 策略游戏
    https://www.luogu.com.cn/problem/P8818什么玩意儿。。这种策略题不就是你来我往的，你如果选那个我就选这个，到了最后俩人都做不了决策，一直在博弈吗放个示例跑不过去的代码真不想调，这种题就是恶心啊，你说说怎么调呢针对一方的选择，另一方总能选出更优的策略来。然后这一方针对另......
  • Windows Server 2022 OVF, updated Apr 2024 (sysin) - VMware 虚拟机模板
    WindowsServer2022OVF,updatedApr2024(sysin)-VMware虚拟机模板2024年4月版本更新，现在自动运行sysprep，支持ESXiHostClient部署请访问原文链接：WindowsServer2022OVF,updatedApr2024(sysin)-VMware虚拟机模板，查看最新版。原创作品，转载请保留出处。作......
  • Windows Server 2022 中文版、英文版下载 (updated Apr 2024)
    WindowsServer2022中文版、英文版下载(updatedApr2024)WindowsServer2022正式版，x64请访问原文链接：WindowsServer2022中文版、英文版下载(updatedApr2024)，查看最新版。原创作品，转载请保留出处。作者主页：sysin.org此次发布更新了什么？答：版本号，当然还有…2021.09......
  • P8207 [THUPC2022 初赛] 最小公倍树 题解
    题目大意有编号为\([L,R]\)区间的点，连接两个点\(x,y\)边权的为\(LCM(x,y)\)，求这张图的最小生成树。\[1\leqL\leqR\leq10^6,R-L\leq10^5\]解题思路我们有一个结论：对于张图\(G\)中的一个生成子图\(E\)，\(E\)之中的一条边\(k\)如果不在\(E\)最小生成树中，那么\(......
  • 新手大白话 [HNCTF 2022 Week1]Challenge__rce RCE自增绕过
    今天遇到个RCE难题，挺另类的，这里做个复盘。进入题目直接给出了源码，可以发现就是个无字母RCE，且有长度限制不能使用url取反绕过，到这想到了以前的一个rce自增绕过方式，但是以前的没有长度限制。点击查看代码<?phperror_reporting(0);if(isset($_GET['hint'])){highlight_f......
  • [题解][2021-2022年度国际大学生程序设计竞赛第10届陕西省程序设计竞赛] Cute Rabbit
    题目描述有n只兔子，每个兔子上有一个数ai。要将所有兔子分为白色和绿色两堆，使所有白色兔子的数对绿色兔子取余结果相等。求绿色兔子的最大数量。题解考虑一种情况：把所有除了最小值的数都涂为绿色，此时显然满足条件。对于一般情况：可以枚举白绿兔子的分割线x。对于小于x，试将其全......
  • [题解] [CCPC陕西省赛2022 H题] Cute Rabbit
    [CCPC陕西省赛2022H题]CuteRabbit题目描述有\(n\)只白色的兔子，把其中\(m\)只染成绿色。每只兔子上有一个数\(a_i\)，如果所有白色兔子上的数对所有绿色兔子上的数两两取余的值均相同，则该种染色方式合法，求能够使染色合法的最大的\(m\)。输入格式第一行有一个整数\(n(......
  • 新手大白话 UUCTF 2022 新生赛ezpop 字符串逃逸
    今天做个字符串逃逸的题目，这个题还挺不错的，不多bb直接看源码。点击查看代码<?php//flaginflag.phperror_reporting(0);classUUCTF{public$name,$key,$basedata,$ob;function__construct($str){$this->name=$str;}function__wakeup(){......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99