Consecutive Subsequence

GitHub跳转原题关系图返回列表

按结尾定义长度 + 用值到最后出现位置的桶替代前驱枚举 + 沿 pre 链回推下标

OJ: codeforces

题目 ID: 977F

难度:普及

标签:动态规划线性DP哈希表

创建: 2026-11-04 14:50

更新: 2026-11-06 20:40

RBook 文章:
最长上长子序列

前置阅读

最长上长子序列本题的 f_i 就是这篇讲的「以第 i 个元素结尾的 LIS 长度」，先看这篇的 f(i)=max{1, f(j)+1} 转移，再看本题把前驱枚举换成「值→最后出现位置」的桶

形式化题目

给定序列 $a_1, a_2, \dots, a_n$ ，选出下标 $i_1 < i_2 < \cdots < i_k$ ，使存在整数 $x$ 满足 $a_{i_j} = x + j - 1$ ，最大化 $k$ 并输出一组下标。

正解

思路

以 $i$ 结尾的最长长度只由值 $a_i - 1$ 的最优结尾决定，用哈希桶记住「值 → 最后一次出现的下标」，一次查表代替回扫， $O(n)$ 完成。

记 $f_i$ 为以位置 $i$ 结尾的最长长度。位置 $i$ 前面只能接值 $a_i - 1$ ，所以回扫所有前驱时反复回答的其实是同一个问题——值 $a_i - 1$ 的哪个位置让 $f$ 最大，于是改成用 last[v] 记值 $v$ 最后一次出现的下标， $f_i = f_{last[a_i-1]} + 1$ ，查不到时取 $1$ 。同值的 $f$ 随时间单调不减（后出现的同值元素能继承前一次的全部前驱），所以桶里只留最后一次出现就是该值上的最优结尾。再开一个 pre 数组记前驱下标，从 $f$ 最大的位置沿链回退即得一组答案。

样例 $a = [3, 3, 4, 7, 5, 6, 8]$ 逐位算得 $f = [1, 1, 2, 1, 3, 4, 2]$ ，最大在 $i = 6$ ，沿 $pre$ 回退得 $6 \to 5 \to 3 \to 2$ ，反转后即 2 3 5 6。

桶若改成「值第一次出现的位置」， $a = [1, 2, 3, 0, 1, 2, 3, 4]$ 会错答 $4$ （正确为 $5$ ），所以每次出现都要覆盖。

代码

C++ 用 unordered_map 存桶，Python 用 defaultdict 让缺键直接拿到 $-1$ 。

cpp

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
56
57
58
59
60
61
62/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-11-04 14:50
 * update_at: 2026-11-04 19:08
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 2e5 + 5;

int n;
ll a[MAXN];                   // 原序列，下标从 1 开始
int f[MAXN];                  // f[i]：以 i 结尾的最长连续递增子序列长度，最大为 n，int 够用
int pre[MAXN];                // pre[i]：拼出 f[i] 时 i 前面接的下标，-1 表示没有前驱
unordered_map<ll, int> last;  // last[v]：值 v 最后一次出现的下标；键来自输入，不必防构造攻击

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

    cin >> n;
    last.reserve(n * 2);  // 键最多 n 个，先预留桶，避免反复 rehash
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    // 前驱的值只能是 a[i] - 1，所以查一次表就够，不用回扫
    for (int i = 1; i <= n; ++i) {
        f[i] = 1;
        pre[i] = -1;
        auto it = last.find(a[i] - 1);
        if (it != last.end()) {
            f[i] = f[it->second] + 1;
            pre[i] = it->second;
        }
        last[a[i]] = i;  // 每次出现都覆盖，桶里留的是最后一次出现
    }

    int ans_pos = 1;  // 取第一个最大长度的结尾，题面允许任意一组合法答案
    for (int i = 2; i <= n; ++i) {
        if (f[i] > f[ans_pos]) {
            ans_pos = i;
        }
    }
    cout << f[ans_pos] << "\n";

    // 沿 pre 回退得到倒序的下标序列，反转后输出
    vector<int> path;
    for (int pos = ans_pos; pos != -1; pos = pre[pos]) {
        path.push_back(pos);
    }
    reverse(path.begin(), path.end());
    for (int pos : path) {
        cout << pos << " ";
    }
    cout << "\n";

    return 0;
}

python

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# 直接对每个位置往前扫前驱就是 O(n^2)，会超时。
# 记 f[i] 为以 i 结尾的最长连续递增子序列长度。
# 前驱的值必然是 a[i] - 1，所以只需要记住「值 v 最后一次出现的下标」。

import sys
from collections import defaultdict


def solve(data):
    n = next(data)
    a = [next(data) for _ in range(n)]

    last = defaultdict(lambda: -1)  # last[v] = 值 v 最后一次出现的下标
    pre = [-1] * n                  # pre[i] = 以 i 结尾时的前一个位置
    f = [1] * n                     # f[i] = 以 i 结尾的最长连续递增子序列长度

    for i in range(n):
        j = last[a[i] - 1]          # 值 a[i] - 1 最后一次出现的位置
        if j != -1:
            f[i] = f[j] + 1
            pre[i] = j
        last[a[i]] = i

    ans = max(f)
    print(ans)

    pos = f.index(ans)              # 任取一个取到最大长度的结尾
    output = []
    while pos != -1:
        output.append(pos)
        pos = pre[pos]
    print(*[p + 1 for p in output[::-1]])


if __name__ == "__main__":
    data = iter(map(int, sys.stdin.buffer.read().split()))
    solve(data)

复杂度

时间期望 $O(n)$ （每个位置一次查表、一次写表），空间 $O(n)$ （ $a$ 、 $f$ 、pre 各 $n$ 项，桶内最多 $n$ 个不同值）。值域到 $10^9$ ，桶只能用哈希表，不能开数组。

总结

前驱的值由 $a_i$ 唯一确定，把不确定的「位置」换成「值 → 最后一次出现」， $O(n^2)$ 的枚举就成了一次查表。
需要输出方案时加一个 pre 数组沿链回退，相邻两项差为定值 $d$ 时把 $a_i - 1$ 换成 $a_i - d$ 即可。
验证：四组样例 C++/Python 均通过；与 $O(n^2)$ 暴力对拍 $200$ 组、两版互拍 $120$ 组无差异； $n = 2 \cdot 10^5$ 链式数据 C++ $96$ ms / $15.1$ MiB，Python $646$ ms / $62.6$ MiB。

977F Consecutive Subsequence

题目描述

给你一个长度为 $n$ 的整数数组。

你需要从中挑出一个最长的子序列，这个子序列必须是连续递增的整数序列。换句话说，要求的序列形如 $[x, x + 1, \dots, x + k - 1]$ ，其中 $x$ 是起始整数， $k$ 是长度。

数组的子序列是通过删除若干（可以是零个）元素得到的，删除的元素不必连续，但剩下的元素顺序不变。举个例子，数组 $[5, 3, 1, 2, 4]$ 的子序列有 $[3]$ 、 $[5, 3, 1, 2, 4]$ 、 $[5, 1, 4]$ ，但 $[1, 3]$ 不是子序列。

输入格式

第一行输入一个整数 $n$ （ $1 \le n \le 2 \cdot 10^5$ ）——数组长度。第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$ （ $1 \le a_i \le 10^9$ ）——数组元素。

输出格式

第一行输出 $k$ ——满足条件的最长子序列长度。

第二行输出该最长子序列中元素在原数组中的任意下标序列。

说明

第一个样例所有合法答案（以下标序列表示）：

$[1, 3, 5, 6]$
$[2, 3, 5, 6]$

第二个样例所有合法答案：

$[1, 4]$
$[2, 5]$
$[3, 6]$

第三个样例所有合法答案：

$[1]$
$[2]$
$[3]$
$[4]$

第四个样例所有合法答案：

$[1, 2, 3, 7, 8, 9]$

输入输出样例 #1

输入 #1

text

1
27
3 3 4 7 5 6 8

输出 #1

text

1
24
2 3 5 6

输入输出样例 #2

输入 #2

text

1
26
1 3 5 2 4 6

输出 #2

text

1
22
1 4

输入输出样例 #3

输入 #3

text

1
24
10 9 8 7

输出 #3

text

1
21
1

输入输出样例 #4

输入 #4

text

1
29
6 7 8 3 4 5 9 10 11

输出 #4

text

1
26
1 2 3 7 8 9

Consecutive Subsequence

目录

形式化题目

正解

思路

代码

复杂度

总结