[2018年必威体育精装版整理]09-习题探讨.ppt

Practice makes perfect练习题 例1. Pascals Travels 给定棋盘map[r][c]，要求从最左上角跳到最右下角。怎么跳呢？每次只能向右或向下跳最多map[i][j] 步。问要跳到目的地有多少种跳法。 Input: 4 2331 1213 1231 3110 -1 Output: 3 Hint: Brute force methods (简单模式匹配算法)examine every path. int main() { register int i,j,k; char map[35][35]; int n; __int64 ans[35][35];//记录到达该点的路径数目 while(scanf(%d,n)n!=-1) { for(i=1;i=n;i++) { getchar(); for(j=1;j=n;j++) { scanf(%c,map[i][j]); ans[i][j]=0; } } ans[1][1]=1; for(i=1;i=n;i++) for(j=1;j=n;j++) { //向下可到达[i][j] for(k=1;ki;k++) if(i-k==map[k][j]-0) ans[i][j]+=ans[k][j]; //向右可到达[i][j] for(k=1;kj;k++) if(j-k==map[i][k]-0) ans[i][j]+=ans[i][k]; } printf(%I64d\n,ans[n][n]); } return 0; } 例2. Analyzing Login/Logout Records 学生上机图： Input: 4 2 //4PC 2Stu 10 //10 Records 775 1 1 1 //第775分钟 第一台电脑 第一个学生 上机 780 4 2 1 //………………… 790 2 1 1 800 2 1 0 810 3 1 1 820 1 1 0 //第820分钟 第一台电脑 第一个学生 下机 825 3 1 0 860 1 1 1 870 4 2 0 880 1 1 0 1 // 1 个询问 780 870 1 // 第780到第870分钟，第1个人上机多长时间 Output: 55 struct xxx { int time,pc,stu,flag; }a[1005]; void judge() { if(segst=t1 segedt1 seged=t2) sum+=seged-t1; else if(segst=t1 segedt2) sum+=t2-t1; else if(segst=t1 segst=t2 seged=t1 seged=t2) sum+=seged-segst; else if(segst=t1 segst=t2 segedt2) sum+=t2-segst; } int main() { int i,j,k; while(scanf(%d%d,PC,STU)(PC||STU)) { scanf(%d,rec); for(i=0;irec;i++) scanf(%d%d%d%d,a[i].time,a[i].pc,a[i].stu,a[i].flag); scanf(%d,que); for(i=0;ique;i++) { scanf(%d%d%d,t1,t2,pp); count0=0;count1=0; segst=-1;seged=-1; sum=0; for(j=0;jrec;j++) // 对于每一条记录 { if(a[j].stu==pp) // 如果是这个学生的记录 { if(segst==-1) segst=a[j].time; if(a[j].flag==1) count1++; else count0++; if(count0==count1) { seged=a[j].time; judge(); if(seged=t2) break; else { segst=-1; seged=-1; } } }