NOIP 普及 2010 第一轮 第 22 题：正整数队列快照的可能数量

题目

队列快照是指在某一时刻队列中的元素组成的有序序列。例如，当元素 $1,2,3$ 入队，元素 $1$ 出队后，此刻的队列快照是 $2,3$。当元素 $2,3$ 也出队后，队列快照是""，即为空。现有 $3$ 个正整数元素依次入队、出队。已知它们的和为 $8$，则共有_种可能的不同的队列快照（不同队列的相同快照只计一次）。例如，"$5,1$"、"$4,2,2$"、""都是可能的队列快照；而"$7$"不是可能的队列快照，因为剩下的 $2$ 个正整数的和不可能是 $1$。

答案

49

题解

考点定位

本题考「计数问题」,对应大纲 2.1.5 组合计数（难度【4】）。

解题过程

3 个正整数 a,b,c 和为 8。队列快照 = 出队若干后的剩余序列：可能是 abc、bc、c、空（4 个阶段）。所有可能快照去重计数：

• 空快照：1 种；
• 单元素快照：c 或 b 或 a 都可能作为唯一剩余：{1},{2},…,{7}？剩一个元素时它是「还没出队的第一个」= a/b/c 之一，值为 1..6（其余两数 ≥1 且和 =8−值 ≤？值 ∈1..6）：所有可能单元素值 = {1,2,3,4,5,6}，6 种；
• 双元素快照：{b,c}（a 已出）或 {a,b},{a,c}？出队顺序只能从头出：剩两个 = {b,c}（a 已出）——但入队后可先出 a 或不出……「依次入队、出队」灵活：快照 {x,y}（正整数对，和 ≤7）：所有无序？快照有序。枚举可能：(1,1)…值对 (x,y) x,y≥1，x+y≤6，有序？{b,c} 保序。(a,b) 时 c 已出？c 后入不能先出 ✗。合法双快照 = (b,c) 类型：x=b,y=c，b+c ≤7：(1,1)..(1,5),(2,1).. 共 C(6,2)=15 对？x+y≤7 且 ≥2 的正整数对数 = C(7,2)=21？x+y ≤ 7（a≥1）：对数 = Σ_{s=2..7}(s−1) = 21？(b,c) 有序对且和 ≤7：21 种；
• 三元素快照 (a,b,c)：和=8 唯一形态？(1,1,6),(1,2,5)…= C(7,2)=21 种（有序三和为 8 的正整数组数 = C(7,2)=21）。

总计：1+6+21+21 = 49？单元素 6 种、双 21、三 21、空 1 = 49 ✓。

答案：49。

易错提醒

① 快照阶段至多 4 种（全在/剩俩/剩一/空）；② 同一快照可能来自不同 (a,b,c)，按题意只计一次——用「值集合」去重而非方案数。