D. Permutation Game - 题解

比赛与标签

比赛: Codeforces Round 943 (Div. 3) 标签: brute force, dfs and similar, games, graphs, greedy, math 难度: *1300

喵喵，这是什么游戏呀？

主人你好呀，欢迎来到本喵的题解小站~ ฅ^•ﻌ•^ฅ

这道题呀，是关于一个叫做“排列游戏”的对决哦！我们有两个玩家，Bodya 和 Sasha，他们在一个由数字 1 到 n 组成的排列 p 上玩游戏。还有一个数组 a，代表每个位置的分数。

游戏规则是这样的说：

1. 游戏总共进行 k 个回合。
2. Bodya 和 Sasha 各自有一个起始位置 P_B 和 P_S。
3. 在每个回合，如果一个玩家在位置 x，他会先获得 a[x] 的分数。
4. 然后，他可以选择留在原地 x，或者移动到新位置 p[x]，为下一回合做准备。
5. 两个玩家同时进行操作，并且都想让自己的分数最大化。

我们的任务就是，在 k 回合后，判断谁的分数更高，谁就赢啦！如果分数一样，就是平局的说。

本喵的思考时间！

这个游戏看起来有点复杂呢，因为每个回合都有选择。如果 k 很大，那选择的可能性不就爆炸了吗？别急别急，让本喵来分析一下，一定有捷径的喵~

关键策略是什么喵？

我们先只考虑一个玩家，比如 Bodya。他的目标是在 k 个回合里拿到最高分。

一个很自然的想法是：Bodya 可以选择先沿着排列 p 的路径移动 m 次，然后在某个位置停下来，在剩下的 k - m 个回合里一直待在原地刷分。

这个策略是最优的吗？是的喵！可以这样想：如果 Bodya 在第 t 回合决定停在位置 y 不动了，那么在接下来的 t+1, t+2, ... 回合，他还有理由再次移动吗？没有啦！因为如果移动到 p[y] 在未来能获得更高的收益，那他当初在第 t 回合就不应该停下来。所以，一个最优的策略一定是**“连续移动 m 次，然后在终点停留 k-m 次”**的形式。

如何计算得分？

好！既然策略简化了，我们来算一下得分。 假设 Bodya 决定移动 m 次（0 <= m < k）。

• 他的移动路径是：pos_0 -> pos_1 -> ... -> pos_m，其中 pos_0 是他的起点，pos_{i+1} = p[pos_i]。
• 在前 m 个回合里，他依次在 pos_0, pos_1, ..., pos_{m-1} 获得分数并移动。这部分得分是 a[pos_0] + a[pos_1] + ... + a[pos_{m-1}}。
• 移动 m 次后，他到达了 pos_m。此时已经过去了 m 个回合。
• 在剩下的 k - m 个回合里，他都停在 pos_m，所以这部分得分是 (k - m) * a[pos_m]。

所以，移动 m 次的总得分就是： Score(m) = (a[pos_0] + ... + a[pos_{m-1}}) + (k - m) * a[pos_m]

k 太大了怎么办？

k 可以达到 10^9，我们不可能去遍历所有 m 从 0 到 k-1 的情况。这里就是问题的关键突破口啦！

排列 p 定义的移动路径，其实是一个功能图。从任何一个点出发，一直走下去，因为总共只有 n 个点，所以最多走 n 步，就一定会遇到之前走过的点，然后就进入一个环里了。

这意味着，一个玩家的移动路径上，不重复的位置最多只有 n 个。我们真的需要考虑移动超过 n 次的策略吗？ 其实不需要哦！我们只需要考虑在前 min(k, n) 步内停下的所有情况就足够了。

• 如果 k < n，我们最多也就能移动 k-1 次，所以我们把从移动 0 次到 k-1 次的所有策略都算一遍，取最大值就好。
• 如果 k >= n，我们只需要考虑移动 0 到 n-1 次的策略。因为任何更长的移动路径，其终点一定和前面 n 步的某个终点是重复的，而且继续在环里绕路不一定比早点停在某个高分点更优。我们把所有在前 n 步停下的可能性都计算一遍，就已经包含了所有最优的决策点了。

最终方案

所以，最终的解法就很清晰了呐：

1. 为 Bodya 计算他的最高分：
   • 模拟他从 P_B 出发，一步步移动。
   • 在移动的第 i 步（0 <= i < min(k, n)），计算如果此时停下，总得分会是多少。
   • 记录所有这些可能得分中的最大值。
2. 用同样的方法为 Sasha 计算他的最高分。
3. 比较两人的最高分，得出比赛结果！

这个方法把一个看似复杂的游戏问题，简化成了一个对 min(k, n) 种策略的简单遍历，是不是很巧妙呀？

看本喵的代码魔法！

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

void solve() {
    long long n;
    long long k;
    int pb, ps;
    std::cin >> n >> k >> pb >> ps;
    
    std::vector<int> p(n + 1);
    for (int i = 1; i <= n; ++i) {
        std::cin >> p[i];
    }
    
    std::vector<long long> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        std::cin >> a[i];
    }

    // 定义一个 lambda 函数，用来计算某个玩家能获得的最大分数
    auto calculate_max_score = [&](int start_pos) {
        long long max_score = 0;
        long long path_score_prefix = 0; // 记录沿路径移动累积的分数
        int current_pos = start_pos;
        
        // 关键点！我们只需要考虑 min(k, n) 种不同的策略就足够了
        // i 代表玩家决定移动 i 次
        long long limit = std::min(k, n);
        
        for (long long i = 0; i < limit; ++i) {
            // 这个循环体计算的是“移动 i 次，然后在终点停留”的策略的总分
            
            // 剩下 k - i 个回合，都会在 current_pos 这个位置获得分数
            long long remaining_turns = k - i;
            // 总分 = 路径分 + 停留分
            long long current_total_score = path_score_prefix + remaining_turns * a[current_pos];
            
            // 更新目前找到的最高分
            if (current_total_score > max_score) {
                max_score = current_total_score;
            }
            
            // 为下一次循环（即移动 i+1 次的策略）做准备
            // 累加当前位置的分数到路径分数中
            path_score_prefix += a[current_pos];
            // 移动到下一个位置
            current_pos = p[current_pos];
        }
        return max_score;
    };

    // 分别计算 Bodya 和 Sasha 的最高分
    long long bodya_score = calculate_max_score(pb);
    long long sasha_score = calculate_max_score(ps);

    // 比较分数并输出结果
    if (bodya_score > sasha_score) {
        std::cout << "Bodya\n";
    } else if (sasha_score > sasha_score) {
        std::cout << "Sasha\n";
    } else {
        std::cout << "Draw\n";
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

跑得快不快喵？

• 时间复杂度: O(min(k, n)) 的说。 对于每个玩家，我们都调用一次 calculate_max_score 函数。这个函数的核心是一个循环，执行 min(k, n) 次。循环内部都是常数时间的操作。所以，每个测试用例的总时间复杂度就是 O(min(k, n))。因为所有测试用例的 n 的总和有上限，所以这个速度是完全没问题的！

• 空间复杂度: O(n) 的说。 我们主要需要空间来存储排列 p 和分数数组 a，它们的大小都和 n 相关。所以空间复杂度是 O(n)。

喵喵小课堂！

这道题真有趣，对吧？它教会了我们几件重要的事情呐：

1. 贪心与问题简化: 面对一个看似有很多选择的游戏问题，首先要思考它的最优策略是否具有某种简单的结构。在这里，我们发现最优策略就是“一路向前，直到某个点停下”，这是一个非常关键的贪心思想，它将问题大大简化了。
2. 利用问题内在结构: 排列 p 构成的路径最多只有 n 个不同的点，这个结构是解决 k 值过大问题的钥匙。当看到排列、置换这类词时，可以多往图论（特别是功能图和环）的方向想一想喵。
3. 大 k 值的处理: 在算法竞赛中，超大的 k 或 t (表示时间或次数) 往往是一个信号，告诉我们不能进行简单的线性模拟。通常需要找到某种循环节、周期性，或者像本题一样，发现有效决策空间其实很小。

希望本喵的讲解对主人有帮助哦！只要肯动脑筋，再复杂的问题也能被我们一步步解开的！加油喵~ ฅ'ω'ฅ