JSCPC补题#

赛时只切了签到，~~太丢脸~~，I本可以但是被误导了（~~太可惜~~），A被卡PY了，1：1转换的C++可过，~~太可惜~~，萌新第一次参加省赛，本就带着被搏杀的心态，不过也是感受到了XCPC比赛现场的氛围，不后悔(补题以H这道反悔贪心做结束)。

下面是补题（×），补个der，拼尽全力也想不出除ACI外的其他题，太多思维题了，被吓哭了，于是召唤gemini3PRO，协助补题

Easy：I、C

Easy-Mid：A、B、F、L

Mid：H、J、K

其余三题不属于我能看的，，，，

除ICA外其余题的题解均来自gemini3PRO，提供的代码均AC

26年JSCPC.pdf

I-模拟题

非常遗憾的一道签到题，赛时队友说是经典题，要动用神秘小算法，实际上，只要简简单单的模拟即可，太可惜！

1
word = []
2
import string
3
words = list(string.ascii_lowercase)
4
for a in words:
5
    for b in words:
6
        word.append(a+b)
7
sorted(word)
8
for _ in range(int(input())):
9
    ok = False
10
    ans = ''
11
    s1 = input().strip()
12
    s2 = input().strip()
13
    for c in word:
14
        c1 = c[0]
15
        c2 = c[1]
16
        if (c1 in s1 and c2 in s1 and s1.find(c1) < s1.find(c2,s1.find(c1)+1)) and (c1 in s2 and c2 in s2 and s2.find(c1) < s2.find(c2,s2.find(c1)+1)):
17
            ok = True
18
            ans = c
19
            break
20
    if ok:
21
        print(ans)
22
    else:
23
        print('HENG!')

C-位运算思维题

熟悉按位与、异或、或的运算先后顺序以及字符串为01串的性质

只要字符串有’0’存在，在每个字符都进行按位与运算即可

对于全是1的情况，由于按位与的运算优先级最高，故只需要在第一个和第二个字符之间插入按位异或，其余位置插入按位与即可

1
n = int(input().strip())
2
s = input().strip()
3
ans = ''
4
if '0' in s:
5
    ans = '&'*(n-1)
6
else:
7
    ans = '^'+'&'*(n-2)
8
print(ans)

A-二分答案+区间覆盖

非常可惜的一道题，赛时思路和正解一模一样，可惜被卡了PY，哭死

区间覆盖转化：

假设当前二分枚举到的时间是 $T$ 。对于第 $i$ 个舞者：

如果他还没有出生（即 $T < a_i$ ），那么他对当前时间没有贡献。
如果他已经出生（即 $T \ge a_i$ ），他已经存活了 $T - a_i$ 秒。由于他每秒向左右各扩展 1 个单位，所以该舞者及其召唤出的分身能覆盖的连续坐标区间为：

$[b_i - (T - a_i), \ b_i + (T - a_i)]$

将所有满足条件的舞者的覆盖区间收集起来，问题就转换为了：判断这些线段能否完全覆盖住区间 $[0, k]$ 的所有整数点。

合并区间判定：

将收集到的所有区间按照左端点从小到大排序。
设定当前已经连续覆盖到的最右侧端点 cur_R = -1。
遍历排序后的区间：
如果下一个区间的左端点 $L \le \text{cur\_R} + 1$ （注意：因为坐标是整数，所以两个区间哪怕没有交点，只要相差 1 也能算作整数连续覆盖，例如 $[0, 2]$ 和 $[3, 5]$ 合起来能覆盖 $0 \sim 5$ ）。
更新 cur_R 。
如果 $L > \text{cur\_R} + 1$ ，说明出现了无法弥补的空隙，直接跳出判断。
最后只需检查 cur_R 是否大于等于 $k$ 即可。

1
import sys
2
def solve():
3
    input = lambda:sys.stdin.readline().strip()
4
    n,k = map(int,input().strip().split())
5
    zombies = []
6
    for _ in range(n):
7
        a,b = map(int,input().split())
8
        zombies.append((a, b))
9
    def check(T):
10
        t = []
11
        for a, b in zombies:
12
            if T >= a:
13
                spread = T - a
14
                t.append((b - spread, b + spread))
15
        if not t:
16
            return False
17
        t.sort()
18
        cur_R = -1
19
        for L, R in t:
20
            if L <= cur_R + 1:
21
                if R > cur_R:
22
                    cur_R = R
23
            else:
24
                break
25
        return cur_R >= k
26
    l,r = -1,10**9
27
    while l + 1 < r:
28
        mid = (l + r)//2
29
        if check(mid):
30
            r = mid
31
        else:
32
            l = mid
33
    print(r)
34
if __name__ == '__main__':
35
    solve()

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
using namespace std;
5
void solve() {
6
    long long n, k;
7
    if (!(cin >> n >> k)) return;
8
    vector<pair<long long, long long>> zombies(n);
9
    for (int i = 0; i < n; ++i) {
10
        cin >> zombies[i].first >> zombies[i].second;
11
    }
12
    auto check = [&](long long T) {
13
        vector<pair<long long, long long>> t;
14
        for (const auto& zombie : zombies) {
15
            long long a = zombie.first;
16
            long long b = zombie.second;
17
            if (T >= a) {
18
                long long spread = T - a;
19
                t.push_back({b - spread, b + spread});
20
            }
21
        }
22
        if (t.empty()) {
23
            return false;
24
        }
25
        sort(t.begin(), t.end());
26
        long long cur_R = -1;
27
        for (const auto& interval : t) {
28
            long long L = interval.first;
29
            long long R = interval.second;
30

31
            if (L <= cur_R + 1) {
32
                if (R > cur_R) {
33
                    cur_R = R;
34
                }
35
            } else {
36
                break;
37
            }
38
        }
39
        return cur_R >= k;
40
    };
41
    long long l = -1;
42
    long long r = 1000000000000000000LL;
43

44
    while (l + 1 < r) {
45
        long long mid = (l + r) / 2;
46
        if (check(mid)) {
47
            r = mid;
48
        } else {
49
            l = mid;
50
        }
51
    }
52

53
    cout << r << "\n";
54
}
55
int main() {
56
    ios_base::sync_with_stdio(false);
57
    cin.tie(NULL);
58
    solve();
59
    return 0;
60
}

F-数学思维题

取值范围的连续性：

假设能通过某组 $a$ 和 $m$ 得到 $\text{mex}(a) = k$ ，那么一定也能得到 $\text{mex}(a) = k-1$ 。只需要找到原数组 $a$ 中等于 $k-1$ 的那个数，给它加上一个足够大的 $m$ 的倍数（例如 $C \cdot m$ ），让它变成一个极大的数即可。这样 $k-1$ 就从数组中消失了，而比 $k-1$ 小的数不受影响，新的 $\text{mex}$ 就变成了 $k-1$ 。

结论：可能得到的 $\text{mex}$ 值一定是从 $0$ 开始的**连续整数区间 ** $[0, K_{\max}]$ ，因此答案就是 $K_{\max} + 1$ 。

模数 $m$ 的下界限制：

由于 $b_i = a_i \bmod m$ ，根据取模的定义，余数一定小于模数，所以必须满足 $m > \max(b)$ 。

令 $M = \max(b)$ ，则**模数 $m$ 最少为 ** $M + 1$ 。

**如何得到最大的 ** $K_{\max}$

如果要凑出 $\text{mex} = k$ ，意味着 $0, 1, 2, \dots, k-1$ 都要在数组 $a$ 中出现。

因为 $m > M$ ，对于任何 $x \in \{0, 1, \dots, k-1\}$ ，如果要让 $a_i = x$ ，由于 $a_i \equiv b_i \pmod m$ ，必定要求 $b_i = x \bmod m$ 。

这里分为两种情况：

情况一： $\text{mex}(b) \le M$

这意味着在 $0$ 到 $M$ 之间，有一个最小的数（即 $\text{mex}(b)$ ）在 $b$ 中完全没有出现过。因为无论选多大的 $m > M$ ，都无法凭空变出这个余数，所以永远也凑不出这个缺失的数。

在这种情况下，最大的 $K_{\max} = \text{mex}(b)$ 。

情况二： $\text{mex}(b) = M + 1$

这意味着 $0, 1, \dots, M$ 每一个数都在 $b$ 中出现了至少一次。

此时为了让 $k$ 尽可能大，只需取 $m$ 的下界，即 $m = M + 1$ 。

对于 $b$ 中的某个值 $x$ （ $0 \le x \le M$ ），它在 $b$ 中出现了 $cnt[x]$ 次。它能贡献出的 $a_i$ 的值依次为： $x,\ x + m,\ x + 2m, \dots$ 。

这 $cnt[x]$ 个坑位，最多只能撑到 $x + (cnt[x] - 1) \cdot m$ 。一旦试图突破，就会因为 $x$ 对应的余数不够用而断档。断档的那个值就是 $x + cnt[x] \cdot m$ 。

因为 $\text{mex}$ 取决于“木桶效应”里最短的那块板，所以最大能达到的 $K_{\max}$ 就是所有余数断档值的最小值：

K_{\max} = \min_{0 \le x \le M} \big(x + cnt[x] \cdot (M + 1)\big)

1
n = int(input().strip())
2
a = list(map(int,input().strip().split()))
3
m = max(a)
4
p = [False]*(n+2)
5
for x in a:
6
    if x <= n + 1:
7
        p[x] = True
8
mex = 0
9
while p[mex]:
10
    mex += 1
11
if mex <= m:
12
    print(mex + 1)
13
else:
14
    cnt = [0]*(m+1)
15
    for x in a:
16
        if x <= m:
17
            cnt[x] += 1
18
    max_k = min(x + cnt[x]*(m+1) for x in range(m + 1))
19
    print(max_k + 1)

B-数学思维题

向平方根靠拢

题目要求寻找非负整数 $a, b, c$ 满足 $a \times b + c = x$ ，且极差 $\max(a, b, c) - \min(a, b, c)$ 尽可能小。

为了让三者的差距最小，理想情况下它们应该尽可能接近。由于 $a \times b \approx x$ ，那么 $a$ 和 $b$ 必然都在 $\sqrt{x}$ 的附近。

枚举策略

设定 $a \le b$ 。为了以最快速度找到最优解，我们**从 $a = \lfloor\sqrt{x}\rfloor$ 开始，逆向向下枚举 ** $a$ 。

对于每一个固定的 $a$ ，为了让 $b$ 靠近 $a$ 且 $c$ 最小，基础的 $b$ 应该是商： $b_{\text{base}} = \lfloor x / a \rfloor$ 。

此时基础的 $c$ 就是余数： $c_{\text{base}} = x \bmod a$ 。

内层枚举

有时候基础的 $c_{\text{base}}$ 可能会比 $a$ 和 $b$ 小很多。此时可以“牺牲”一点 $b$ ，来“喂饱” $c$ 。

具体来说，如果将 $b$ 减小 $1$ ，那么为了保持总和等于 $x$ ， $c$ 就必须增加 $a$ 。

因为 $a$ 在 $\sqrt{x}$ 附近，这种补偿非常剧烈，我们只需要让 $b$ 向下减小 $0$ 到 $4$ 次，就绝对能覆盖所有可能让极差缩小的组合了。超出这个微调范围， $c$ 就会变得太大，极差反而会飙升。

剪枝

这是最关键的一步，也是解决 TLE 的根本！

随着枚举的推进， $a$ 越来越小，导致 $b_{\text{base}} = \lfloor x / a \rfloor$ 越来越大。

这意味着 $b_{\text{base}}$ 和 $a$ 的差距是严格单调递增的。

如果发现当前的 $b_{\text{base}} - a$ 已经大于或等于我们手中目前的最优极差（加上内层循环微调的容错值 5），那就说明：再往下枚举，即便怎么微调，a 和 b 的撕裂程度都已经超过了历史最优解，不可能再产生更小的极差了！

此时直接 break 结束当前用例的寻找。

1
#include <iostream>
2
#include <cmath>
3
#include <algorithm>
4
using namespace std;
5
void solve() {
6
    long long x;
7
    cin >> x;
8
    if (x == 0) {
9
        cout << 0 << "\n";
10
        return;
11
    }
12
    long long k = sqrt(x);
13
    long long ans = x;
14

15
    for (long long a = k; a >= 1; --a) {
16
        long long b_base = x / a;
17
        if (b_base - a >= ans + 5) {
18
            break;
19
        }
20

21
        long long rem = x % a;
22
        for (long long nx = 0; nx < 5; ++nx) {
23
            long long b = b_base - nx;
24
            if (b < 0) {
25
                break;
26
            }
27
            long long c = rem + nx * a;
28

29
            long long mn = min({a, b, c});
30
            long long mx = max({a, b, c});
31
            long long sp = mx - mn;
32

33
            if (sp < ans) {
34
                ans = sp;
35
            }
36
        }
37
    }
38
    cout << ans << "\n";
39
}
40

41
int main() {
42
    ios_base::sync_with_stdio(false);
43
    cin.tie(NULL);
44
    int t;
45
    if (cin >> t) {
46
        while (t--) {
47
            solve();
48
        }
49
    }
50
    return 0;
51
}

L-博弈思维题

状态转换：从原数组到差分数组

将数组 $a$ 降序排序，并在末尾补上一个 $0$ （即 $a_{n+1} = 0$ ）。

观察相邻元素的差值，构造差分数组 $D$ ：

D_k = a_k - a_{k+1} \quad (1 \le k \le n)

比如数组 $a = [4, 2, 1, 1]$ ，补 $0$ 后为 $[4, 2, 1, 1, 0]$ 。

对应的差分数组 $D = [2, 1, 0, 1]$ 。

操作的本质

如果在降序数组中，玩家选择了一个值 $a_k$ （必须满足 $a_k > a_{k+1}$ ，也就是差分 $D_k > 0$ ），根据游戏规则：

所有 $> a_k$ 的元素全部变成 $a_k$ 。
选中的 $a_k$ 变成 $a_k - 1$ 。
其余 $\le a_k$ 的元素保持不变。

对应到差分数组 $D$ 上，这个操作等价于：

$D_k \leftarrow D_k - 1$
$D_{k-1} \leftarrow 1$ （如果 $k > 1$ ）
$D_1 \sim D_{k-2}$ 全部被清零（即 $D_i \leftarrow 0$ ）
$D_{k+1}$ 及以后的元素完全不变。

必胜态（W）与必败态（L）的判定

注意差分数组的一个致命特性：对 $D_k$ 的操作，会瞬间将 $k-1$ 之前的所有历史状态全部抹除（归零）！

通过严格的博弈论推导，我们发现只有奇数索引位置（ $D_1, D_3, D_5 \dots$ ）的奇偶性才决定游戏胜负：

必胜态（Insight 赢）：存在至少一个奇数索引 $i$ （如 1, 3, 5…），使得 $D_i$ 为奇数。
必败态（Maya 赢）：所有奇数索引 $i$ 上的 $D_i$ 全都是偶数。

为什么这个结论是对的？

如果当前是必败态（全是偶数）：不管玩家选哪个合法的 $k$ （ $D_k > 0$ ），
如果选奇数 $k$ ， $D_k$ 减 $1$ 变成奇数，把一个奇数留给了对手。
如果选偶数 $k$ ，规则会强制令 $D_{k-1} = 1$ 。因为 $k$ 是偶数， $k-1$ 就是奇数，同样把一个奇数留给了对手。
无论怎么走，都会把必胜态拱手让给对方。
如果当前是必胜态（有奇数）：玩家只需找到**最靠右的、值为奇数的奇数索引 ** $k$ ，然后选择它。
$D_k$ 减 $1$ 变成了偶数。
$D_{k-1}$ 虽然变成 $1$ ，但 $k-1$ 是偶数索引，不影响胜负判定。
最恐怖的是，所有 $< k-1$ 的差分值全部被清零（变成了偶数）。
这完美地将场上所有奇数索引的值变成了偶数，直接把必败态踢给对手！

结论：降序排序后，将相邻两项两两分组。如果存在一组的差值为奇数，则先手（Insight）必胜；否则后手（Maya）必胜。

1
def main():
2
    for _ in range(int(input().strip())):
3
        n = int(input().strip())
4
        a = list(map(int,input().strip().split()))
5
        a.sort(reverse=True)
6
        a.append(0)
7
        ok = False
8
        for i in range(0, n, 2):
9
            diff = a[i] - a[i + 1]
10
            if diff % 2 != 0:
11
                ok = True
12
                break
13
        if ok:
14
            print("Insight")
15
        else:
16
            print("Maya")
17
if __name__ == '__main__':
18
    main()

K-离线处理+线段树+贪心

固定的买入行为

买入阈值 $a$ 是固定的。无论询问的卖出阈值 $b$ 是多少，触发买入的时间点和总买入次数永远不变（即满足 $v_i \le a$ 的点）。

因此，我们能够在一开始就算出：总买入股票数量 Total_B 和 总买入成本 Total_Cost。

左到右贪心匹配机制

对于任何给定的 $b$ ，合法的卖出点就是那些 $v_i \ge b$ 的点。

机器人的交易逻辑是“遇到能卖的，只要手里有股票就立刻卖”。这可以完全等效为一个括号匹配模型：

买入操作（ $v_i \le a$ ）视作左括号 (
卖出操作（ $v_i \ge b$ ）视作右括号 )
机器人从左到右匹配，只要有未匹配的 (，遇到 ) 就立刻匹配。
任何到最后都没有被匹配的 (（即最后手中剩下的股票），都会在最后以平仓价 $v_n$ 卖出。

收益公式的统一化

根据以上结论，总收益的计算公式可以简化为：

\text{总收益} = \text{成功匹配的卖出总金额} + (\text{总买入数量} - \text{成功匹配的数量}) \times v_n - \text{总买入成本}

在这其中，买入数量、平仓价 $v_n$ 、买入成本都是常数，我们唯一需要动态维护的，就是“成功匹配的卖出点所带来的金额总和”以及“成功匹配的数量”。

如果针对每个询问单独从头模拟，复杂度将是 $O(N \times M)$ ，必将超时。

由于多个询问之间只有参数 $b$ 不同，我们采用离线处理策略：

将所有查询按照 $b$ 从大到小降序排序。
随着 $b$ 的减小，会有越来越多的历史价格 $v_i$ 跨过 $b$ 的门槛，成为“有效卖出点”。
我们每次只需单点激活这些新的有效卖出点即可。

线段树的设计（核心难点）：

为了在 $O(\log N)$ 时间内更新一次，我们需要一颗区间线段树。线段树的每一个节点管理一个时间区间 $[L, R]$ ，并维护该区间内部：

cnt_B：内部未被匹配的买入次数（左括号）
cnt_S：内部未被匹配的激活卖出次数（右括号）
sum_S：内部未被匹配的激活卖出的金额之和
matched_sum：内部已经成功匹配的卖出金额之和

合并两个子区间（Left 和 Right）时的物理意义：

左区间的剩余 ( 会遇到右区间的剩余 ) 并发生匹配。
匹配数量 $M = \min(\text{Left.cnt\_B}, \text{Right.cnt\_S})$ 。
贪心策略下，左边过来的股票，一定会匹配到右区间最靠前的 $M$ 个可用卖出点！
为了实现这一点，我们需要在右区间内进行递归搜索函数 get_sum_slice，询问：“右区间内前 $M$ 个未匹配的卖出点，金额之和是多少？”
借助这个函数，父节点可以精准快速地（ $O(\log N)$ ）合并左右区间。

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4

5
using namespace std;
6

7
struct Node {
8
    int cnt_B;
9
    int cnt_S;
10
    long long sum_S;
11
    long long matched_sum;
12
};
13

14
const int MAXN = 200005;
15
Node tree[4 * MAXN];
16
long long v[MAXN];
17
long long a;
18

19
// 核心函数：查询节点 node 内部，前 k 个未被匹配的卖出点的金额总和
20
long long get_sum_slice(int node, int L, int R, int st, int k) {
21
    if (k == 0) return 0;
22
    // 如果需要的数量正好等于该节点总的未匹配卖出数，直接 $O(1)$ 返回，极大加速
23
    if (k == tree[node].cnt_S) return tree[node].sum_S;
24

25
    int mid = L + (R - L) / 2;
26
    int left_child = 2 * node;
27
    int right_child = 2 * node + 1;
28

29
    int C_L = tree[left_child].cnt_S;
30
    if (st + k <= C_L) {
31
        return get_sum_slice(left_child, L, mid, st, k);
32
    }
33

34
    int M = min(tree[left_child].cnt_B, tree[right_child].cnt_S);
35
    if (st >= C_L) {
36
        int st_R = M + (st - C_L);
37
        return get_sum_slice(right_child, mid + 1, R, st_R, k);
38
    }
39

40
    // 如果横跨左右子树的未匹配队列
41
    int k1 = C_L - st;
42
    int k2 = k - k1;
43
    return get_sum_slice(left_child, L, mid, st, k1) +
44
           get_sum_slice(right_child, mid + 1, R, M, k2);
45
}
46

47
void pull(int node, int L, int R) {
48
    int left_child = 2 * node;
49
    int right_child = 2 * node + 1;
50
    int mid = L + (R - L) / 2;
51

52
    int M = min(tree[left_child].cnt_B, tree[right_child].cnt_S);
53

54
    tree[node].cnt_B = tree[left_child].cnt_B - M + tree[right_child].cnt_B;
55
    tree[node].cnt_S = tree[left_child].cnt_S + tree[right_child].cnt_S - M;
56

57
    // 获取右子区间被匹配掉的前 M 个卖出点金额
58
    long long matched_R = get_sum_slice(right_child, mid + 1, R, 0, M);
59

60
    tree[node].sum_S = tree[left_child].sum_S + tree[right_child].sum_S - matched_R;
61
    tree[node].matched_sum = tree[left_child].matched_sum + tree[right_child].matched_sum + matched_R;
62
}
63

64
void build(int node, int L, int R) {
65
    if (L == R) {
66
        if (v[L] <= a) {
67
            tree[node].cnt_B = 1;
68
            tree[node].cnt_S = 0;
69
            tree[node].sum_S = 0;
70
            tree[node].matched_sum = 0;
71
        } else {
72
            tree[node].cnt_B = 0;
73
            tree[node].cnt_S = 0;
74
            tree[node].sum_S = 0;
75
            tree[node].matched_sum = 0;
76
        }
77
        return;
78
    }
79
    int mid = L + (R - L) / 2;
80
    build(2 * node, L, mid);
81
    build(2 * node + 1, mid + 1, R);
82
    pull(node, L, R);
83
}
84

85
void update(int node, int L, int R, int idx) {
86
    if (L == R) {
87
        tree[node].cnt_S = 1;
88
        tree[node].sum_S = v[idx];
89
        return;
90
    }
91
    int mid = L + (R - L) / 2;
92
    if (idx <= mid) update(2 * node, L, mid, idx);
93
    else update(2 * node + 1, mid + 1, R, idx);
94
    pull(node, L, R);
95
}
96

97
void solve() {
98
    int n;
99
    cin >> n >> a;
100

101
    long long Total_B = 0;
102
    long long Total_Cost = 0;
103
    vector<pair<long long, int>> sells;
104

105
    for (int i = 1; i <= n; i++) {
106
        cin >> v[i];
107
        if (v[i] <= a) {
108
            Total_B++;
109
            Total_Cost += v[i];
110
        } else {
111
            sells.push_back({v[i], i});
112
        }
113
    }
114

115
    build(1, 1, n);
116

117
    int m;
118
    cin >> m;
119
    vector<pair<long long, int>> queries(m);
120
    for (int i = 0; i < m; i++) {
121
        cin >> queries[i].first;
122
        queries[i].second = i;
123
    }
124

125
    // 降序排序
126
    sort(sells.rbegin(), sells.rend());
127
    sort(queries.rbegin(), queries.rend());
128

129
    vector<long long> ans(m);
130
    int p = 0;
131

132
    for (int i = 0; i < m; i++) {
133
        long long b = queries[i].first;
134
        int q_idx = queries[i].second;
135

136
        // 激活大于等于当前 b 阈值的卖出点
137
        while (p < sells.size() && sells[p].first >= b) {
138
            update(1, 1, n, sells[p].second);
139
            p++;
140
        }
141

142
        long long matched_count = Total_B - tree[1].cnt_B;
143
        long long profit = tree[1].matched_sum + (Total_B - matched_count) * v[n] - Total_Cost;
144
        ans[q_idx] = profit;
145
    }
146

147
    for (int i = 0; i < m; i++) {
148
        cout << ans[i] << (i == m - 1 ? "" : " ");
149
    }
150
    cout << "\n";
151
}
152

153
int main() {
154
    // 接触 I/O 封印，极大提升运行速度
155
    ios_base::sync_with_stdio(false);
156
    cin.tie(NULL);
157
    int T;
158
    if (cin >> T) {
159
        while (T--) solve();
160
    }
161
    return 0;
162
}

H-反悔贪心

统一价值度量：

一枚金币等于 $k$ 块钱，也可以造成 $k$ 点伤害。一枚银币等于 $1$ 块钱，造成 $1$ 点伤害。

因此，不论是金币还是银币， $1$ ** 点伤害的成本永远是 $1$ 块钱 **。我们要让最终剩余的钱最多，就等价于让打怪时浪费的伤害总和最小。

只有在使用金币对抗不足 $k$ 点血量的目标时，才会产生“伤害溢出”的浪费。

贪心策略与反悔机制：

面对血量为 $x$ 的怪物，令 $q = \lfloor x / k \rfloor$ ， $r = x \bmod k$ 。

对于 $q \times k$ 的部分：用 $q$ 枚金币是完美无缺的（浪费为 $0$ ）。如果没有足够的金币，只能强制用银币凑，这也是无法避免的。
对于余数 $r$ 的部分：

我们总是优先假设使用 $r$ 枚银币（因为这也不会造成任何浪费）。

但是，万一我们后来遇到银币不足的情况怎么办？

这时候，我们可以进行反悔（Regret）：我们可以假装“之前某个怪物我不花 $r$ 枚银币了，我改用 $1$ 枚金币砸死它”，这样我们虽然浪费了 $k-r$ 的伤害，但是成功拿回了 $r$ 枚银币用于救急！

数据结构维护：

我们需要维护当前拥有的金币 $G$ 、银币 $S$ ，以及一个记录所有可反悔操作的数据结构 H（存放着所有我们决定用银币垫付的 $r$ ）。

H 的容量不能超过当前 $G$ 的数量。因为如果要反悔，你必须得交得出 $1$ 枚金币。
如果 $G$ 不够用了（比如要支付 $q$ 的时候金币不够），我们就从 H 中删去最小的 $r$ （取消反悔权），以腾出金币去支付 $q$ 。
如果 $S < 0$ 欠债了，我们就从 H 中弹出最大的 $r$ 执行反悔（消耗 $1$ 枚金币，换取最多的银币补齐欠款）。

在 C++ 中，std::multiset 天然支持完美获取/删除最值，代码可以写得极为优雅紧凑。注意开 long long 防止 G 累加越界。

1
#include <iostream>
2
#include <vector>
3
#include <set>
4
#include <algorithm>
5

6
using namespace std;
7

8
void solve() {
9
    long long n, k;
10
    cin >> n >> k;
11

12
    long long G = 0, S = 0;
13
    multiset<long long> H;
14
    bool possible = true;
15

16
    for (int i = 0; i < n; ++i) {
17
        long long o, x;
18
        cin >> o >> x;
19

20
        if (!possible) continue; // 如果已经无法存活，只需读取剩下的输入，不再进行逻辑处理
21

22
        if (o == 1) {
23
            G += x;
24
        } else if (o == 2) {
25
            S += x;
26
        } else if (o == 3) {
27
            long long q = x / k;
28
            long long r = x % k;
29

30
            // 处理大块 q：必须用到实打实的金币
31
            long long free_G = G - H.size();
32
            long long use_free = min(q, free_G);
33
            G -= use_free;
34
            q -= use_free;
35

36
            // 如果自由金币不够，只能从历史记录中强行取消一些反悔权（取消最小的，损失最少）
37
            while (q > 0 && !H.empty()) {
38
                H.erase(H.begin());
39
                G -= 1;
40
                q -= 1;
41
            }
42

43
            if (q > 0) {
44
                S -= q * k;
45
            }
46

47
            // 处理余数 r：优先用银币支付
48
            S -= r;
49
            if (r > 0) {
50
                if (G > (long long)H.size()) {
51
                    H.insert(r);
52
                } else if (!H.empty() && r > *H.begin()) {
53
                    H.erase(H.begin());
54
                    H.insert(r);
55
                }
56
            }
57

58
            // 债务结算：如果银币超支了，行使反悔权（消耗1金币换回当初交出去的银币）
59
            while (S < 0 && !H.empty()) {
60
                auto it = prev(H.end());
61
                long long r_max = *it;
62
                H.erase(it);
63
                G -= 1;
64
                S += r_max;
65
            }
66

67
            if (S < 0) {
68
                possible = false;
69
            }
70
        }
71
    }
72

73
    if (possible) {
74
        cout << G * k + S << "\n";
75
    } else {
76
        cout << "-1\n";
77
    }
78
}
79

80
int main() {
81
    ios_base::sync_with_stdio(false);
82
    cin.tie(NULL);
83

84
    int t;
85
    if (cin >> t) {
86
        while (t--) solve();
87
    }
88

89
    return 0;
90
}

音乐

音乐

JSCPC补题#

音乐

目录