北京大学ACM国际大学生程序设计竞赛课件1.ppt

1、问题求解与程序设计,李文新 2004.2-6,问题求解与程序设计,课程内容 授课方式 成绩评定 进度安排 信息学奥赛简介 ACM大学生程序设计竞赛简介 简单题 较难题 作业,课程内容,信息学奥赛及ACM比赛题目 透过比赛题目，提高分析问题和应用计算机编程解决问题的能力 为北大ACM代表队培养后备人才,授课方式,每周二 9-10 ， 电教125 集中授课 教师讲授 学生分组讨论，全班讨论 学生讲授 每周两小时上机，时间地点待定 网上计时做题,成绩评定,总则：做够一定数量的题目可以及格 想要优秀则需要在班里排名前10% 期中20% + 期末40% + 作业 30% + 个人表现10% 作业：每周2

2、-4题，每月出1题,进度安排,1-2 简单题 3 模拟题 4-5 图论题 6 组合数学题 7 几何题 8-9 动态规划题 10-11 搜索题 12-14 综合,信息学奥赛简介,对象 组织形式 考试方式 题目及评分 我国的情况,ACM竞赛简介,对象 组织形式 考试方式 题目及评分 我国及我校的情况,ACM竞赛样题,一个最简单的 ProblemSimple.doc,IOI2002试题,乌托邦 utopia.doc,例题：ioi2002 day 1 task 2 utopia,问题描述 utopia.doc 问题分析 两个彼此独立的序列 对于一维问题求解 符号序列 si 数值序列 xi 对xi重新排

3、列并加相应的正负号，使其按新顺序逐一相加后，等到符号si.,例题：ioi2002 day 1 task 2 utopia -问题的解,Definition alternating sequence A sequence of non-zero integers X=(xa, xa+1, xb,), ab is an alternating sequence if 1) |xa| |xa+1| |xb|, and 2) for all i, aib, the sign of xi is different from the sign of xi-1. Here, |xa| is the abso

4、lute value of xa.,例题：ioi2002 day 1 task 2 utopia -问题的解,Lemma 1. Let X=(xa, xa+1, xb) be an alternating sequence. The sign of xb is equal to the sign of aibxi , the total sum of elements in X.,例题：ioi2002 day 1 task 2 utopia -问题的解,Proof Assume: xb is positive number of elements in X is even Then: xa+x

5、a+1 , xa+2+xa+3 , , xb-1+xb are all positive, thus the total sum aibxi is positive.,例题：ioi2002 day 1 task 2 utopia -问题的解,Example 1. (-1,+2,-5,+6) = (-1+2)+(-5+6)=+2 which is positive. Example 2. (+3,-4,+5,-6,+7) =(+3)+(-4+5)+(-6+7) =+5, which is also positive.,例题：ioi2002 day 1 task 2 utopia -问题的解,Th

6、eorem 1. Let X=(xa, xa+1, xb), ab be an alternating sequence, and let S=(sa, sa+1, sb) , ab be a sequence of signs. If the sign of xb is equal to sb , then there exists a sequence X=(xia, xia+1, xib) such that xa, xa+1, xb =xia, xia+1, xib, and X is valid with respect to S.,例题：ioi2002 day 1 task 2 u

7、topia -问题的解,Proof The proof is by induction on the number of k of elements in X. When k=1, it is easy to see that X=X is a valid sequence with respect to S. Now we assume that k2. We let S1=S-sb, that is, S1=(sa,sa+1,sb-1). Case 1. The sign of sb-1 is equal to xb , Let X1=X-xa, that is, X1=(xa+1,xa+

8、2,xb). Case 2. The sign of sb-1 is equal to xb-1 , Let X1=X-xb, that is, X1=(xa,xa+1,xb-1).,例题：ioi2002 day 1 task 2 utopia -问题的解,Example 3. X=(-4,+5,-7,+8),S=(+,-,-,+), we have S1 = (+,-,-), X1=(-4,+5,-7), S2 = (+,-), X2=(+5,-7), S3 = (+), X3=(+5). Thus, X3=(+5), X2=(+5,-7), X1=(+5,-7,-4), X =(+5,-7

9、,-4,+8).,例题：ioi2002 day 1 task 2 utopia -问题的解,Example 4. X=(-1,+2,-3) and S=(-,-,-), S1=(-,-), X1=(+2,-3), S2=(-), X2=(-3). Thus, X2=(-3), X1=(-3,+2), X =(-3,+2,-1).,例题：ioi2002 day 1 task 2 utopia -问题的解,Algorithm of utopia Step 1. /read input 1.1 read N; 1.2 read 2N code numbers and partition them i

10、nto A and B such that |A|=|B|; 1.3 read a sequence of regions R=(r1, r2, ,rN );,例题：ioi2002 day 1 task 2 utopia -问题的解,Step 2. /find x-coordinates of code pairs 2.1 find a sequence of signs S=(s1, s2, ,sN ) such that for all j , 1jN, sj=+ if rj=1,4; otherwise sj=-. 2.2 find an alternating sequence X=(

11、x1, x2, ,xN ) from A such that the sign of xN is equal to sN . 2.3 given X and S , find a valid sequence X=(xi1, xi2, ,xiN ) w.r.t S according to the proof of Theorem 1.,例题：ioi2002 day 1 task 2 utopia -问题的解,Step 3. /find y-coordinates of code pairs 3.1 find a sequence of signs S=(s1, s2, ,sN ) such

12、that for all j , 1jN, sj=+ if rj=1,2; otherwise sj=-. 3.2 find an alternating sequence Y=(y1, y2, ,yN ) from B such that the sign of yN is equal to sN . 3.3 given Y and S , find a valid sequence Y=(yi1, yi2, ,yiN ) w.r.t S according to the proof of Theorem 1.,例题：ioi2002 day 1 task 2 utopia -问题的解,Ste

13、p 4. /write output print (xi1,yi1),(xi2,yi2),(xiN,yiN).,例题：ioi2002 day 1 task 2 utopia -问题的解,Theorem 2 Algorithm Utopia is correct, and its running time is O(NlogN). Proof The correctness of the algorithm is mainly due to Theorem 1. The complexity of each step except Step2.2 and 3.2 os O(N), where Step 2.2 and 3.2 require O(NlogN) time for sorting.,例题：ioi2002 day 1 task 2 utopia -问题的解,Testing data,例题：ioi