企业官网建设流程全解析

“信息学奥赛一本通高手训练1680：序列”——看到这个编号，很多刷过《一本通》的OIer应该都会心一笑。高手训练部分的题，和基础篇完全是两个世界。基础篇教你怎么写代码，高手训练教你怎么想问题。而所有以“序列”为名的题目，几乎都是思维含量最重的那一类：它们从不直接告诉你“这题考LIS”，而是把最长上升子序列、最大子段和、区间合并这些经典模型包上一层又一层的壳，等你自己去扒开。

这篇文章我不打算只盯着1680这一道题去“报答案”，那没有意义。更值钱的是把“序列”这类题的底层逻辑彻底捋清楚。无论你是在备战NOIP/CSP，还是单纯想提升算法思维，这篇文章都能给你一套可复用的解题框架。我会从题型定位讲到核心算法模板，从暴力优化讲到变式题坑点，最后再分享一些只有实操过才会懂的调试心得。

1. 1680的题型定位：为什么“序列”二字值得警惕

1.1 高手训练系列的真实难度曲线

《信息学奥赛一本通》的“高手训练”部分，定位非常明确：它假设你已经掌握了基础语法、常见数据结构和经典DP模型，然后开始给你上强度。这里的题平均难度可以参照NOIP提高组T2到T3的区间，有些甚至直接对标省选入门。

说句实在话，我见过太多人在基础篇把LIS模板背得滚瓜烂熟，一到高手训练的序列题就懵。原因很简单：基础篇的LIS题，数组下标从1到n，输入一个序列，叫你求最长上升子序列长度，完事。高手训练的序列题，同样的LIS内核，但它会给你塞进“字典序最小”“必须包含某个位置”“带权值”这些附加条件，让你连状态怎么设都拿不准。

所以当你拿到“1680：序列”这种题名极简、毫无提示的题目时，第一反应不应该是“这题简单”，而应该是“这题考的是序列的哪张脸”。这是高手训练序列题的第一课：题面越是简短，隐藏信息量越大。

1.2 从热搜词看序列题的考查版图

我特意看了一下围绕这道题的热搜词，非常有意思。“最长公共子序列”“最大连续子序列”“不同的子序列”“无序数组最长连续递增子序列”——这些词几乎把序列类题目的主要考点全点了一遍。

结合这些年我带竞赛的经验，序列题在OI中的考查范围基本可以划分为四个梯队：

1680这道题到底落在哪个梯队，说实话只看标题谁都无法百分之百确定——这恰恰是竞赛题最真实的地方。但正因为如此，把这四个梯队的核心算法全部打通，才是应对一切“序列”题的王道。接下来我按实战优先级逐个拆。

2. 序列题的四块基石：LIS、LCS、最大子段和、最长连续递增子序列

2.1 最长上升子序列（LIS）：从O(n²)到O(n log n)的进化

最长上升子序列是序列题的内功心法。它的基础方程我简单提一嘴：设dp[i]表示以a[i]结尾的最长上升子序列长度，转移时枚举j < i，若a[j] < a[i]，则dp[i] = max(dp[i], dp[j] + 1)。这个是O(n²)的，n ≤ 5000还能扛，n一旦到10⁵直接暴毙。

高手的做法是用一个辅助数组维护“当前长度为len的上升子序列中，末尾元素的最小值”。这个数组是单调递增的，所以可以用二分查找。判断逻辑是：新来的元素x，在辅助数组里找到第一个大于等于x的位置pos，如果pos不存在，说明x可以接在所有已知序列末尾，序列长度加一；否则用x替换掉辅助数组里那个位置的元素。

vector<int> lis; for (int x : a) { auto it = lower_bound(lis.begin(), lis.end(), x); if (it == lis.end()) lis.push_back(x); else *it = x; } // 最终 lis.size() 就是最长上升子序列长度

注意，这种写法得到的lis数组本身不一定是真实的最长上升子序列，它只是维护了一个“最有潜力”的候选集合。如果要输出具体序列，还得额外维护每个位置的前驱，或者用pos数组记录每个长度对应的序列尾部位置，再从后往前倒推。这是LIS一个非常经典的坑：很多人以为lis数组就是答案序列，一提交就错。

2.2 最长公共子序列（LCS）：二维DP与空间压缩

LCS的方程更基础：设dp[i][j]表示a的前i个字符和b的前j个字符的最长公共子序列长度。转移如下：

if (a[i] == b[j]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

O(n²)的时间复杂度、O(n²)的空间复杂度，让LCS在高n范围下很被动。常见的优化是滚动数组：因为dp[i][j]只依赖于dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]三个状态，也就是只依赖上一行和当前行的数据，所以空间可以压到O(n)。

我在实际写滚动数组的时候吃了不少亏，这里必须提醒一下：dp[i-1][j-1]这个值在滚动数组里对应的是“上一行的上一列”，如果你只开一个一维数组，更新dp[j]的时候它已经被覆盖了。正确做法是先用临时变量保存左上角的值，或者在更新前把前一列的旧值备份。一字之差，全盘皆输。

2.3 最大子段和（Kadane算法）：状态设计为什么是“以i结尾”

最大连续子序列的和，这是序列题里统计频率最高的模板之一，网上能搜到的相关实现不下几十种。但很多人只是背代码，没搞懂为什么状态要设计成“以i结尾”。

设cur表示以当前元素结尾的最大子段和，ans表示全局答案。每读入一个x：

cur = max(x, cur + x); ans = max(ans, cur);

cur + x的意思是：把x接到之前选中的连续段后面。但万一前面的那段总和是负数，接上去只会拖累x，所以直接放弃之前的段，从x重新开始——这就是max(x, cur + x)这一行的全部含义。

这个设计非常关键，因为“以i结尾”保证了连续性和子段定义的一致性。如果你设的是“前i个元素中最大子段和”，反而没法直接写转移——因为你不知道上一个选中的连续段末尾在哪，也就无法判断x能不能接上去。一个看似微小的状态定义差异，决定了整个DP方程能否成立。这也是竞赛思维和死背模板的本质区别。

2.4 最长连续递增子序列：双指针与贪心扫描

这里要和LIS做一个明确的区分：LIS不要求元素在原序列中连续，而“最长连续递增子序列”要求的是“连续的一段”且“段内严格递增”。热搜词里“给定一个无序数组，找出最长连续递增子序列的长度”，考的就是这个。

其实这个题不需要DP，一趟O(n)的贪心扫描就够了：

int ans = 1, len = 1; for (int i = 1; i < n; i++) { if (a[i] > a[i-1]) len++; else len = 1; ans = max(ans, len); }

核心逻辑是：如果当前位置比前一个位置大，说明递增关系还在延续，长度加一；一旦断了，就重置为1，重新开始累积。这里只用一个变量就能完成统计，连数组都不需要额外的辅助空间。很多人在写这个题时会不自觉把它和LIS搞混，写着写着就开始用lower_bound，完全没必要。先看清楚题目是“连续”还是“不连续”，是“严格递增”还是“非严格递增”，这决定了你调用哪套算法。

3. 序列题优化思维的完整推导链

3.1 暴力为什么不行：复杂度分析的直觉判断

我以前带集训队时，让学生遇到序列题先做一件事：算暴力复杂度，再读一遍数据范围。n ≤ 20就直接搜；n ≤ 5000就用O(n²)的DP；n ≤ 10⁵就得考虑O(n log n)甚至O(n)的解法。这听起来像个简单的判断流程，但很多人写题时根本没有这个意识，上来就无脑套代码模板。

1680这类高手训练题的数据范围通常不会手软。如果它是求最值类序列题，n大概率在10⁵上下；如果是计数类，那对取模运算的考察也会一并上来。看懂数据范围，其实是在“偷听”出题人给你传递的信息：他允许你用哪种复杂度的算法。这是OI实战里最基础但最容易被忽略的一步。

3.2 从“选或不选”到“以谁结尾”：状态设计的转折点

新手学DP时，习惯用“前i个元素，选或者不选第i个”的角度思考。这种状态设计在处理背包问题时非常好用，但放到序列题里经常会碰壁。原因是：很多序列问题的约束（尤其是“连续”和“递增”这类性质）与“最后一个元素是谁”直接相关，而与“前i个元素选了多少个”关系不大。

LIS之所以要设成“以a[i]结尾”，是因为上升子序列的扩展只取决于当前最后一个元素的值——如果你只知道“前i个元素的最长上升子序列长度”，却不知道那个子序列末尾是多少，那面对一个新元素时，你根本不知道能不能接上去。所以，序列DP的一个核心转折点，就是学会把“末尾状态”纳入DP维度。一旦跨过这道坎，很多题的转移方程就会变得理所当然。

3.3 单调性与二分：当DP优化需要“降维打击”

LIS的O(n log n)做法之所以成立，核心在于辅助数组的单调性。而“单调”这个词，在序列题里几乎等同于“可优化”的暗号。看到“元素越大越容易接在后面”这种性质时，就要条件反射地想到单调栈、单调队列、二分维护这些工具。

举一个具体场景：假设你在维护一个数组，它存的是“长度为len的上升子序列中最小的末尾值”，那么这个数组从左到右一定是严格递增的。为什么？因为如果长度为len的最优末尾值已经大于长度为len+1的最优末尾值了，那长度len+1的那个子序列的前len个元素，显然可以当作一个末尾值更小的长度为len的上升子序列——矛盾。所以这个数组天然有序，二分才派得上用场。理解了这个单调性的来源，你就不会把lower_bound和upper_bound用错，也不会在等号边界上翻车。

4. 序列变式题的两个命门：子序列计数与区间合并

4.1 “不同的子序列”计数：去重的艺术

热搜词里“不同的子序列”出现了，这也是序列题里非常经典的一类变式。题目大概是：给定一个字符串s，求s中不同的子序列个数。注意“不同”两个字——子序列可以不连续，但重复的只算一次。

这道题有个很优雅的DP做法，设dp[i]表示前i个字符中不同的子序列总数。转移时，考虑第i个字符s[i]加到末尾后新增的子序列：原来所有的子序列后面都可以拼上这个字符，就会产生dp[i-1]个新子序列；再加上s[i]自己单独作为一个子序列，总共新增dp[i-1]个。但问题来了，如果s[i]之前出现过，那有些子序列末尾本来就有一个相同的字符，拼上这个字符并不会形成新的子序列，会产生重复。

去重的技巧是：记录每个字符最后一次出现的位置last[ch]，那么新增量就不是dp[i-1]，而是dp[i-1] - dp[last[ch]-1]。

for (int i = 1; i <= n; i++) { dp[i] = (dp[i-1] * 2) % MOD; if (last[s[i]] != 0) dp[i] = (dp[i] - dp[last[s[i]] - 1] + MOD) % MOD; last[s[i]] = i; }

这个减法的含义很精妙：前缀到last[ch]位置为止的子序列，在last[ch]处拼ch得到的结果，和在第i处拼ch得到的结果完全相同。仔细体会这个“位置重叠导致重复”的逻辑，它是子序列计数题里所有去重手法的源头。把这个题想明白了，很多组合计数题你都会有感觉。

4.2 区间合并的DFS思路：当序列题套上树的壳

还有些“序列题”表面上看着根本不是序列——给你一个序列和一堆操作，每次合并相邻两个数，代价是它们的和，求最小总代价。这就是经典的区间DP，石子合并问题。它披着序列的外衣，但内里在考区间划分。

区间DP的枚举套路非常固定：先枚举区间长度len，再枚举左端点l，右端点r = l + len - 1，最后枚举中间的划分点k。复杂度O(n³)。这里的“先枚举长度”是有原因的：因为长区间的答案依赖短区间的答案，只有把短区间的dp值全部算完，长区间才能顺利转移。我见过不少人直接枚举l和r导致答案全错，就是因为忽略了区间DP的依赖顺序。

当然到了更进阶的版本，比如支持循环序列合并（把序列首尾相接），那就需要把数组扩成两倍长度再做区间DP。这是“序列题加一层壳”的标准操作：环怎么办？破环成链，长度翻倍，答案在长度为n的区间里取最值。这类题型的识别特征是“合并”“分割”“选择区间”这些关键词。

4.3 序列题与数据结构的联姻：从“傻DP”到“聪明DP”

真正能放进“高手训练”的序列题，往往不只是DP，而是DP加数据结构优化。比如状态转移里需要快速查询前i个位置中满足某条件的最优dp值，这时候线段树、树状数组就派上了用场。

举个最常见的例子：带权LIS，每个元素有一个权值，要求最长上升子序列的权值和最大。朴素的O(n²)很容易写，但如果n到10⁵，就必须要用树状数组维护“以某值域为末尾的最大权值和”，然后对每个元素查询小于它的最大值加自身权值。这本质上是把LIS的二分优化替代成了一种更通用的“值域查询”手段。理解了这层关系，你会突然明白：树状数组在序列题里不只是用来求逆序对的，它更大的价值在于给DP的转移过程做加速。

5. 序列题易错点排查与调试实战

5.1 初始化陷阱：dp数组的“0”和“1”之争

序列题的DP初始化是个重灾区，而且错误极其隐蔽。以LIS为例，每个位置至少自己可以构成一个长度为1的子序列，所以dp[i]一定要初始化为1。但最大子段和就不一样，你初始化cur = 0还是cur = a[0]，结果可能直接差一个量级——尤其当输入全是负数的时候。

我自己的习惯是：写任何序列DP之前，先在草稿纸上画出“最小子问题是什么”。如果最小子问题是“只考虑一个元素”，那初始值必然跟这个元素相关，要么是1（长度类），要么是a[i]（和值类），而不能是无脑的0。很多人对拍不出错、一交就WA，大多数就是栽在这个看似微不足道的初始化上。

5.2 调试“序列题”的神器：对拍与随机数据生成

刷序列题时，最痛苦的莫过于“样例过了，提交错了”，而且你根本不知道错在哪组数据。我的建议是：不要省对拍的时间。写一个暴力的O(n²)或者深搜版本来对拍，生成随机小数据跑，一旦结果不一致就用小数据来定位。序列题的好处是——数据规模可以缩得非常小，比如n = 5，你可以手动枚举所有情况去验证状态定义是否一致。

对拍脚本的核心其实也就几行：用rand()生成随机序列，调用暴力程序和优化程序各跑一遍，然后比对输出。一旦比对失败，把输入数据和两组输出打印出来，基本就能一眼看出是转移方程写错了还是边界没处理好。这个小习惯能让你少做很多无效调试。

5.3 性能瓶颈与读入优化

“高手训练”的题，很多数据规模都在10⁵甚至10⁶级别。此时cin不关同步流基本就等着卡常卡到怀疑人生。序列题因为会频繁读入、频繁更新状态，输入输出优化的影响非常明显。

ios::sync_with_stdio(false); cin.tie(nullptr);

如果还不够，就干脆用getchar手写快读。再有就是：能开O(n log n)就不要犹豫，有些题就是为了卡O(n²)而设计的。多写一行二分，比事后花一整晚想怎么优化要划算得多。

6. 从1680往外走：序列题的思维模式迁移

这道“1680：序列”究竟给你的最大收获是什么？我认为不是某一份AC代码，而是一整套识别—拆解—解决序列问题的流程。之后再看到任何“序列”题，我建议你按这个顺序问自己：

1. 要求连续还是可以不连续？——这决定了扫描、双指针还是DP登场。
2. 是求最值还是求方案数？——求最值优先考虑贪心或DP，求方案数要立刻想到去重。
3. 数据范围允许什么复杂度？——这直接划定算法边界。
4. 有没有“单调性”“可二分性”可以利用？——有，就数据结构优化；没有，就朴素DP。

我个人在实际带题和做题过程中的体会是：序列题是整个OI知识体系里性价比最高的一类题。它们代码量普遍不大，但思维的密集程度极高。你把LIS、LCS、最大子段和、子序列计数这几块基石打磨得足够扎实，“1680：序列”这种题无论它套的是哪张皮，你都能在30分钟内找到切入口。接下来就是多刷、多对拍、多总结，把这些思维内化成你的本能反应。