文档介绍：NOIP 试题背景分析与复杂度理论北京大学计算机系钟诚 2011 年1月21日上午于全国青少年信息学奥林匹克冬令营?2004 年在上海、 2006 年在四川,我曾作为打酱油营员,参加过冬令营。?当初觉得,许多授课内容都听不懂。感受如下图所示: 我曾经的感受?队列快照是指在某一时刻队列中的元素组成的有序序列。现有 3个正整数元素依次入队、出队。已知它们的和为 8,则共有_________ 种可能的不同的队列快照(不同队列的相同快照只计一次) 。?例如, "5 1" 、"4 2 2" 、""都是可能的队列快照;而"7" 不是可能的队列快照,因为剩下的2个正整数的和不可能是 1。 NOIP2010 ,普及组,问题求解 2 各种疑问?“队列快照是指在某一时刻队列中的元素组成的有序序列。”?有序序列是指计顺序的序列。意思是:序列1、2、3与序列 2、3、1算两种不同的序列。无序序列与有序序列相对,表示不计顺序的序列。?那种被误解的意思,应当用“(单调)递增/ 递减序列”来表达。什么是“有序序列”? function r(n : integer) : integer; var i : integer; begin if n <= 5 then begin r := n; exit; end ; for i := 1 to 5 do if r(n - i) < 0 then begin r := i ; exit ; end ; r := -1; end ; NOIP2010/ 普及&提高/阅读程序 7 ?无向图 G有7个顶点,若不存在由奇数条边构成的简单回路,则它至多有_________ 条边。 NOIP2010 ,提高组,问题求解 2 ?如果只有 3个顶点,则至多 2条边。?如果有5个顶点,任取 G中一条边的两个顶点A、B,则剩余 3个顶点中的每一个至多与 A、B中的一个有边相连。因此, 5个顶点时至多有 2 + 3 + 1 = 6 条边。 NOIP2010 ,提高组,问题求解 2 ?同理,当 G有7个顶点时,至多有 6 + 5 + 1 = 12条边。?另外,当 G为一边为 3个顶点、一边为 4个顶点的二部图时,恰好有 12条边,且不存在由奇数条边构成的简单回路。 NOIP2010 ,提高组,问题求解 2 ?记T为一队列,初始时为空,现有 n个总和不超过 32的正整数依次入队。?如果无论这些数具体为何值,都能找到一种出队的方式,使得存在某个时刻队列 T中的数之和恰好为 9,那么 n的最小值是_________ 。 NOIP2010 ,提高组, 问题求解 3