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

问题求解与程序设计李文新2004.2-6问题求解与程序设计课程内容授课方式成绩评定进度安排信息学奥赛简介ACM大学生程序设计竞赛简介简单题–较难题作业课程内容信息学奥赛及ACM比赛题目•透过比赛题目，提高分析问题和应用计算机编程解决问题的能力•为北大ACM代表队培养后备人才授课方式每周二9-10，电教125集中授课•教师讲授•学生分组讨论，全班讨论•学生讲授每周两小时上机，时间地点待定•网上计时做题成绩评定总则：做够一定数量的题目可以及格想要优秀则需要在班里排名前10%期中20%+期末40%+作业30%+个人表现10%作业：每周2-4题，每月出1题进度安排1-2简单题3模拟题4-5图论题6组合数学题7几何题8-9动态规划题10-11搜索题12-14综合信息学奥赛简介对象组织形式考试方式题目及评分我国的情况ACM竞赛简介对象组织形式考试方式题目及评分我国及我校的情况ACM竞赛样题一个最简单的ProblemSimple.docIOI2002试题乌托邦utopia.doc例题：ioi2002day1task2utopia问题描述–utopia.doc问题分析•两个彼此独立的序列•对于一维问题求解•符号序列si•数值序列xi•对xi重新排列并加相应的正负号，使其按新顺序逐一相加后，等到符号si.例题：ioi2002day1task2utopia--问题的解Definition–alternatingsequenceAsequenceofnon-zerointegersX=(xa,xa+1,…,xb,),a≤bisanalternatingsequenceif1)|xa||xa+1|…|xb|,and2)foralli,ai≤b,thesignofxiisdifferentfromthesignofxi-1.Here,|xa|istheabsolutevalueofxa.例题：ioi2002day1task2utopia--问题的解Lemma1.LetX=(xa,xa+1,…,xb)beanalternatingsequence.Thesignofxbisequaltothesignof∑a≤i≤bxi,thetotalsumofelementsinX.例题：ioi2002day1task2utopia--问题的解ProofAssume:•xbispositive•numberofelementsinXisevenThen:xa+xa+1,xa+2+xa+3,…,xb-1+xbareallpositive,thusthetotalsum∑a≤i≤bxiispositive.例题：ioi2002day1task2utopia--问题的解Example1.(-1,+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,thenthereexistsasequenceX’=(xia,xia+1,…,xib)suchthat1){xa,xa+1,…,xb}={xia,xia+1,…,xib},and2)X’isvalidwithrespecttoS.例题：ioi2002day1task2utopia--问题的解ProofTheproofisbyinductiononthenumberofkofelementsinX.Whenk=1,itiseasytoseethatX’=XisavalidsequencewithrespecttoS.Nowweassumethatk≥2.WeletS1=S-sb,thatis,S1=(sa,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=(+5).Thus,X3’=(+5),X2’=(+5,-7),X1’=(+5,-7,-4),X’=(+5,-7,-4,+8).例题：ioi2002day1task2utopia--问题的解Example4.X=(-1,+2,-3)andS=(-,-,-),S1=(-,-),X1=(+2,-3),S2=(-),X2=(-3).Thus,X2’=(-3),X1’=(-3,+2),X’=(-3,+2,-1).例题：ioi2002day1task2utopia--问题的解AlgorithmofutopiaStep1.//readinput1.1readN;1.2read2NcodenumbersandpartitionthemintoAandBsuchthat|A|=|B|;1.3readasequenceofregionsR=(r1,r2,…,rN);例题：ioi2002day1task2utopia--问题的解Step2.//findx-coordinatesofcodepairs2.1findasequenceofsignsS=(s1,s2,…,sN)suchthatforallj,1≤j≤N,sj=‘+’ifrj=1,4;otherwisesj=‘-’.2.2findanalternatingsequenceX=(x1,x2,…,xN)fromAsuchthatthesignofxNisequaltosN.2.3givenXandS,findavalidsequenceX’=(xi1,xi2,…,xiN)w.r.tSaccordingtotheproofofTheorem1.例题：ioi2002day1task2utopia--问题的解Step3.//findy-coordinatesofcodepairs3.1findasequenceofsignsS=(s1,s2,…,sN)suchthatforallj,1≤j≤N,sj=‘+’ifrj=1,2;otherwisesj=‘-’.3.2findanalternatingsequenceY=(y1,y2,…,yN)fromBsuchthatthesignofyNisequaltosN.3.3givenYandS,findavalidsequenceY’=(yi1,yi2,…,yiN)w.r.tSaccordingtotheproofofTheorem1.例题：ioi2002day1task2utopia--问题的解Step4.//writeoutputprint(xi1,yi1),(xi2,yi2),…,(xiN,yiN).例题：ioi2002day1task2utopia--问题的解Theorem2AlgorithmUtopiaiscorrect,anditsrunningtimeisO(NlogN).ProofThecorrectnessofthealgorithmismainlyduetoTheorem1.ThecomplexityofeachstepexceptStep2.2and3.2osO(N),whereStep2.2and3.2requireO(NlogN)timeforsorting.例题：ioi2002day1task2utopia--问题的解TestingdataNoSize,nmDescription1N=4Example22N=10Keyvalue:1~20,Circularplanesweep3N=10Keyvalue:Startingfrom30,step1or2,scramled………25N=10000Keyvalue:Startingfrom80000~99999,scambled例题：ioi2002day1task2utopia--问题的解Grading4*25=100例题：ioi2002day1task2utopia--问题的解考试答题情况TaskSubmissionNo.offullscoresAverageUptopia209716.21作业用C04+学号建立帐户完成1005，1006题