20260402 一道题

目录

16. 小红闯关

题目描述 小红正在玩一个有 nn 个关卡的游戏。通过第 ii 个关卡通常需要消耗 aia_i 个单位的时间。小红必须按照从前往后的顺序依次通过每一个关卡。

特殊机制

  • 道具获取: 每通过 kk 个关卡(无论是消耗时间通过还是使用道具通过),小红都会获得一个“跳关道具”。
  • 道具效果: 跳关道具可以在任意一个关卡使用。使用后,可以不消耗任何时间直接通过该关卡。

问题 请问小红通过全部 nn 个关卡,最少需要消耗多少单位时间?

解

这题还是挺难的,主要是跳关道具必须在完成第 mkmk 个关卡以后才能使用,因此这题不能单纯地找最大值,例如,我们在 [k,2k][k, 2k] 之间找到了整个数组里前 tt 大数的 kk 个,但是手里只有一个跳关道具,因此这剩下的 k−1k-1 个就必须手动通关了。

关键的思路在于,如果我们不找最大值,而是找最小值,可不可以呢?

从头开始遍历数组,我们先假设当前的关卡需要被跳过,并维护一个小根堆用来存储(暂定)被跳过的关卡。 接着,我们通过 ⌊ik⌋\lfloor \frac{i}{k} \rfloor 判断当前最大可使用的道具,如果堆的大小超过当前限制,就放弃跳过消耗最小的那个关卡。

这样做的好处是,我们既动态地维护了数据结构,保证每个节点在被跳过时都符合当前确实有道具可用的情况。同时,我们也解决了道具不必即时使用的问题。 如果我们想的是:拿着道具,并在接下来的一段路的最大值使用它,那么问题来了,我们要如何知道下一个最大值出现在哪里呢?这里需要 O(n)O(n) 判断,总时间复杂度 O(n2)O(n^2) 。

我们在这里成功地运用了逆向思维:我们首先假设所有关卡都使用道具跳过,在不满足跳过条件时,再把那个关卡的“债”还了。笔者感觉很有意思,遂记录。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <vector>
#include <queue>
#include <numeric>

using namespace std;

/**
 * 解决思路:
 * 使用最小堆维护当前已经选择跳过的关卡耗时。
 * 遍历到第 i 个关卡(0-indexed)时,我们已经完成了 i 关,
 * 因此手中累计获得的道具上限为 i / k。
 */
void solve() {
    int n, k;
    if (!(cin >> n >> k)) return;

    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // 最小堆,存储当前被跳过的关卡的耗时
    priority_queue<long long, vector<long long>, greater<long long>> skipped_levels;
    long long total_time = 0;

    for (int i = 0; i < n; ++i) {
        // 先假设当前这一关我们要跳过
        skipped_levels.push(a[i]);

        // 计算当前允许的最大跳关次数
        int max_allowed_skips = i / k;

        // 如果堆的大小超过了当前拥有的道具数,
        // 则必须从堆中弹出一个耗时最小的关卡改为“手动通关”
        if (skipped_levels.size() > (size_t)max_allowed_skips) {
            total_time += skipped_levels.top();
            skipped_levels.pop();
        }
    }

    cout << total_time << endl;
}

int main() {
    // 优化标准流输入输出性能
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

17. 小苯的子串删除

题目描述 小苯有一个长度为 nn 的数字串 ss。他的目标是通过删除操作,使得剩余数字拼接成的数是 3 的倍数。

操作规则 小苯可以进行最多一次操作:

  • 选择一段区间 [l,r](1≤l≤r≤n)[l, r] \quad (1 \le l \le r \le n);
  • 删除该区间内的所有数位 sl,sl+1,…,srs_l, s_{l+1}, \dots, s_r。

问题 请你计算有多少种不同的删除区间方案 [l,r][l, r],能够使删除后的数字串满足是 3 的倍数。

注意事项

  • 特殊情况: 如果删除后数字串为空,小苯认为它也是 3 的倍数。
  • 目标: 统计所有符合条件的 (l,r)(l, r) 对的数量。

解

  1. 数学模型: 假设原始字符串的数字总和为 SS。当我们删除区间 [l,r][l, r] 时,剩余部分的数字之和为 S−(区间 [l,r] 的和)S - (\text{区间 } [l, r] \text{ 的和})。 我们的目标是让:

    (S−∑i=lrai)≡0(mod3)(S - \sum_{i=l}^{r} a_i) \equiv 0 \pmod 3

    这也等价于:

    ∑i=lrai≡S(mod3)\sum_{i=l}^{r} a_i \equiv S \pmod 3

    也就是说,我们需要找出的所有子区间,其内部数字之和对3取模的结果必须等于整个字符串总和对3取模的结果。

  2. 前缀和转化: 设 P[i]P[i] 为前 ii 个数字的和模3的结果(规定 P[0]=0P[0] = 0)。 区间 [l,r][l, r] 的和模3的结果可以表示为:(P[r]−P[l−1])(mod3)(P[r] - P[l-1]) \pmod 3。 我们要找满足以下条件的 (l,r)(l, r) 组合:

    (P[r]−P[l−1])≡S(mod3)(P[r] - P[l-1]) \equiv S \pmod 3
  3. 算法效率: 如果用双重循环枚举 ll 和 rr,复杂度是 O(n2)O(n^2),对于较大的 nn(如 10510^5 以上)会超时。 我们可以利用哈希表或频率数组记录前缀和出现的次数,将复杂度优化到 O(n)O(n)。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <string>
#include <vector>

using namespace std;

long long solve() {
    string s;
    if (!(cin >> s)) return 0;
    int n = s.length();
    
    // 计算总和 S 模 3 的结果
    int total_sum_mod3 = 0;
    for (char c : s) {
        total_sum_mod3 = (total_sum_mod3 + (c - '0')) % 3;
    }

    // 特殊情况:如果总和已经是3的倍数,我们要找区间和模3等于0的子区间
    // 目标:(P[r] - P[l-1]) % 3 == total_sum_mod3
    
    // count[v] 记录前缀和模 3 等于 v 的出现次数
    vector<long long> count(3, 0);
    count[0] = 1; // 初始前缀和 P[0] = 0
    
    int current_prefix_sum = 0;
    long long ans = 0;

    for (int i = 0; i < n; ++i) {
        // 更新当前前缀和
        current_prefix_sum = (current_prefix_sum + (s[i] - '0')) % 3;
        
        // 我们需要找到之前的某个前缀和 prev_prefix_sum 使得:
        // (current_prefix_sum - prev_prefix_sum + 3) % 3 == total_sum_mod3
        // 移项得:
        int target = (current_prefix_sum - total_sum_mod3 + 3) % 3;
        
        // 累加之前出现过多少次这个 target
        ans += count[target];
        
        // 记录当前前缀和出现的次数
        count[current_prefix_sum]++;
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cout << "请输入数字串: ";
    cout << "\n满足条件的操作数: " << solve() << endl;

    return 0;
}