文档介绍：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/普及&提高/阅读程序
无向图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