县立樱姬中学 - 题解

标签与难度

标签: 动态规划, 二分查找, 最长上升子序列, DP优化, 贪心难度: 2000

题目大意喵~

Nyaa~ 主人，你好呀！这道题是说，我们有 n 个点，每个点 i 都有一个权值 a[i]。我们可以从一个点 i 跳到另一个点 j，但必须满足三个超~严格的条件哦：

j 的编号必须比 i 小，也就是 j < i。
j 的权值也必须比 i 小，也就是 a[j] < a[i]。
i 和 j 的编号除以 k 的余数不能相同，也就是 i % k != j % k。

对于每一个点 i（从 1 到 n），我们都要找出从它开始，最多能连续跳跃多少次。每次跳跃都必须满足上面的三个条件哦！然后把每个 i 对应的最大跳跃次数依次输出。

举个栗子，一条跳跃路径 i -> j -> l，这里面有两次跳跃，所以长度就是 2 呐。

解题思路分析

这道题，初看起来是不是有点像寻找最长路径的问题呢？喵~ 没错！这本质上是一个动态规划（DP）问题。

让我们先来定义一下状态。设 dp[i] 为从点 i 出发，能够构成的最长跳跃路径的跳跃次数。

根据题目定义，从 i 跳到 j，必须有 j < i。这意味着我们寻找的下一跳，总是在我们已经处理过的点中。这给了我们一个很棒的递推思路！

当我们计算 dp[i] 时，我们可以尝试从 i 跳到任何一个满足条件的 j。如果我们跳到了 j，那么从 i 开始的路径就变成了 i -> j -> ...。这条路径的跳跃次数就是 1 (从 i到j的这次跳跃) + 从 j 开始的最长跳跃次数 dp[j]。

为了让 dp[i] 最大，我们当然要选择那个能让 1 + dp[j] 最大的 j 啦！所以，我们的状态转移方程就是：

dp[i] = 1 + \max(\{dp[j] \mid j < i, a[j] < a[i], i \pmod k \neq j \pmod k\} \cup \{-1\})

这里的 $\max$ 集合里加入一个 -1 是为了处理边界情况：如果找不到任何可以跳的 j，那么 max 的结果就是 -1，dp[i] 就等于 1 + (-1) = 0，表示从 i 出发一次都跳不了，这很合理对吧，喵~

如果我们按照 i 从 1 到 n 的顺序来计算 dp[i]，对于每个 i，我们都遍历所有 j < i 来寻找最优的 j。这个朴素的 DP 写法，时间复杂度会是 $O(N^2)$ 。但是题目中 $N$ 高达 $10^6$ ，平方的复杂度肯定会超时的说！我们得想办法优化它！

优化的魔法！ $O(N \log N)$ 的华丽变身！

这个 "在满足 a[j] < a[i] 的 j 中找某个最优值" 的模式，是不是让你想起了什么？对啦！就是大名鼎鼎的“最长上升子序列”（LIS）的 $O(N \log N)$ 优化方法！我们可以借鉴它的思想。

LIS 的优化，核心是维护一个 g 数组，g[L] 存储的是长度为 L 的上升子序列的最小末尾元素。我们这里也可以做类似的事情。

我们想要快速地找到满足条件的、dp[j] 最大的那个 j。我们可以换个角度思考：对于一个固定的跳跃次数 L，所有能跳 L 次的出发点 j 中，它们的权值 a[j] 最小是多少？

我们定义一个数组 tails，tails[L] 存储所有 dp 值为 L 的点 j 中，最小的权值 a[j]。这个数组 tails 里的值一定是单调递增的。因为如果 tails[L+1] <= tails[L]，那说明有一个点 p (dp[p]=L+1, a[p]=tails[L+1]) 和一个点 q (dp[q]=L, a[q]=tails[L])，我们完全可以用 p 替代 q 成为跳 L 次的路径起点，因为它权值更小，更容易被后面的点作为前驱，所以 tails 数组一定是单调的。

当计算 dp[i] 时，我们想找一个 j，它的 dp[j] 尽可能大，同时 a[j] < a[i]。这等价于在 tails 数组中，找到最大的 L，使得 tails[L] < a[i]。这可以用二分查找来高效完成！

但是！我们还有一个棘手的条件：i % k != j % k。

单纯维护一个 tails 数组就不够了。因为 tails[L] 对应的那个点 j，它的 j % k 可能恰好和 i % k 相等，这样就不能跳了！

怎么办呢？我想到了一个好办法：多存一个备胎！对于每个跳跃次数 L，我们不仅记录权值最小的那个点的信息（我们称它为“最优选择”），还要记录一个“次优选择”：

最优选择 best[L]: 一个二元组 {value, remainder}，记录 dp 值为 L 的所有点中，权值 a[j] 最小的那个点的权值和 j % k。
次优选择 second_best[L]: 另一个二元组，记录 dp 值为 L 的所有点中，在 j % k 与最优选择的 remainder 不同的前提下，权值 a[j] 最小的那个点的信息。

这样一来，当我们处理点 i 时：

我们用二分查找，在 best 数组的 value 上找到最大的 L，使得 best[L].value < a[i]。
我们检查这个 best[L]。如果它的 remainder 不等于 i % k，太棒了！我们找到了一个可以跳的点 j，并且它的 dp 值是 L。所以 dp[i] 就是 L + 1。
如果 best[L].remainder 恰好等于 i % k，最优选择不能用。这时候，“备胎”就派上用场了！我们检查 second_best[L]。如果 second_best[L].value < a[i]，我们就可以用它。dp[i] 同样是 L + 1。
如果 best[L] 和 second_best[L] 都不能用（比如 best[L] 余数相同，而 second_best[L] 的权值又不够小），那我们就不能从能跳 L 次的点转移了。我们只能退而求其次，尝试从能跳 L-1 次的点转移。所以 dp[i] 就是 (L-1) + 1 = L。

计算出 dp[i] 后，我们还要用 (a[i], i % k) 这个新的信息去更新 best[dp[i]] 和 second_best[dp[i]]，以便后面的点使用。更新的逻辑也要小心处理，确保 best 和 second_best 的定义被严格遵守哦。

通过这种方式，我们每次计算 dp[i] 只需要一次二分查找和几次常数时间的比较，总时间复杂度就从 $O(N^2)$ 降到了美妙的 $O(N \log N)$ 啦！

代码实现

这是我根据上面的思路，精心重构的一份代码，希望能帮助主人更好地理解呐~

cpp

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

using namespace std;

// 用一个结构体来存储路径信息，会更清晰喵~
struct PathInfo {
    long long min_val; // 对应路径长度的最小权值
    int remainder;     // 对应点的下标模 k 的余数
};

// 更新某个长度 L 的最优和次优路径信息
void update_tails(long long current_val, int current_rem, int len, vector<PathInfo>& best, vector<PathInfo>& second_best) {
    // 尝试更新最优选择
    if (current_val < best[len].min_val) {
        // 如果新来的这个点和原来的最优选择余数不同，
        // 那么原来的最优选择就降级成次优选择
        if (current_rem != best[len].remainder) {
            second_best[len] = best[len];
        }
        // 无论如何，新来的点成为新的最优选择
        best[len] = {current_val, current_rem};
    } 
    // 如果不能更新最优选择，尝试更新次优选择
    // 条件是：它的余数和最优选择不同，并且它的值比当前的次优选择要小
    else if (current_rem != best[len].remainder && current_val < second_best[len].min_val) {
        second_best[len] = {current_val, current_rem};
    }
}


int main() {
    // 加速输入输出，是好习惯哦~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    long long k;
    cin >> n >> k;

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

    // `best[L]` 存储跳跃次数为 L 的路径起点的 {最小权值, 余数}
    // `second_best[L]` 存储备胎信息
    // N+1 是因为跳跃次数最多为 N-1，长度为 N
    const long long INF = 2e18; // 一个足够大的数
    vector<PathInfo> best(n + 1, {INF, -1});
    vector<PathInfo> second_best(n + 1, {INF, -1});
    
    // 哨兵：0次跳跃，可以认为是一个权值为0，余数为-1（不存在）的点
    // 这样任何点都可以从它“转移”过来，构成1次跳跃
    best[0] = {0, -1}; 

    int max_len = 0; // 当前出现过的最大跳跃次数

    for (int i = 0; i < n; ++i) {
        long long current_val = a[i];
        int current_rem = (i + 1) % k; // 题目是1-based index，我们用0-based，所以i+1

        // 二分查找，找到可以接在后面的最长跳跃路径
        // 我们要找最大的 L，使得 best[L].min_val < current_val
        // `upper_bound` 会找到第一个 > 的位置，它的前一个就是我们要的
        auto it = lower_bound(best.begin(), best.begin() + max_len + 1, current_val, 
            [](const PathInfo& p, long long val){
                return p.min_val < val;
            });
        
        int prev_len = distance(best.begin(), it) - 1;

        int current_jumps = 0;

        // 检查从跳跃次数为 prev_len 的路径后面接上
        if (best[prev_len].remainder != current_rem) {
            // 最优选择可用
            current_jumps = prev_len + 1;
        } else if (second_best[prev_len].min_val < current_val) {
            // 最优选择余数冲突，但次优选择可用
            current_jumps = prev_len + 1;
        } else {
            // 长度为 prev_len 的路径都接不上，只能退一步，接在 prev_len-1 后面
            // (如果 prev_len 是 0，那 prev_len-1 就是 -1，结果是 0 次跳跃)
            current_jumps = prev_len;
        }

        cout << current_jumps << (i == n - 1 ? "" : " ");
        
        // 用当前点的信息去更新 dp 表
        update_tails(current_val, current_rem, current_jumps, best, second_best);
        
        // 更新一下我们见过的最大跳跃次数
        max_len = max(max_len, current_jumps);
    }
    cout << endl;

    return 0;
}

复杂度分析

时间复杂度: $O(N \log N)$ 我们在一个循环中遍历了 n 个点。在循环的内部，最耗时的操作是二分查找，它的复杂度是 $O(\log N)$ （因为 max_len 最多到 N）。其余的操作都是常数时间。所以总的时间复杂度就是 $O(N \log N)$ 啦，喵~
空间复杂度: $O(N)$ 我们主要使用了 a 数组，以及 best 和 second_best 两个辅助数组来存储DP的中间状态。它们的大小都和 N 成正比，所以空间复杂度是 $O(N)$ 的说。

知识点总结

这道题真是一道非常好的DP练习题呢！它教会了我们：

动态规划建模: 如何把一个看似复杂的最长路径问题，抽象成一个清晰的DP模型。
LIS优化思想: 核心就是那个 $O(N \log N)$ 的优化技巧！通过维护一个单调的辅助数组（我们这里的 best 数组），并利用二分查找来加速状态转移，是解决这类问题的强大武器。
处理附加约束: 当问题在标准模型（如LIS）上增加额外约束时（比如本题的 i % k != j % k），不要害怕！我们可以通过增加DP状态的维度或者像本题解一样，维护备用信息（次优解） 来巧妙地解决问题。
代码实现细节: 使用结构体能让代码更清晰易读。设置“哨兵”值（比如 best[0]）可以简化边界条件的处理。

希望我的题解能对主人有所帮助！如果还有不明白的地方，随时可以再来问我哦，喵~

县立樱姬中学 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

优化的魔法！O(Nlog⁡N)O(N \log N)O(NlogN) 的华丽变身！ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​