第一次在OJ习题列表里看到“21行代码AC”这种描述时我第一反应是又遇到标题党了。结果自己把习题3-7 DNA序列(某OJ 1368)做了一遍倒吸一口气这道题确实只需要二十来行代码但真正想清楚它需要跨过三个坎——理解共识序列的目标函数、想明白按列贪心为什么是对的、处理字典序并列时的选择顺序。这篇文章不打算只贴代码。我会把从读题到AC的完整思路链写出来包括为什么这样设计数据结构、为什么“出现次数最多”不等于“答案正确”、以及我在实际调试中踩过的几个坑。如果你正在刷题或者想找一道“短代码但高信息量”的题练手这篇应该能帮你省不少时间。1. 先看题目到底在算什么共识序列与Hamming距离1.1 题意拆开其实只有一句话题目给n条等长的DNA序列每条长度都是m字符只允许A、C、G、T。要求构造一条长度同样为m的DNA序列使得这条序列与给定n条序列的Hamming距离总和最小如果存在多条满足条件的序列输出字典序最小的那条。这句话里藏着两个输出一个是构造出来的共识序列字符串另一个是那个最小距离总和。很多人做着做着就忘了第二行输出只把字符串打印出来样例能过一提交就WA这种错误我见过太多次了。所谓“共识序列”听起来很高大上本质就是“在每一列上选一个最能代表大家意见的字母”。n条序列排成一个n行m列的矩阵每一列有n个字符我们逐列决定最终答案串这一列填什么。矩阵的每一格都是独立的没有任何跨列约束这一点是整个题目的突破口。1.2 Hamming距离数一数有几个位置不一样Hamming距离的定义很简单两个等长字符串从左到右逐位比较有多少个位置的字符不同距离就是多少。比如AAGC和AACT前两位都是A、A第三位G和C不同第四位C和T不同所以距离是2。放在这道题里我们要构造的答案串和某一条给定序列的距离就是对每一列判断“这一列我选的字符是否和这条序列在该列的字符相同”相同加0不同加1。最终答案串与全部n条序列的总距离就是把n个距离加起来。于是总距离有一个非常直观的等价写法对于某一列如果我选了某个字符X那么这一列对总距离的贡献就是n减去这一列字符X出现的次数。因为这一列一共有n个位置选X后只有那些本来就等于X的位置不会产生差异其余位置全都要计1。1.3 先拿一组小数据把目标函数跑一遍我建议在动手写代码前先在纸上画一个3行4列的矩阵第1条AAG T第2条AGC T第3条ACG T逐列统计第0列A、A、AA出现3次第1列A、G、C三个字符各出现1次第2列G、C、GG出现2次第3列T、T、TT出现3次。如果只看“出现次数最多”那第1列就麻烦了A、C、G并列第一选谁都行但题目要求字典序最小所以这列应该选A。最终共识序列就是AAGT。验证一下总距离第0列选An-cnt0第1列选A和第一行相同和另外两行不同贡献2第2列选G和第一、第三行相同贡献1第3列选T贡献0。总距离3。这个例子同时暴露了题目的核心每一列的选择逻辑不是“谁出现最多就无脑选谁”而是“在出现次数最多的候选字符里挑字典序最小的”。顺序不能反。2. 为什么按列统计就是最优解贪心的两个层次2.1 每一列都是独立的选择题很多人看到“求全局距离最小”会本能地想是不是要动态规划是不是要搜索会不会有后效性答案是否定的。总距离的定义是逐位累加矩阵的每一列互不干扰。我在第0列选了什么完全不影响第1列的Hamming距离贡献。这是因为总距离可以拆成m个独立求和项每一项只依赖当前列的选中字符和当前列的n个输入字符。既然某一列选什么字符只会影响这一列的贡献不会波及其他列那么“全局最小”就退化成“每一列分别最小”。这就把一道看起来像组合优化的问题变成m个互不相干的小投票问题。这里用生活类比更好理解班级要选班服颜色每人投了A/C/G/T四种颜色一共m轮的票但每一轮投票结果只决定那一周的周服颜色周与周之间没有任何关联。那每一周当然直接选当周得票最高的颜色不可能会为了下周的票而去委屈这一周。2.2 局部最优叠加成全局最优的证明思路严格一点说假设最终答案串为S那么S的总距离可以写成sum_{j0}^{m-1} (n - cnt[j][S[j]])其中cnt[j][c]表示第j列字符c出现的次数。我们发现这个和式里第j项只取决于S在第j列的取值和其他任何一列都无关。所以最小化和式等价于对每一列j独立最小化这一项。对于第j列想让n - cnt[j][c]最小就是让cnt[j][c]最大。这一步的选择是局部最优又因为和式可分离局部最优拼起来就是全局最优。这就是整道题贪心正确性的全部证明不需要什么高深理论。如果你有强迫症还可以用反证法走一遍假设某个全局最小解里某一列没有选该列出现次数最多的字符那么换成出现次数最多的字符这一列贡献变小其他列不变总距离会更小矛盾。所以任何全局最优解每一列都必须选出现次数最多的字符之一。2.3 “字典序最小”不是“优先选字典序小的字符”这是整道题最容易被带偏的地方。题目要求是先保证总距离最小再在这个前提下输出字典序最小的串。于是每一列的逻辑顺序是第一步找出这一列出现次数最多的字符集合第二步如果这个集合里只有一个字符就选它第三步如果集合里有多个字符选ASCII顺序最小的那个。注意不是“字典序最小的字符只要出现次数够高就优先”也不是“直接把字符按ACGT排序后取出现次数最大的”。比如某一列A出现了3次、T出现了4次你绝不能因为A字典序小就选A那样距离会变大直接违反第一优先级。只有在并列最高的时候字典序才参与决策。“字典序”是针对整个答案串的比较从左到右一位一位看。我们逐列从第0列开始决策每一列在“不影响距离最优”的前提下尽量选小字符最终得到的就是字典序最小的最优串。这和常规字典序贪心完全一致。3. 21行代码拆开看数据结构与核心循环3.1 为什么不用枚举所有可能的DNA序列看到“求最优序列”第一反应可能是枚举所有4^m种长度m的ACGT组合再逐一计算距离取最优。这在m很小的时候可以但题目里m只要到504的50次方就是天文数字枚举直接爆炸。所以正确姿势是反向思考既然每一列独立我们根本不需要“枚举答案串”只需要逐列统计输入矩阵中每一列各字符的出现次数。存储方面最简单的方式就是开一个二维字符数组把n行m列的矩阵整个读进来。这题数据规模很小二维数组完全够用。如果你想把代码压得更短甚至可以不存矩阵边读边统计每读一行就把它每个位置的字符累加到对应的列计数器里。这样内存从O(n*m)降到O(m)代码行数也基本不变。我下面给的版本用二维数组因为更直观适合用来理解算法。3.2 字符映射表让计数代码从四份变成一份新手最容易写出的代码是每一列分别统计a_count、c_count、g_count、t_count四个变量再写四个if比较大小。这样不是不能AC但代码又长又容易抄错。更简洁的做法是建一个字符到下标0~3的映射A - 0C - 1G - 2T - 3这个映射顺序不是随便定的它正好是字典序从小到大A C G T。后面处理并列时会非常方便只要在遍历计数器时用“严格大于”更新最优下标相等时保持不动就自然选到了字典序最小的字符。3.3 一份可压缩到21行的C/C实现下面这段代码去掉空行和花括号压到21行左右完全没问题。为了可读性我保留了一点空格完整逻辑如下#include bits/stdc.h using namespace std; int T, n, m; int cnt[4]; char dna[55][1005], ans[1005]; int idx[128]; char letter[4] {A, C, G, T}; int main() { scanf(%d, T); idx[A] 0; idx[C] 1; idx[G] 2; idx[T] 3; while (T--) { scanf(%d%d, n, m); for (int i 0; i n; i) scanf(%s, dna[i]); int dist 0; for (int j 0; j m; j) { memset(cnt, 0, sizeof(cnt)); for (int i 0; i n; i) cnt[idx[dna[i][j]]]; int best 0; for (int k 1; k 4; k) if (cnt[k] cnt[best]) best k; ans[j] letter[best]; dist n - cnt[best]; } ans[m] \0; printf(%s\n%d\n, ans, dist); } return 0; }核心循环只有两部分外层for枚举列内层for统计这列的四个计数然后找best并累加距离。如果非要精简我可以把scanf输入、字符映射表初始化放到主循环里压缩行数但那种代码只适合表演不适合学习。上面这个版本该有的结构都有一行不多一行不少。3.4 距离累加为什么是n减去最大次数每一列共有n个字符。选best作为答案串这一列的字符后这一列里有cnt[best]个位置原本就是best它们不会产生差异剩下n-cnt[best]个位置和best不同每个位置贡献1个Hamming距离。所以在统计完cnt数组并确定best后一句dist n - cnt[best]就把这一列的总贡献加上了。整个循环结束后dist就是答案串与所有输入序列的Hamming距离总和。这里不需要再回头逐条比对因为列内计数已经包含了全部信息。4. 实测中最容易翻车的三个细节4.1 并列最大时的选择顺序严格大于而不是大于等于我最初写找best时用的是“如果cnt[k] cnt[best]就让best k”结果样例都不对。因为初始best0指向A当某一列A、C、G各出现1次时遍历到C时cnt[1] cnt[0]成立best变成1遍历到G时又变成2。最后一列如果有T也并列best就变成3最终选了T而不是题目要求的字典序最小字符A。正确写法是只有当cnt[k]大于cnt[best]时才更新best。这样在多个字符并列最大时best始终停留在更早也就是字典序更小的下标上。一个小符号决定生死的典型例子值得记下来。另外字符映射表的顺序必须和字典序一致。如果把T放在下标0A放在下标3即使你用严格大于并列时也会选到T。映射表顺序和比较符号是配套的改一个就得改另一个。4.2 输入输出的隐藏格式问题题目输入第一行是测试组数T接下来每组先给n和m再给n行长度为m的DNA序列。用scanf(%s)读取字符串时它会自动跳过空白字符不会把换行符吃进来所以即使样例排版很乱也不怕。但要注意一个习惯问题如果你在代码里用了cin又同时用printf输出最好在开头写上ios::sync_with_stdio(false)并保持全程用cin/cout或者干脆全部用scanf/printf。混用且关掉同步可能会因为缓冲区刷新顺序而出现输出错位。这种问题在单组数据下不明显在T比较大时偶发排查起来很恶心。还有一点每组测试之间没有空行输出也是每组答案一行共识序列加一行距离不需要额外加空行。多打空行会被判Presentation Error。4.3 边界数据的验证方法自己造一组“全并列”用例我调试这道题时手动构造了几组边界数据n1时任何一列都只有一个字符答案串就是那条输入本身距离为0。这能验证主循环归一化逻辑。n4且m1四个字符A、C、G、T各出现一次那么四个候选答案的距离都是3因为任意选一个都有3个位置不同此时必须输出A。所有序列完全相同共识序列就是它们本身距离为0。把这些用例跑一遍基本能确定贪心主体和字典序分支都写对了。如果你还想更变态一点可以写一个暴力枚举4^m的验证程序和贪心结果对拍随机造几百组小数据任何错误都会立刻暴露。对拍是刷题过程中性价比最高的自查手段没有之一。5. 从OJ题目到真实场景共识序列的用武之地5.1 生物信息学里的多序列比对“共识序列”不是一个只在OJ里存在的抽象概念。在真实的基因分析流程中研究者经常会把多个样本的测序结果比对到同一个参考区域然后提取一条共识序列用于后续的物种鉴定或变异检测。道理和这道题一模一样每一列就像比对结果中的一个位点大家在这个位点上的碱基可能不完全一致取出现频率最高的碱基作为该位点的代表。当然真实场景要复杂得多会有缺口、质量值、链方向等问题Hamming距离也会被更精细的比对打分替代。但核心思想没有变从一堆序列里找出一个最能代表整体的序列。理解这道题等于理解了多序列比对中最基础的一层。5.2 如果n和m变大代码怎么改这题的原始数据范围很温和二维字符数组存得下。但如果把n和m都放大到十万级别二维数组就存不下了逐列统计的思路反而更好读每一行时直接把这个串每一位的字符累加到第j列的计数器里。这样只需要O(m)个计数器加O(m)的输出串甚至不需要把原始序列保存下来。更进阶一点如果输入不是一次性读完而是流式到达这种“一边读一边累加列统计”的方法依然是可行的。它说明了一个通用的技巧当最终答案只需要统计信息而不需要原始数据时尽量压缩存储只保留必要状态。5.3 变式题加权投票与自定义字母表理解了这道题很多变式都可以直接套如果每一列不是字符而是数字字母表变成0~9字典序顺序就是数字顺序映射表改成数字数组即可。如果每条序列有一个权重那么“出现次数”变成“权重累加”选最大加权和的字符。如果不同位置的差异代价不同那就不是简单计数而是要把代价算进去选总代价最小的字符。这些变式的共通点是只要目标函数对每一列可分离就能用“逐列独立决策”的思路处理。这也解释了为什么很多题解强调“先证明可分离再写贪心”。最后再分享一个小技巧做这类“输出最优字符串最小值”的题我会先把答案串和代价分开算不要在一个循环里混着写。先确定每列选谁再累加距离逻辑清晰调试方便。等你把这道题真正想透21行代码不仅是一行不多一行不少而是每一行都有它存在的理由。