1. 把题面翻译成一句人话

1.1 解题前先问自己：这道题到底在考什么

洛谷 P9516 color 这道题，我第一次点进去的时候心里其实有点犯怵——题干里“颜色”两个字容易让人往图论染色、二分图、并查集合并那些方向跑，脑子里瞬间冒出一堆重活。真读完之后才发现，它考的东西非常朴素：给你一串颜色，你可以把任意一个位置改成你想要的任意颜色，问最少改几次，能让这串颜色里不存在相邻两个一样的情况。就这一句话，别被“color”这个词唬住。

我把它归到“序列上的相邻约束最小修改”这一类题里。这类题在入门到普及组难度里出现频率极高，变体也多：有的让你改成相邻不同，有的让你改成严格递增，有的让你把环也考虑进去。核心套路是同一套，只是外壳换来换去。所以这篇东西我更想讲的是一套可以复用的思考流程，P9516 color 只是这套流程的一个具体落点。

适合谁看？如果你刚学完循环和数组，能写 for 但一遇到“最少多少次”就只会暴力枚举全部方案，那这篇正对口；如果你已经能做这类题，但每次都是靠感觉猜贪心、猜对了才敢提交，那也可以往下看，我把“为什么这个贪心是对的”这件事掰开讲了一遍，顺便给了 DP 的通用版本，以后遇到环形、树上这些变体不至于卡死。

1.2 题面里真正有用的信息只有三条

很多新手读题会一行一行死磕，其实效率不高。我的习惯是先扫一遍，把有用的信息抽出来，通常不超过三条。这道题抽完是三样东西：

• 对象：一个长度为 n 的颜色序列，元素是颜色编号。
• 操作：改一个位置的颜色，一次改一个，改成什么都行，不消耗额外代价。
• 目标：让序列里任意相邻两位的颜色都不相同，且操作次数最少。

剩下的“颜色编号多大”“n 有多大”属于约束，不改变思路，但决定算法复杂度。这里必须养成习惯：先看数据范围再动手。如果 n 只有 20，你写个 2^n 的枚举也能过；如果 n 到了 1e5 甚至 1e6，那就必须往 O(n) 或者 O(n log n) 去想，任何带平方的东西都得砍掉。我见过太多人思路是对的，代码也没错，就是复杂度多了一个 n，交上去一片 TLE，然后开始怀疑人生，其实只是没看范围。

还有一个细节容易被忽略：颜色编号的取值范围和颜色种类数是两回事。题面可能给颜色编号到 1e9，但实际出现的不同颜色只有几十种。这两种情况对 DP 的影响完全不同——前者必须先做离散化，否则你开数组就要开爆；后者可以省掉这一步。这就是下一节要展开的东西。

2. 方案选型：贪心、DP 还是硬搜

2.1 先试着用贪心走一遍，看它会不会翻车

拿到“最少操作次数”这几个字，我的第一反应永远是：能不能贪。贪心的好处是代码短、跑得快、心里踏实；坏处是它经常在你以为对的时候悄悄错掉。所以我的做法是：先大胆假设一个贪心策略，然后主动去找能把它打死的反例，找不到再考虑证明。

对这道题，最自然的贪心是这样的：从左往右扫，如果当前位置和它左边那位颜色相同，就把当前位置改掉，改成什么？改成“和左边不同且和右边也不同”的某个颜色。计数加一。

这个策略的直觉很顺：每一对撞车的相邻位置，我动一次手就能拆开，而且动右边比动左边安全，因为右边还没处理完，改它不会破坏已经修好的部分。我拿几组数据手推了一下，没发现问题。但“没发现问题”不等于“没问题”，这里面藏着一个前提：你真的永远有颜色可以改成第三种吗？

这就是关键。假设整道题只允许出现两种颜色，比如只给 0 和 1，序列是0 1 1 0。中间那两个 1 撞车了，你想把第二个 1 改成和左边（1）不同、和右边（0）也不同的颜色——可选项只有 0 和 1，0 已经被右边占了，1 被左边占了，你无路可走。这时候贪心的“随手改”就失效了，你得退回去改别的位子。

提示：任何涉及“改成和邻居都不同的值”的贪心，第一件事就是数清楚可用的取值到底有几个。两个颜色的世界和三个颜色的世界，结论可能完全相反。

所以直接贪“改当前位置”是不稳的，得换思路。这就是为什么我下面先讲 DP——DP 的特点是笨，但笨得可靠，它把所有可能性都摆出来比较，不会因为你没想到某个反例而崩掉。

2.2 DP 的状态怎么定才不重不漏

设计 DP 状态，我的口诀是：状态里必须包含“影响下一步决策的全部信息”。这道题里，处理到第 i 位的时候，什么样的历史信息会影响第 i+1 位的选择？只有一个——第 i 位最终是什么颜色。前面第 i-1 位、i-2 位长什么样，已经不影响后面了。

于是状态很自然：dp[i][c]表示“前 i 位已经处理完毕，第 i 位最终颜色是 c 的最小修改次数”。

转移也不复杂。从dp[i-1][c']转到dp[i][c]，要求 c' ≠ c（相邻不同），代价是“第 i 位原本颜色是 a[i]，如果我把它定成 c，要不要花一次操作”：

dp[i][c] = min over c' != c of ( dp[i-1][c'] + (a[i] == c ? 0 : 1) )

初始化：dp[1][c] = (a[1] == c ? 0 : 1)，也就是第一位随便定什么颜色，代价只有 0 或 1。

答案：min over c of dp[n][c]。

这个状态设计的好处是不重不漏：每一种合法的最终序列，都唯一对应一条转移路径；每一条转移路径，也都对应一种合法的最终序列。你可以把 DP 想象成一张表，行是位置，列是颜色，每个格子记录“走到这里的最小花费”，最后一行取最小值就是答案。

代价那部分我要单独强调一下，因为这是新手最容易写错的地方。(a[i] == c ? 0 : 1)的意思是：如果我把第 i 位定成它原本的颜色，就不用花钱；如果我改了它，就花一块钱。它跟“第 i-1 位是什么颜色”完全无关，别把两个代价混在一起加。

2.3 复杂度核算：为什么必须先把颜色压一压

刚才那个 DP 是 O(n·k)，k 是颜色候选集的大小。问题来了，k 取多少？

如果题面里颜色编号最大能到 1e9，你不可能开一个 1e9 宽的表。但实际上序列里出现的不同颜色最多 n 种，所以真正的候选集只有 n 个。做法是离散化：把原序列里出现过的颜色收集起来排序去重，然后用“排名”代替“原值”。这一步不改变任何相邻关系——原来相等的还相等，原来不等的还不等——所以完全安全。

离散化之后 k ≤ n，复杂度变成 O(n²)。n = 1e5 的话这是 1e10，铁定超时。所以这个 DP 只能算“正确但不够快”的版本，用来对拍、用来在小数据上验证贪心是对的，非常好用；但想 AC 必须再往前一步。

这里顺便算一笔账，让“为什么要优化”这件事更具体。假设 n = 1e5，k 平均 10，那 O(n·k) 是 1e6 次操作，一秒内轻轻松松跑完；但如果 k 也到了 1e5（每个位置颜色都不一样），就是 1e10，按每秒 1e8 次简单运算估，需要 100 秒，超时十倍以上。所以判断一个算法行不行，别凭感觉，拿最坏情况的数字乘一遍，比什么都准。

注意：离散化的时候千万别用 map，除非你算过复杂度。map 的常数很大，1e5 级别可能还好，1e6 就危险了。排序 + unique + lower_bound 的写法常数小得多，而且写起来也就三行。

3. 从 DP 到 O(n) 贪心：这次真的站得住

3.1 换个视角看问题：把它切成一段一段

DP 想到这儿，我一般会问自己第二个问题：这个 DP 的形状有没有特殊结构，能不能砍掉一维？

观察一下代价函数。转移里那个min over c' != c其实很讨厌，因为要对每个 c 都排除一个 c'。但如果我们换个角度想：相邻不同的约束，本质上是在说“连续相同的一段，段内必须隔一个改一个”。

举个例子，序列是红 红 红 红。这四个位置颜色全一样，要让相邻不同，最简单的做法是保留第 1 个，改第 2 个，保留第 3 个，改第 4 个——改 2 次。四连红改 2 个，五连红改 2 个（保留 1、3、5，改 2、4），六连红改 3 个。规律很明显：长度 L 的一段连续同色，需要改 ⌊L/2⌋ 次。

那不同的同色段之间会不会互相影响？假设序列是红 红 蓝 蓝。第一段长度 2，改 1 个；第二段长度 2，改 1 个；总共 2 次。如果改的时候小心一点，把第一段的第二个红改成蓝，那它会和第二段开头的蓝撞车——但这没关系，因为你改的时候可以选第三种颜色，或者干脆把第一段改成“红 蓝 红 蓝”再把第二段改成“蓝 红 蓝 红”，交界处自然就错开了。只要颜色种类不止一种、段与段之间本来颜色就不同，交界处天然就是不同的。

所以结论是：答案等于所有极大同色段的 ⌊长度/2⌋ 之和。这个计算一次遍历就能完成，复杂度 O(n)，而且完全不用管颜色编号多大，连离散化都省了。代码大概长这样：

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; ++i) cin >> a[i]; long long ans = 0; int i = 0; while (i < n) { int j = i; while (j < n && a[j] == a[i]) ++j; // 找出极大同色段的右端点 ans += (j - i) / 2; // 长度 L 贡献 L/2 向下取整 i = j; // 从下一段继续 } cout << ans << "\n"; return 0; }

十几行，跑 1e6 的数据也是几毫秒的事。注意ans要用 long long，虽然单段贡献不会太大，但段数多了累加起来可能超过 int 范围，这种低级错误在赛场上非常致命，写完先自己扫一眼变量类型。

3.2 为什么这个贪心一定对：把一段的最优性锁死

代码短不代表不用证明。我在比赛里见过太多“贪心瞎写，样例过了就交”然后 WA 一片的场面。这个结论为什么成立，可以用两种方式说服自己。

第一种是下界论证。看任意一个长度为 L 的极大同色段，段内相邻位置本来颜色相同。要让它们最终都不同，段内 L-1 条相邻边里，每条边至少有一端被改过（否则这条边两端都保持原色，仍然相同）。这就变成了一个“选点覆盖所有边”的问题：一条长度为 L 的链，L-1 条边，最少要选几个点才能覆盖全部边？答案是 ⌊L/2⌋——一条边最多被两个端点覆盖，所以要覆盖 L-1 条边至少需要 ⌈(L-1)/2⌉ = ⌊L/2⌋ 个点。这条下界是硬的，任何方案都躲不开。

第二种是构造上界。就按“保留第 1、3、5…个，改第 2、4、6…个”的方式改，正好用掉 ⌊L/2⌋ 次，达到下界。上下界一夹，最优值就锁死了。

至于段与段之间，因为它们是“极大”同色段，相邻两段的颜色必然不同，所以交界处天然满足约束，不需要额外花钱。这两条合起来，答案就是 Σ⌊L/2⌋，一个字符都不用多。

提示：写题解或者跟人讲思路的时候，能同时说清楚“为什么不能更少”和“为什么这么能做到”，才算真懂了。只说“我觉得这样最优”，面试官或者队友一句话就能问倒你。

3.3 边界情况：三个最容易漏的地方

再稳的算法也会在边界上翻车，我把这道题我踩过的坑列一下。

n = 1 的情况。只有一个位置，没有相邻关系，答案必须是 0。如果你写的循环从 1 开始比较，或者用“前后都看”的写法，很容易莫名其妙输出 1 或者越界。上面那段代码用的是“找段”的方式，n=1 时只会找到一个长度 1 的段，贡献 0，天然正确。

全序列同色。蓝 蓝 蓝 蓝 蓝，一段长度 5，答案 2。手算一下：保留第 1、3、5 个，改第 2、4 个，确实 2 次。这里有个心理误区——有人觉得“颜色种类只有一种，那不是无解吗”。不是的，题目允许你把颜色改成任意值，改完之后颜色种类自然就丰富了，所以永远不需要担心“没颜色可用”。只有一种颜色反而更简单，因为全程都在一个段里。

输入读不进来。多组数据或者文件末尾判断没写好的时候，cin >> n会失败，然后vector<int> a(n)里 n 是个随机值，直接 RE 或者 MLE。加一句if (!(cin >> n)) return 0;兜底，成本几乎为零。

4. 换个壳子：环形版本和树上版本怎么迁移

4.1 首尾相接之后，问题难在哪

很多题目会在“相邻不同”的基础上加一句：首尾也算相邻。这时候序列变成一个环，红 红 蓝这种数据就出问题了——本来首尾是红和蓝，不同；但如果你按线性思路去改，可能改完变成红 蓝 蓝，首尾（红和蓝）没问题但中间撞了，或者改成蓝 红 蓝虽然内部对了，首尾又是蓝和蓝相撞。

环的关键麻烦在于：第 1 位和第 n 位的颜色是互相牵制的，而线性 DP 恰好不知道第 n 位最后是什么颜色。

处理手法有两类。一类是破环：枚举第 1 位最终定成什么颜色（或者只枚举“改”与“不改”两种状态），把环拆成两条链，分别跑 DP 取小。另一类是直接改 DP：状态里同时记住第 1 位的最终颜色和第 i 位的最终颜色，最后加一条“首尾不同”的检查。前一种代码简单、常数小，后一种状态大一倍但思路统一。

拿线性贪心的结论去套环要格外小心。比如红 红 红这个环，长度 3，按线性算是 ⌊3/2⌋ = 1，改中间那个就变成红 蓝 红，首尾都是红，撞了，不行；得改 2 次，改成红 蓝 蓝？也不行。正确的是红 蓝 红不成立，红 蓝 蓝首尾撞，那只能蓝 红 蓝或红 蓝 …——三连环要改 2 个才够。所以环版本的答案是另一套公式，不能直接复用线性的。

4.2 树上染色：约束从一条线变成一张网

再往外延伸一步，如果给定的不是序列而是一棵树，要求任意相邻（有边相连）的两个点颜色不同，改一个点的颜色算一次操作，最少改几次？

这时候线性贪心彻底失效了，因为一个点可能同时牵着好几个邻居，改它一个会影响一大片。标准的做法是树形 DP：dp[u][c]表示以 u 为根的子树处理完毕、u 最终颜色是 c 的最小代价。转移的时候把所有儿子 v 的min over c' != c of dp[v][c']加起来，再加上 u 自己改色的代价。

这个式子跟线性 DP 长得几乎一样，只是“前一个”变成了“所有儿子”。这也说明了一件事：DP 的通用性远强于贪心。贪心是特化，只对特定结构成立；DP 是通法，结构变复杂了它照样能用，代价只是复杂度上升。所以我一直建议新手先把 DP 写熟，贪心当优化技巧来用，而不是反过来。

如果颜色种类不止两个，树形 DP 里那个“排除 c 的最小值”还可以用“记录最小值和次小值”的方式优化掉一层循环，从 O(n·k²) 降到 O(n·k)。这个技巧在线性 DP 里我前面也用过（维护 best1、best2），套路完全一样，值得单独记一笔。

5. 调试实录：那些让你 WA 得莫名其妙的地方

5.1 常见错误速查表

我把这道题以及同类型题里反复出现的错误整理成了表，交题前对着扫一遍，能省下大量对拍时间。

这张表里我最想强调第一行和第三行。前者是逻辑正确性问题，后者是工程正确性问题，两个都得治。

5.2 对拍：最朴素也最有效的验证手段

写完贪心之后我心里其实还是不踏实，因为“我觉得它对”这件事本身不构成证据。于是我写了个暴力枚举版本用来对拍。暴力的思路很简单：n 很小的时候（比如不超过 15），枚举每个位置改或不改，再检查剩下的是否还有相邻相同，全部合法方案里取改得最少的。虽然慢，但它逻辑直白，几乎不可能写错。

对拍脚本的骨架就三行：随机生成一组小数据，两边各跑一次，比较输出。一旦发现不一致，立刻把数据打印出来人工分析。我用这套方法在 n=8、颜色数=3 的范围内跑了上万组随机数据，全对，才敢确信那个 ⌊L/2⌋ 的结论没有隐藏反例。

提示：对拍不要只跑随机数据。随机数据往往很“温和”，构造不出极端情况。要额外手写几组：全同色、两色交替、只有一种颜色、颜色数等于 2 且长度是奇数——这些才是杀贪心的主力。

另外一个提高对拍效率的小技巧：把暴力版本和正确版本写在同一份代码里，用#ifdef或者一个编译期常量切换，这样不用维护两个文件，改一处就行。这个习惯看起来麻烦，实际上每次省下来的时间远超那几分钟的搭建成本。

5.3 代码风格上的几点个人习惯

说几条跟题目本身无关但确实影响长期效率的习惯。

第一，变量名别偷懒。a、b、c这种名字在 20 行的程序里没问题，但只要逻辑稍微复杂一点，你自己两天后回来看就得重新推一遍。我一般用color表示颜色数组，len表示段长，ans表示答案，一眼就知道是什么。

第二，把“找段”和“算贡献”分成两步写。上面那段代码里，我用一个 while 找出整段，再单独一行算贡献，逻辑很清晰。如果硬写成一个 for 加一堆 if，出问题时你根本不知道是段边界错了还是贡献算错了。

第三，每次改完代码，先自己跑一次小样例，别急着提交。提交次数在某些评测平台上是有记录的，频繁无意义提交不仅浪费时间，也容易让你养成“反正可以重交”的惰性心态。

6. 这类题还能往哪儿扩展

6.1 换个目标：从“相邻不同”到“相邻递增”

同样的骨架，如果把“相邻不同”改成“相邻严格递增”，问题的性质就变了。修改一个位置的值，代价为 1，问最少改几次变成严格递增序列。这是经典的 LIS 变形，答案往往是 n 减去某个最长的“可保留子序列”长度。思路的迁移点在于：找出哪些位置可以原样保留，剩下的都改，从“改哪些”转成“留哪些”，视角一换，问题就好解了。

这个视角转换非常重要。我遇到“最小修改”类问题时，第一反应永远是先想“最大保留”。因为保留的位置越多，改的位置越少，两者是互补的。“保留”这件事往往更容易刻画——它只需要满足原序列内部的相对关系，不用管改成什么。

6.2 加上权重：每次操作不再是 1

再复杂一点，如果每个位置改一次的代价不一样（比如第 i 位改一次花 w_i），那“改哪些”就不能只看段长了，得权衡哪边便宜。这时候线性的 ⌊L/2⌋ 公式直接失效，必须老老实实做 DP，按“改或不改”两种状态转移。

这其实揭示了一个规律：当所有操作代价相等时，问题往往退化成计数或贪心；一旦代价不等，就得回到 DP。这个判断标准我在很多题上都验证过，非常好用。看到“代价相同”就大胆去贪，看到“代价不同”就先老老实实列状态。

6.3 真实场景里的“相邻去重”

跳出题目，这套逻辑在工程里其实到处都是。比如生成一份排班表，要求相邻两天的值班人不同；比如渲染一条色带，要求相邻两格颜色有区分度；比如做数据脱敏，要求相邻记录不能出现相同的标识。本质都是“在一个序列上做最小改动，让相邻元素满足某种不相等关系”。

我印象比较深的是一个做报表导出的场景：连续多行某个字段值完全一样时，视觉上会糊成一片，需要隔行填个占位符。当时的处理逻辑就是把连续相同的行归成一段，每隔一行处理，跟这道题的贪心一模一样。写的时候我甚至没意识到这是同一道题，直到后来刷到 P9516 才反应过来——很多算法题不是凭空造的，它们就是某个人在某个下午遇到的真实问题的抽象。想通这一层之后，我刷题的心态变了不少，不再只是“为了过题”，而是真的在攒工具箱。

7. 我个人的一点体会

这类题我前后做过十几道，最大的教训是：别急着写代码，先在纸上把“答案是什么形状”画出来。P9516 color 我第一遍是直接开写 DP 的，写完发现 n 大了跑不动；第二遍才回头去观察结构，发现原来是分段计数。如果一开始就拿几组小数据手推一遍，这个规律可能五分钟就能看出来，能省掉一大圈弯路。

手推这件事听着笨，但它是最快的理解方式。我现在遇到任何“最少多少次”的题，都会先在纸上列五六组数据，自己算一遍答案，看看答案跟输入之间有没有明显的对应关系——段数、长度、极值、奇偶性，这些线索往往就在手推的过程中冒出来。等规律有了，再去想证明，最后才动手写代码。顺序反过来，效率会低很多。