Codeforces Hello 2024 A~D,F1

A.Wallet Exchange(思维)

题意：

Alice和Bob各自拥有 $a, b$ 枚硬币，他们决定以Alice为先手开始比赛，比赛中每人在每轮需按顺序执行操作1和操作2：

操作1：交换两人手上拥有的硬币数量，或什么都不做
操作2：丢掉手上的一枚硬币（如果此时手上没有硬币则输掉比赛）

问：假设两人都极为聪明，那么谁会赢下这场比赛？

分析：

实际上对于操作1，比赛两方均会选择硬币较多的一堆，因此，可以将硬币视为只有一堆，共 $n$ 枚，其中 $n = a + b$ ，Alice和Bob按顺序从这堆硬币中丢弃硬币。

此时若硬币数量 $n$ 为偶数时，必然是后手丢掉最后一枚硬币，即Bob获胜，反之，先手Alice获胜。

代码：

#include<bits/stdc++.h>

using namespace std;

void solve() {
    int a, b;
    cin >> a >> b;
    if ((a + b) % 2 == 0) {
        cout << "Bob" << endl;
    } else {
        cout << "Alice" << endl;
    }
}

int main() {
    int Case;
    cin >> Case;
    while (Case--) {
        solve();
    }
    return 0;
}

B.Plus-Minus Split(贪心)

题意：

给出一个包含 $n$ 个字符的字符串 $s$ ，字符串中仅包含字符-或+，其中-代表 $- 1$ ，+代表 $1$ 。

你可以进行以下步骤来计算罚分：

将字符串 $s$ 分为若干子子串 $b_1, b_2, ..., b_k$ 。
对于字符串 $c$ 产生的罚分为 $|c_1 + c_2 + ... + c_m| \cdot m$
产生的总罚分为 $p(s) = p(b_1) + p(b_2) + ... + p(b_k)$ 。

问：最小可能的罚分是多少？

分析：

为了最小化罚分，需要尽可能多的将正负号进行匹配，即若干子拆出的子串中正负号出现次数相同，但字符串中正负号数量并不一定相同，那么剩下的正号或负号依然会产生罚分，此时为了最小化罚分，必然选择这些正负号自身为一个子串，假设存在 $a$ 个 $+$ 号， $b$ 个 $-$ 号，那么最小罚分为 $\times min(a, b)$ 。

代码：

#include<bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    string s;
    cin >> n >> s;
    int add = 0, sub = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '-') sub++;
        else add++;
    }
    cout << n - 2 * min(add, sub) << endl;
}

int main() {
    int Case;
    cin >> Case;
    while (Case--) {
        solve();
    }
    return 0;
}

C.Grouping Increases(贪心)

题意：

给出一个包含 $n$ 个数字的数组 $a$ ，你需要按以下要求计算罚分：

将数组 $a$ 分为两个子序列 $s, t$ （可能有个子序列为空）。
对于一个包含 $m$ 个数字的数组 $b$ ，产生的罚分 $\sum\limits_{i = 1}^{m - 1}f(i)$ ，其中 $f (i)$ 为满足 $b_i < b_{i + 1}$ 则为 $1$ ，不满足则为 $0$ 。
总罚分为 $p (s) + p (t)$

问：最小可能的罚分是多少？

分析：

由于对于子序列的罚分计算只考虑相邻的两个数字，那么只需要维护两个子序列最后的元素。

令 $b$ 为两个子序列中最后元素中的较小值， $c$ 为较大值，并按以下要求检查 $a_i$ 该加入哪个子序列：

如果 $a_i \le b$ ，那么 $a_i$ 将会加入最后元素较小的序列，即 $b = a_i$ 。
否则，再检查是否满足 $a_i \le c$ ，如果满足，则将 $a_i$ 加入最后元素较大的序列，即 $c = a_i$ 。
如果以上两种情况均不满足，那么此时必然产生一点罚分，并且为了使之后的罚分尽可能小，当前数字 $a_i$ 必然会加入尾部元素较小的序列，即 $b = a_i$

代码：

#include<bits/stdc++.h>

using namespace std;

int a[200005];

void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    int b = 1e9, c = 1e9, ans = 0;
    for (int i = 0; i < n; i++) {
        if (b > c) {
            swap(b, c);
        }
        if (a[i] <= b) {
            b = a[i];
        } else if (a[i] <= c) {
            c = a[i];
        } else {
            b = a[i];
            ans++;
        }
    }
    cout << ans << endl;
}

int main() {
    int Case;
    cin >> Case;
    while (Case--) {
        solve();
    }
    return 0;
}

D.01 Tree（思维）

题意：

有一棵包含 $n$ 个叶节点的树，保证每个非叶节点均包含两个子节点，同时，对于所有非叶节点，走向子节点的边中均包含权值，且其中一条权值为 $0$ ，另一条权值为 $1$ 。

你忘记了原本的树是什么样子的，只记得根节点到这 $n$ 个叶节点的权值之和，按dfs序给出这些叶节点的权值，问是否存在满足这些节点权值的树。

分析

由于每个非叶节点与子节点之间的边权分别为 $0, 1$ ，那么属于同一个父节点的两个节点的权值之差必然为 $1$ ，且权值较小的一个与父节点的权值一致，由此可知如果给出的叶节点合法，那么必然存在且仅存在一个叶节点的权值为 $0$ 。

同时，由于叶节点以dfs序给出，那么属于同一个父节点的两个叶节点在dfs序中也必然相邻，为了便于处理，使用静态双向链表将 $\sim n$ 这些节点按顺序连在一起。

由于非叶节点的权值与两个子节点的权值较小者相同，那么如果同时删除它的两个子节点（这两个子节点均为叶节点），该节点也会变成叶节点，为了便于处理，可以在操作时仅删除权值较大的节点，将另一个子节点视为删除后新产生的叶节点。

然后考虑从叶节点开始向上删除节点，按以下步骤执行：

删除的节点，它在dfs序中相邻的两个节点中，必然存在一个节点的权值比它小 $1$ （树上仅会存在一个权值为 $0$ 的节点，其他节点权值均大于 $0$ ），此时可以将节点视为待删除节点，放入大根堆中等待删除
当从大根堆取出节点后，就需要对该节点进行删除操作了，由于该节点存储在静态双向链表上，那么需要同时修改前后节点的指针。
然后检查当前节点删除后，左右两边相邻的节点能否进入待删除状态，如果能，就将节点也加入堆中。

删除完成后，如果仅剩下一个权值为 $0$ 的节点未被删除，那么就表示存在满足要求的树，否则，找不到满足要求的树。

代码：

#include<bits/stdc++.h>

using namespace std;

int n, a[200005], pre[200005], nxt[200005], vis[200005];
struct Node{
    int id, val;
    bool operator < (const Node &o) const {
        if (val != o.val) return val < o.val;
        return id > o.id;
    }
};

priority_queue<Node> Q;

int check(int x) {
    return x >= 1 && x <= n && (a[pre[x]] == a[x] - 1 || a[nxt[x]] == a[x] - 1);
}

void solve() {
    cin >> n;
    int zero = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = i - 1;
        nxt[i] = i + 1;
        vis[i] = 0;
        if (a[i] == 0) zero++;
    }
    /*a[0]和a[n + 1]取-1时可能会导致a[1]=0或a[n]=0的情况入队，因此取不影响答案的-2*/
    a[0] = a[n + 1] = -2;
    if (zero == 0) {
        cout << "NO" << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {
    /*找开始时就能进入待删除状态的节点*/
        if (check(i)) {
            vis[i] = 1;
            Q.push(Node{i, a[i]});
        }
    }
    while (!Q.empty()) {
        Node u = Q.top();
        Q.pop();
        /*相当于双向链表中删点，需将前后连起来*/
        nxt[pre[u.id]] = nxt[u.id];
        pre[nxt[u.id]] = pre[u.id];
        /*检查左右的节点能否进入待删除状态*/
        if (vis[nxt[u.id]] == 0 && check(nxt[u.id])) {
            vis[nxt[u.id]] = 1;
            Q.push(Node{nxt[u.id], a[nxt[u.id]]});
        }
        if (vis[pre[u.id]] == 0 && check(pre[u.id])) {
            vis[pre[u.id]] = 1;
            Q.push(Node{pre[u.id], a[pre[u.id]]});
        }
    }
    /*由于权值为0的节点必然不会被删除，那么只需要判断剩余的节点数量.
    如果为1，那么剩下的节点权值必然为0*/
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (vis[i] == 0) {
            cnt++;
        }
    }
    if (cnt == 1) cout << "YES" << endl;
    else cout << "NO" << endl;
}

int main() {
    int Case;
    cin >> Case;
    while (Case--) {
        solve();
    }
    return 0;
}

E. 更新中…

F1.Wine Factory (Easy Version)(后缀和，线段树)

题意：

有 $n$ 座水塔，其中第 $i$ 座包含 $a_i$ 升的水，且拥有一个能消除 $b_i$ 升水的法师，同时相邻两座水塔之间拥有一道阀门，第 $i$ 座高塔与第 $i + 1$ 座水塔之间的阀门允许通过 $c_i$ 升水。

对于第 $i (i = 1, 2, ..., n)$ 座塔，将会进行以下操作：

法师将水塔 $i$ 中最多 $b_i$ 升的水消除，并将消除的水转化为等量的红酒。
如果 $\ne n$ ，那么至多 $c_i$ 升水可以由阀门流到第 $i + 1$ 座水塔。

题目将给出 $q$ 次更新，每次给出四个数字 $p, x, y, z$ ，即将 $a_p = x, b_p = y, c_p = z$ ，并要求对于每次更新，输出最多能获得多少升红酒。

特殊条件：对于所有数据，有 $c_i = 10^{18}, z = 10^{18}$

分析：

对于特殊条件， $c_i, z$ 均为 $10^{18}$ ，由于 $\sum\limits_{i = 1}^{n}max(a_i) = 5 \times 10^{14} < 10^{18}$ ，那么如果水塔中的水没有被全部消除，则剩下的水均能流到下一座高塔，即可以不考虑 $c_i$ 这个限制因素。

先考虑每座水塔自身无法消除的水量： $v_i = a_i - b_i$ ，当 $v_i > 0$ 时，未被消除的水量必然需要由后面的法师来进行消除（如果可以的话），因此对于水塔 $k$ 而言，无法消除的水量实际为 $\sum\limits_{i = k}^{n}v_i$ 。那么对于所有水塔来说，无法消除的水量即为 $ma x (f (1), f (2), ..., f (n))$ 。

使用后缀和建一棵线段树，维护区间上的最大值，并使用变量 $s u m$ 记录水塔的总水量。

每次更新水塔 $p$ 时，由于线段树维护的是后缀和，那么对于所有 $\sim n$ 上的点，均不会收到影响，只需要对区间 $\sim p$ 进行更新，先减去原本的 $v_p$ ，再加上当前更新后的新 $v_p = x - y$ 。

那么最后的答案就是 $s u m - ma x (f (1), f (2), ..., f (n))$ ，其中 $ma x (f (1), f (2), ..., f (n))$ 为线段树树根中记录的信息。

代码：

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 5e5 + 5e2;

LL n, q, a[N], b[N];
LL sum, T[N << 2], lazy[N << 2], c[N], v[N], sv[N];

void pushup(int x) {
    T[x] = max(T[x << 1], T[x << 1 | 1]);
}

void build(int l, int r, int x) {
    if (l == r) {
        T[x] = sv[l];
        return;
    }
    int mid = l + r >> 1;
    build(l, mid, x << 1);
    build(mid + 1, r, x << 1 | 1);
    pushup(x);
}

void pushdown(int x) {
    if (lazy[x]) {
        lazy[x << 1] += lazy[x];
        lazy[x << 1 | 1] += lazy[x];
        T[x << 1] += lazy[x];
        T[x << 1 | 1] += lazy[x];
        lazy[x] = 0;
    }
}

void update(int l, int r, int x, int ul, int ur, LL val) {
    if (l >= ul && r <= ur) {
        T[x] += val;
        lazy[x] += val;
        return;
    }
    pushdown(x);
    int mid = l + r >> 1;
    if (ul <= mid) update(l, mid, x << 1, ul, ur, val);
    if (ur > mid) update(mid + 1, r, x << 1 | 1, ul, ur, val);
    pushup(x);
}

void solve() {
    cin >> n >> q;
    sum = 0;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = 1; i < n; i++)  cin >> c[i];
    for (int i = n; i >= 1; i--) {
        v[i] = a[i] - b[i];
        sv[i] = v[i] + sv[i + 1];
        sum += a[i];
    }
    build(1, n, 1);
    while (q--) {
        int p, x, y;
        LL z;
        cin >> p >> x >> y >> z;
        sum -= a[p];//减去原本的水量
        /*减掉原本的vp*/
        update(1, n, 1, 1, p, -v[p]);
        a[p] = x;
        b[p] = y;
        v[p] = x - y;//更新vp
        sum += a[p];//加上现在的水量
        /*加上现在的vp*/
        update(1, n, 1, 1, p, v[p]);
        /*出现负数说明所有水均能消除，此时需要减去的值为0，需取max*/
        cout << sum - max(0ll, T[1]) << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    int Case = 1;
    while (Case--) {
        solve();
    }
    return 0;
}