NOIP 普及组初赛 · NOIP 2009 普及组初赛试题 第 21 题

小陈现有 $2$ 个任务 $A,B$ 要完成，每个任务分别有若干步骤如下：$A=a_1\to a_2\to a3$，$B=b_1\to b_2\to b_3\to b_4\to b_5$。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如 $\dots \to a_2\to b_2\to a_3 \to b_3 \to\dots$ 是合法的，而 $\dots \to a_2\to b_3\to a_3\to b_2\dots$ 是不合法的。小陈从 B 任务的 $b_1$ 步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任务 A，其他的都忘了。试计算小陈饭前已做的可能的任务步骤序列共有（ ）种。

这道题本质是带约束的插空计数。拿到题先别急着列全排列，抓住两个硬约束：序列必须以b1开头、必须以a3结尾。把A的a1,a2和B的剩余步骤看作待插入的元素，用隔板法或组合数公式就能快速算出总数。

最容易掉进两个坑：一是忽略'从b1开始'这个隐含条件，把b1当成普通元素参与排列，导致多算或少算；二是误以为B的任务必须全部做完，其实题目只要求A做完，B可以只做b1到b5中的任意一段。另外，有人会把a1,a2,a3当成独立元素乱插，忘了它们必须保持相对顺序，这就需要用'保持顺序的插入'思路，而不是简单的全排列。

考点与概念

本题考查的是保持相对顺序的序列计数（有时也叫"穿插"或"合并有序序列"问题）。核心概念很简单：如果有两个已经排好序的序列，比如A的a1,a2,a3和B的b1,b2,b3,b4,b5，要把它们合并成一个新序列，同时保证A里的元素依然按a1→a2→a3出现，B里的元素依然按b1→b2→…→b5出现，那么合并的方式数量就是一个经典组合问题。

命题视角：挖坑在哪？

命题人喜欢把这类问题包装成"任务调度"或"步骤执行"，然后埋下几个隐蔽条件： 1. 起点固定：题目说"从B任务的b1步骤开始做"，这意味着整个序列的第一个元素必须是b1，不能随便插别的。 2. 终点固定："恰做完某个任务的某个步骤后停工，回来只记得完成了整个任务A"，说明序列的最后一个元素一定是a3（A的最后一个步骤）。 3. B不必做完：题目没要求B完成，所以b2~b5可以出现，也可以不出现，只要保持顺序就行。

这些条件如果不细读，很容易误以为是普通的"A和B各完成所有步骤"，那样答案就会变成C(8,3)=56，或者误以为b1只是普通元素，导致计算偏差。