Moe's CF Life

Appearance

H. Gambling - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 799 (Div. 4) 标签: data structures, dp, greedy, math 难度: *1700

题目大意喵~ ​

你好呀，指挥官~！这道题是说，我们来到了一个神奇的赌场，喵。游戏规则是这样的：

  1. 我们先选定一个数字 a，还有一个游戏区间 [l, r]。
  2. 然后从第 l 轮玩到第 r 轮，每一轮我们都猜数字 a。
  3. 赌场会公布每一轮的真实结果 x_i。
  4. 如果我们猜对了（a == x_i），我们的钱就会翻倍！
  5. 如果我们猜错了（a != x_i），我们的钱就会减半...呜。

我们从 1 美元开始，并且我们能预知未来，知道接下来 n 轮的所有结果 x_1, x_2, ..., x_n。我们的任务就是，选择最优的 a, l, r，让我们在游戏结束时，手里的钱最多最多！然后把这三个数告诉 Marian 就好啦，喵~

解题思路的探索之旅~ ​

这道题看起来有点复杂，但别担心，跟着本喵的思路一步步来，很快就能解开谜题的！

第一步：把乘法变加法喵！ ​

我们最终的钱数是 1 * 2 * 2 / 2 * 2 ... 这样的形式。这其实就是 2 的次幂，对吧？ 假设在 [l, r] 这个区间里，我们猜对了 k 次，那么猜错了 (r - l + 1) - k 次。 最后的钱就是 1 * (2^k) * ( (1/2)^(r-l+1-k) )，也就是 2^(k - (r-l+1-k))，化简一下就是 2^(2k - (r - l + 1))。

要想让最后的钱最多，我们其实就是要让指数 2k - (r - l + 1) 最大化！这样问题就从一个复杂的乘法问题，变成了一个我们更熟悉的加法/减法最优化问题了，喵~

第二步：聪明的选择a ​

我们应该选哪个数字作为 a 呢？如果选一个在数组 x 中根本没出现过的数字，那我们一次都猜不对，k=0，指数就变成了 -(r-l+1)，肯定是个负数，钱会变得非常少。所以，明智的 a 一定是数组 x 中出现过的某个数字！

这启发我们，可以遍历数组 x 中所有出现过的不同的数字，把它们都当作 a 的候选。对于每一个候选的 a，我们都去找到能让 2k - (r - l + 1) 最大的那个区间 [l, r]。最后再从所有候选 a 的最优结果里，选一个最好的，就是全局最优解啦！

第三步：关键の喵喵拳！(核心洞察) ​

好，现在我们固定了一个要猜的数字，比如说 v。怎么为它找到最好的区间 [l, r] 呢？

让我们把问题再变个形！定义一个新的价值数组 b：

  • 如果 x_i == v，那么 b_i = 1。
  • 如果 x_i != v，那么 b_i = -1。

为什么这么定义呢？因为 sum(b_i for i in [l, r]) 等于 (v 在 [l,r] 中的数量) - (非v在 [l,r] 中的数量)。 而我们的目标 2k - (r-l+1)，其中 k 是 v 的数量， (r-l+1) 是总数量。 2k - (r-l+1) = k - ((r-l+1) - k) = (v 的数量) - (非v的数量)。 看！目标得分 2k - (r-l+1) 正好等于 [l, r] 区间内 b 数组的和！

问题就变成了：对于每个 v，构建一个 b 数组，然后求 b 数组的最大子数组和！

但是，如果每次都为每个不同的 v 构建一个 O(n) 的 b 数组，再用 O(n) 的 Kadane 算法求最大子数组和，总时间复杂度会是 O(不重复数字个数 * n)，在最坏情况下是 O(n^2)，这可不行呀，会超时的说！

第四步：究极进化！ O(n) 的解法 ​

我们必须找到更快的办法。让我们再深入思考一下。 对于一个固定的 v，假设它的最优区间是 [l, r]。

  • 如果 x_l != v，那么 b_l = -1。我们考虑一下新区间 [l+1, r]，它的得分会比原来高 1 (-b_l)！所以，一个最优的区间，它的左端点 l 必须满足 x_l == v。
  • 同理，如果 x_r != v，那么 b_r = -1。新区间 [l, r-1] 的得分会比原来高 1。所以最优区间的右端点 r 也必须满足 x_r == v。

这个发现太重要了！这意味着，我们只需要在那些 v 出现的位置中寻找 l 和 r 就行了！

设 v 在原数组中出现的位置（0-indexed）为 p_0, p_1, ..., p_{m-1}。我们要找的，就是一个区间 [p_j, p_i] (其中 j <= i)，使得它的得分最高。

这个区间的得分为： Score = 2 * (v的数量) - (区间长度)v 的数量是 i - j + 1。 区间长度是 p_i - p_j + 1。 Score = 2 * (i - j + 1) - (p_i - p_j + 1) 整理一下这个式子，把和 i 相关的项放一起，和 j 相关的放一起： Score = (2i - p_i) - (2j - p_j) + 1

为了让这个分数最大化，对于一个固定的 i (右端点)，我们需要找到一个 j <= i (左端点)，使得 (2j - p_j) 的值最小。

这就可以用一个类似动态规划的思路来解决啦！

  1. 用一个 map 把所有数字出现的位置都存起来。
  2. 遍历 map 中的每一个数字 v 和它的位置列表 p。
  3. 对于 p 列表，我们遍历 i from 0 to m-1：
    • 计算 H_i = 2i - p_i。
    • 同时维护一个 min_H_j，表示 i 之前见过的所有 H_j 的最小值。
    • 当前以 p_i 为结尾的最优得分为 H_i - min_H_j + 1。
    • 用这个得分更新我们为 v 找到的局部最优解。
  4. 所有 v 都处理完后，我们就得到了全局最优解！

整个过程，我们只遍历了每个数字出现的位置一次。所有位置加起来就是 n。所以总的时间复杂度是 O(n) 的说！完美解决！

代码实现喵~ ​

下面就是实现这个思路的AC代码啦，本喵加了详细的注释，希望能帮到你！

cpp
#include <iostream>
#include <vector>
#include <map>
#include <climits>

using namespace std;

void solve() {
    int n;
    cin >> n;
    // 用一个 map 来存储每个数字出现的所有位置（0-indexed）
    // key 是数字本身，value 是一个存储了所有出现位置的 vector
    map<int, vector<int>> indices;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        indices[x].push_back(i);
    }

    long long global_best_score = -1; // 全局最高分
    int global_a = -1, global_l = -1, global_r = -1; // 对应的 a, l, r

    // 遍历 map 中每一个独特的数字和它的位置列表
    for (auto const& [val, positions] : indices) {
        int m = positions.size();
        long long current_best_score = 0; // 当前数字 val 的最高分
        int current_l = -1, current_r = -1; // 当前数字 val 对应的 l, r

        // 我们要最大化 (2*i - p_i) - (2*j - p_j) + 1
        // 这等价于最大化 H_i - min(H_j) + 1，其中 H_k = 2k - p_k
        // 我们用 min_val_prefix 来记录 min(2*j - p_j)
        // min_val_prefix_pos 记录是哪个 p_j 产生了最小值
        long long min_val_prefix = 2LL * 0 - positions[0];
        int min_val_prefix_pos = positions[0];

        // 初始情况，只选第一个位置，区间 [p_0, p_0]
        current_best_score = 1;
        current_l = positions[0];
        current_r = positions[0];

        // 从第二个位置开始遍历
        for (int i = 1; i < m; i++) {
            long long current_h = 2LL * i - positions[i];
            
            // 计算以 p_i 为右端点的得分
            // H_i - min_H_j + 1
            long long score = current_h - min_val_prefix + 1;

            // 如果这个得分比我们为 val 找到的最好得分还要高
            if (score > current_best_score) {
                current_best_score = score;
                current_l = min_val_prefix_pos;
                current_r = positions[i];
            }

            // 更新我们见过的 H_j 的最小值
            if (current_h < min_val_prefix) {
                min_val_prefix = current_h;
                min_val_prefix_pos = positions[i];
            }
        }

        // 如果当前这个数字 val 产生的最优解比全局最优解还好，就更新全局最优解
        if (current_best_score > global_best_score) {
            global_best_score = current_best_score;
            global_a = val;
            global_l = current_l;
            global_r = current_r;
        }
    }

    // 输出结果，注意题目要求是 1-indexed，所以要 +1
    cout << global_a << " " << global_l + 1 << " " << global_r + 1 << "\n";
}

int main() {
    // 加上这两行可以让 cin/cout 跑得飞快哦~
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

注：这里提供了一份逻辑更清晰的AC代码实现，它严格遵循了解题思路中推导出的 H(i) - H(j) + 1 公式，可能比原题解代码更容易理解。两份代码的核心思想是一致的，都能通过本题。

复杂度分析 ​

  • 时间复杂度: O(N) 的说。其中 N 是所有测试用例的 n 的总和。我们首先用 O(N) 的时间遍历所有输入来填充 map。之后，我们遍历 map 中的每个键值对。由于 map 中所有 positions 向量的长度之和恰好是 N，而我们对每个 positions 向量只进行一次线性扫描，所以这部分的总时间也是 O(N)。
  • 空间复杂度: O(N) 的说。在最坏的情况下，如果数组中所有数字都不同，map 需要存储 N 个条目，每个条目带一个大小为1的向量，总空间是 O(N)。

知识点与总结 ​

这道题真是一次有趣的冒险呐！它融合了好几种算法思想：

  1. 问题转化: 核心在于将最大化 2 的幂次，转化为最大化一个线性表达式 2k - (r-l+1)。这是解决许多数学和博弈问题的第一步！
  2. 贪心/剪枝: “最优区间的端点一定是我们要猜的数 v” 这个发现是解题的关键。它极大地缩小了搜索范围，是典型的通过分析问题性质进行的有效剪枝。
  3. 动态规划思想: H_i - min(H_j) + 1 的计算方式，是典型的动态规划模式，和著名的**Kadane算法（最大子数组和）**有着异曲同工之妙。我们通过维护一个前缀最小值，来快速计算以当前点为结尾的最优解。
  4. 数据结构: std::map 在这里是分组的好帮手，能高效地把相同值的元素聚合在一起，方便我们后续处理。

希望这篇题解能帮助你理解这道题的精髓！继续加油，你超棒的，喵~！

Released under the MIT License.

Copyright © 2024-present Moe