NOIP 普及组初赛 · NOIP 2010 普及组初赛试题 第 22 题

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

这题别急着列所有情况，先抓住核心：3个正整数和为8，本质是求正整数解个数（隔板法）。关键是理解队列快照只记录“当前在队元素”，入队出队顺序不同但中间状态相同只算一次。从数字拆分入手，再对每种拆分枚举所有可能的出队时机，最后去重计数。

最容易栽跟头的地方有三处：一是把“队列快照”当成最终出队的顺序，其实快照是任意时刻的中间状态；二是忽略正整数限制，误以为0也能入队，导致拆分方案变多；三是重复计数，比如(1,1,6)和(6,1,1)虽然数字一样，但入队顺序不同产生的快照集合完全不同，必须分开算。另外，有人会把不同队列产生的相同快照合并，题目明确说“不同队列的相同快照只计一次”，这里指的是同一个数字组合在不同入队顺序下若产生完全相同的快照序列，才去重，而不是把不同数字组合的快照混在一起去重。

考点与概念

这题考查的是队列（FIFO）的动态状态计数，核心在于理解“队列快照”是某一时刻队列中所有元素的有序序列。队列的特点是先进先出，元素一旦入队就排在队尾，出队时从队头拿走。因此，对于一组固定的正整数（比如{1,1,6}），不同的入队顺序和出队时机会产生不同的中间快照。

命题视角

命题人喜欢用这种“过程性”的计数题挖坑。它不直接问“有多少种排列”，而是问“有多少种可能的快照”。这意味着你必须模拟队列的操作过程，而且要注意：不同入队顺序可能产生完全相同的快照序列（例如先入1再入1和先入1再入另一个1，如果第二个1还没出队，快照看起来一样），但题目要求的是“不同队列的相同快照只计一次”，这里的“不同队列”指的是由不同数字组成的队列，还是指不同操作序列？结合例子“5,1”和“4,2,2”都是可能的快照，而“7”不可能，说明快照是由当前在队的数字决定的，只要数字集合和顺序相同，就算同一个快照。因此，我们需要对每一种满足a+b+c=8的正整数解，枚举所有可能的操作序列（入队、出队），然后统计所有不重复的快照。

• 答案：49

以上为完整解析的章节结构，展开每一步的推导、正确性说明与复杂度分析请在平台查看。