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

《北京大学ACM国际大学生程序设计竞赛课件1》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、4-5图论题6组合数学题7几何题8-9动态规划题10-11搜索题12-14综合信息学奥赛简介对象组织形式考试方式题目及评分我国的情况ACM竞赛简介对象组织形式考试方式题目及评分我国及我校的情况ACM竞赛样题一个最简单的ProblemSimple.docIOI2002试题乌托邦utopia.doc例题：ioi2002day1task2utopia问题描述–utopia.doc问题分析两个彼此独立的序列对于一维问题求解符号序列si数值序列xi对xi重新排列并加相应的正负号，使其按新顺序逐一相加后，等到符号si.例题：ioi2002day1task2utopia--

3、问题的解Definition–alternatingsequenceAsequenceofnon-zerointegersX=(xa,xa+1,…,xb,),a≤bisanalternatingsequenceif1)

4、xa

5、<

6、xa+1

7、<…<

8、xb

9、,and2)foralli,a

10、xa

11、istheabsolutevalueofxa.例题：ioi2002day1task2utopia--问题的解Lemma1.LetX=(xa,xa+1,…,xb)beanalte

12、rnatingsequence.Thesignofxbisequaltothesignof∑a≤i≤bxi,thetotalsumofelementsinX.例题：ioi2002day1task2utopia--问题的解ProofAssume:xbispositivenumberofelementsinXisevenThen:xa+xa+1,xa+2+xa+3,…,xb-1+xbareallpositive,thusthetotalsum∑a≤i≤bxiispositive.例题：ioi2002day1task2utopia--问题的解Example1.(-1

13、,+2,-5,+6)=(-1+2)+(-5+6)=+2whichispositive.Example2.(+3,-4,+5,-6,+7)=(+3)+(-4+5)+(-6+7)=+5,whichisalsopositive.例题：ioi2002day1task2utopia--问题的解Theorem1.LetX=(xa,xa+1,…,xb),a≤bbeanalternatingsequence,andletS=(sa,sa+1,…,sb),a≤bbeasequenceofsigns.Ifthesignofxbisequaltosb,thenthereexistsas

14、equenceX’=(xia,xia+1,…,xib)suchthat{xa,xa+1,…,xb}={xia,xia+1,…,xib},andX’isvalidwithrespecttoS.例题：ioi2002day1task2utopia--问题的解ProofTheproofisbyinductiononthenumberofkofelementsinX.Whenk=1,itiseasytoseethatX’=XisavalidsequencewithrespecttoS.Nowweassumethatk≥2.WeletS1=S-sb,thatis,S1=(s

15、a,sa+1,…,sb-1).Case1.Thesignofsb-1isequaltoxb,LetX1=X-xa,thatis,X1=(xa+1,xa+2,…,xb).Case2.Thesignofsb-1isequaltoxb-1,LetX1=X-xb,thatis,X1=(xa,xa+1,…,xb-1).例题：ioi2002day1task2utopia--问题的解Example3.X=(-4,+5,-7,+8),S=(+,-,-,+),wehaveS1=(+,-,-),X1=(-4,+5,-7),S2=(+,-),X2=(+5,-7),S3=(+),X3=

16、(+5).