《OnlineJudge例题讲解.ppt》由会员分享，可在线阅读，更多相关《OnlineJudge例题讲解.ppt（22页珍藏版）》请在三一办公上搜索。
1、Online Judge例题讲解,南开ACM协会,1002:NKPC1Lucy的难题,f(n)当 n=50025002 的时候，f(n)=n-5；当 n50025002 的时候，f(n)=f(f(n+2005)。现在请您试试编程解决Lucy的难题！初步想法：int f(int n)if(n50025002)return f(f(n+2005);return n-5;,Runtime Error,1002:NKPC1Lucy的难题,错误原因：递归层数太多，栈溢出简单的改进-递归化为循环用m表示f的层数，f(m,n)表示参数n嵌套了m层f，例如f(3,n)=f(f(f(n)f(1,n)=f(n)f
2、(0,n)=n,while(1=scanf(%d,1002:NKPC1Lucy的难题,进一步改进设k=50025002f(1,k)=f(2,k+2005)=f(1,k+2000)也即f(k)=f(k+2000)设k+2005*m=50025002时有f(1,k)=f(1,k+2000),1002:NKPC1Lucy的难题,当k+2005*(m+1)=50025002时f(1,k)=f(2,k+2005)=f(2,k+2005+2000*t)=f(1,k+2000*(t+1)进一步可知f(k)=f(k+2000)仍然成立这样得到一个简单的方法，如果n50025002，将n累加2000，直到超过5
3、0025002即可，代码略,1263:粗心的物理学家,计算1+1/2+1/3+1/n其中n=5*106输入n输出计算结果，保留12位小数double s;/记录最终计算结果int i,j;,1263:粗心的物理学家,while(scanf(%d,Wrong Answer,为什么？,1263:粗心的物理学家,精度问题原因是double本身精度有限如果将上述程序中的循环改为for(i=j;i=1;-i)s+=1./i;则AC,1023:A+B+C+D+.的挑战,输入有多行数据，每行有若干整数，这些整数数以空格分割，请分别求出每行整数的和。Sample Input100 200 445 45 Sam
4、ple Output30490,1023:A+B+C+D+.的挑战,如果用普通的读入方法读入整数，则无法知道什么时候是一行的结束有很多处理方法，这里介绍用getchar()getchar()无参数，它读入一个字符，可以是转义字符，返回值为int型，表示ASCII思考：getchar()返回值为什么不是char?,1023:A+B+C+D+.的挑战,int sum,a;char ch;/sum为结果，a为当前数ch=getchar()反复读入字符，有以下几种情况1，ch=0 a=0,1023:A+B+C+D+.的挑战,也可以利用cin.getline函数读入一整行，包括空格，或者gets函数也可
5、以得到相同效果读入一整行之后，可以同样采取上述方法解题，但如果熟悉strtok函数的话实际上还有更好的做法，留作自学,1046:正整数划分问题,将一个正整数n表示成一系列正整数的和，如：N=n1+n2+nk（其中n1n2nk1，k1）正整数n的一个这种表示成为正整数n的一个划分。现在给出一个正整数n（80n1），求n的不同划分一共有多少种。,1046:正整数划分问题,假设n已经划分出一个数字为n1，则n-n1的划分成为一个子问题，因此可以考虑动态规划（Dynamic Programming=DP）但是n-n1的划分必须满足一个条件：划分出的最大数字不超过n1，因此我们可以设dpij表示将i进行
6、划分，划分出的最大数字不超过j的种类,1046:正整数划分问题,初始值a1i=1,ai1=1(i=1)a0i=1(i=0)思考这里为什么不设为=0递推aij=sumai-kk/ji输出ann即可,a00=1;for(i=1;iN;+i)ai1=a1i=a0i=1;for(i=2;iN;+i)for(j=2;j=i;+j)for(k=1;k=i,Other Problems,互动请说出你在Online Judge上面感兴趣的题目一起讨论,welcome to NKOJ,进入Ranklist Top 20 并不困难每天来到NKOJ，体会AC的乐趣AC=AcceptedWA（哇）=Wrong AnswerTLE=Time Limit Exceeded,NKPC介绍,也即南开大学程序设计竞赛我为程序狂每年四月举行，已举办三届中英文两版试题，英文试题早公布10道题目，10-14天时间，将代码提交到指定地址，不看代码内容，只根据测试数据打分，每个数据9分，10组全对另加10分颁发奖状、奖品计划下一届公开征题，针对低年级单独评奖,有奖解题,准备近期办一次有奖解题低年级单独评奖，奖品以算法相关书籍为主1-2题，难度不大，但需要花一点时间去写多参加ACM协会的活动有助于今后组队参加ACM国际大学生程序设计竞赛,Edit by刁瑞05数学试点班ID:doraemonok&dorajudge,
