当前位置:首页 >> 学科竞赛 >>

NOIP2007年信息学奥赛普及组复赛参考答案


2007 普及组复赛 C 语言答案; 1.奖学金;(scholar.pas/c/cpp);【问题描述】;某小学最近得到了一 笔赞助, 打算拿出其中一部分为学; 任务: 先根据输入的 3 门课的成绩计算总分, 然后按上; 7279; 5279; 这两行数据的含义是: 总分最高的两个同学的学号依次; 7279;则按输出错误处理,不能得分;【输入】;输入文件 scholar.in 包含

行 n+1 行:; 2007 普及组复赛 C 语言答案 1.奖学金 (scholar.pas/c/cpp) 【问题描述】 某小学最近得到了一笔赞助,打算拿出其中一部分为学习成绩优秀的前 5 名学生发奖学金。期末,每个学生都有 3 门课的成绩:语文、数学、英语。先按 总分从高到低排序,如果两个同学总分相同,再按语文成绩从高到低排序,如果 两个同学总分和语文成绩都相同,那么规定学号小的同学排在前面,这样,每个 学生的排序是唯一确定的。 任务:先根据输入的 3 门课的成绩计算总分,然后按上述规则排序,最后按 排名顺序输出前 5 名学生的学号和总分。注意,在前 5 名同学中,每个人的奖学 金都不相同,因此,你必须严格按上述规则排序。例如,在某个正确答案中,如 果前两行的输出数据(每行输出两个数:学号、总分)是: 7 279

5 279 这两行数据的含义是:总分最高的两个同学的学号依次是 7 号、5 号。这两 名同学的总分都是 279(总分等于输入的语文、数学、英语三科成绩之和),但学 号为 7 的学生语文成绩更高一些。如果你的前两名的输出数据是: 5 279 7 279 则按输出错误处理,不能得分。 【输入】 输入文件 scholar.in 包含行 n+1 行: 第 l 行为一个正整数 n,表示该校参加评选的学生人数。 第 2 到年 n+l 行,每行有 3 个用空格隔开的数字,每个数字都在 0 到 100 之间。 第 j 行的 3 个数字依次表示学号为 j-1 的学生的语文、 数学、 英语的成绩。 每个学生的学号按照输入顺序编号为 1~n(恰好是输入数据的行号减 1)。 所给 的数据都是正确的,不必检验。 【输出】 输出文件 scholar.out 共有 5 行,每行是两个用空格隔开的正整数,依次表 示前 5 名学生的学号和总分。 【限制】 50%的数据满足:各学生的总成绩各不相同 100%的数据满足:6<=n<=300

【试题分析】 简单的排序。因为 n<=300,所以选择排序不会超时。 存储方面只需存储三个数:学好、语文成绩和总分。 【参考程序】 //第一题解法一 #include<stdio.h> #include<stdlib.h> int main() { long a[16][6]={0},i,j,n; FILE *fp1,*fp2; long ii,jj,t0,t5,t4; fp1=fopen("scholar.in","r"); fscanf(fp1,"%d",&n); printf("%d\n",n); for(i=0;i<16;i++) {

fscanf(fp1,"%d %d %d",&a[i][1],&a[i][2],&a[i][3]); a[i][4]= a[i][1]+a[i][2]+a[i][3]; a[i][5]= a[i][4]*10000+a[i][1]*100+(100-a[i][0]); a[i][0]=i+1; printf("%d %d %d %d %d %d\n",a[i][0],a[i][1],a[i][2],a[i][3],a[i] [4],a[i][5]); } /* a[i][0]=学号 a[i][1]= 语文 a[i][2]=数学 a[i][3]=英语 a[i][4]=总分 a[i][5]=总分 X 100+语文 -学号 */ fclose(fp1); for(ii=0;ii<15;ii++) for(jj=0;jj<15-ii;jj++) if(a[jj][5]<a[jj+1][5]){ t5=a[jj][5];

a[jj][5]=a[jj+1][5]; a[jj+1][5]=t5; t0=a[jj][0]; a[jj][0]=a[jj+1][0]; a[jj+1][0]=t0; t4=a[jj][4]; a[jj][4]=a[jj+1][4]; a[jj+1][4]=t4; } printf("\n\n\n"); for(i=0;i<16;i++) printf("%d %d %d %d %d %d\n",a[i][0],a[i][1],a[i][2],a[i][3],a[i] [4],a[i][5]); fp2=fopen("scholar.out","w"); for(i=0;i<5;i++) fprintf(fp2,"%d %d\n",a[i][0],a[i][4]); fclose(fp2);

//----------------printf("\n\n\n"); fp2=fopen("scholar.out","r"); for(i=0;i<5;i++){ fscanf(fp2,"%d %d",&a[i][0],&a[i][1]); printf("%d %d\n",a[i][0],a[i][1]);} fclose(fp2); getchar(); getchar(); } //第一题解法二 #include<stdio.h> #include<stdlib.h> typedef struct {int num; int chinese; int math;

int english; int sum; long num4sort; }SCORE; int main() { SCORE s[300]; int i,j,n; FILE *fp; long ii,jj,t0,t5,t4; fp=fopen("scholar.in","r"); fscanf(fp,"%d",&n); printf("%d\n",n); for(i=0;i<n;i++) { fscanf(fp,"%d %d %d",&s[i].chinese,&s[i].math,&s[i].english); s [i].sum= s[i].chinese+s[i].math+s[i].english;

s[i].num=i+1; s[i].num4sort= s[i].sum*90000+s[i].chinese*300-s[i].num; printf("%d %d %d %d %d %d\n",s[i].num,s[i].chinese,s[i].math,s[i]. english,s[i].sum,s[i].num4sort); } fclose(fp); for(ii=0;ii<(n-1);ii++) for(jj=0;jj<(n-1)-ii;jj++) if(s[jj].num4sort<s[jj+1].num4sort){ t5=s[jj].num4sort; s[jj].num4sort=s[jj+1].num4sort; s[jj+1].num4sort=t5; t0=s[jj].num; s[jj].num=s[jj+1].num; s[jj+1].num=t0; t4=s[jj].sum; s[jj].sum=s[jj+1].sum;

s[jj+1].sum=t4; } printf("\n\n\n";for(i=0;i<n;i++);printf("%d%d%d%d%d%;fp=fopen(" scholar.o;for(i=0;i<5;i++);fprintf(fp,"%d%d\n&;fclose(fp);;//----------------;printf(& printf("\n\n\n"); for(i=0;i<n;i++) printf("%d %d %d %d %d %d\n",s[i].num,s[i].chinese,s[i].math,s[i]. english,s[i].sum,s[i].num4sort); fp=fopen("scholar.out","w"); for(i=0;i<5;i++) fprintf(fp,"%d %d\n",s[i].num,s[i].sum); fclose(fp); //----------------printf("\n\n\n"); fp=fopen("scholar.out","r"); for(i=0;i<5;i++){ fscanf(fp,"%d %d",&s[i].num,&s[i].sum);

printf("%d %d\n",s[i].num,s[i].sum);} fclose(fp); getchar(); getchar(); } 2.纪念品分组 (group.pas/c/cpp) 【题目描述】 元旦快到了, 校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加 晚会的同学所获得的纪念品价值相对均衡, 他要把购来的纪念品根据价格进行分 组, 但每组最多只能包括两件纪念品,并且每组纪念品的价格之和不能超过一个 给定的整数。 为了保证在尽量短的时间内发完所有纪念品,乐乐希望分组的数目 最少。 你的任务是写一个程序, 找出所有分组方案中分组数最少的一种,输出最少 的分组数目。 【输入】 输入文件 group.in 包含 n+2 行: 第 1 行包括一个整数 w,为每组纪念品价格之和的上限。

第 2 行为一个整数 n,表示购来的纪念品的总件数。 第 3~n+2 行每行包含一个正整数 pi(5<=pi<=w), 表示所对应纪念品的价格。 【输出】 输出文件 group.out 仅一行,包含一个整数,即最少的分组数目。 【限制】 50%的数据满足:l<=n<=15 100%的数据满足:1<=n<=30000,80<=w<=200 【试题分析】 贪心法,先排序,然后按以下贪心策略: 设 s 为所需的组数。i,j 为两个指针,开始时指向头和尾。 1.如果 a[i]+a[j]<=w,s=:s+1,i:=i+1,j:=j-1。 2. 如果 a[i]+a[j]>w,s:=s+1,j:=j-1。 因为 n<=300000,所以用选择排序可能会超时,最好用快速排序。 【参考程序】 //第二题解法一 #include<stdio.h> #include<stdlib.h>

#include<math.h> void qsort(int r[],int left,int right); int main() { int r[30000]; int s=0,ww;/*组数*/ int i,j; FILE *fp; int w,n; /*读入前两个数 */ fp=fopen("group.in","r"); fscanf(fp,"%d",&w); fscanf(fp,"%d",&n); printf("w=%d\nn=%d\n",w,n); /*读入其余的数 */ for(i=0;i<n;i++) {fscanf(fp,"%d",&r[i]);

} fclose(fp); /*快速排序*/ qsort(r,0,30000-1); /*显示排序后的结果*/ //for(i=0;i<30000;i++) //printf("%d\n",r[i]); i=0;j=30000-1; while(i<j) { if(r[i]+r[j]<=90) {s++;i++;j--;} else {s++;j--;} } printf("s=%d",s); getchar();

} //------------------------------------------void qsort(int r[],int left,int right) { int i=left,j=right;//最左边序号和最右边序号 int temp=r[i]; //第一 个元素 while(i<j) //当 I,J 没有会合时 { while((r[j]>temp)&&(j>i)) j--; if(j>i) { r[i]=r[j]; i++; } while ((r[i]<=temp)&&(j>i)) i++; if(i<j){r[j]=r[i]; j--; } } r[i]=temp; if(left<i-1)qsort(r,left,i-1); if(i+1<right)qsort(r,i+1,right); } //第二题解法二 #include<stdio.h> #include<stdlib.h> #include<math.h>

void qsort(int r[],int left,int right); int main() { int r[30000]; int s=0,ww;/*组数*/ int i,j; FILE *fp; int w,n; /*读入前两个数 */ fp=fopen("group.in","r"); fscanf(fp,"%d",&w); fscanf(fp,"%d",&n); printf("w=%d\nn=%d\n",w,n); /*读入其余的数 */ for(i=0;i<n;i++) {fscanf(fp,"%d",&r[i]); }

fclose(fp); /*快速排序*/ qsort(r,0,n-1); /*显示排序后的结果*/ for(i=0;i<n;i++) printf("%d\n",r[i]); i=0;j=n-1; while(i<j) { if(r[i]+r[j]<=90) {s++;i++;j--;} else {s++;j--;} } printf("s=%d",s); getchar(); }

//------------------------------------------void qsort(int r[],int left,int right) { int i=left,j=right;//最左边序号和最右边序号 int temp=r[i]; //第一 个元素 while(i<j) //当 I,J 没有会合时 { while((r[j]>temp)&&(j>i)) j--; if(j>i) { r[i]=r[j]; i++; } while ((r[i]<=temp)&&(j>i)) i++; if(i<j){r[j]=r[i]; j--; } } r[i]=temp; if(left<i-1)qsort(r,left,i-1); if(i+1<right)qsort(r,i+1,right); } 3、守望者的逃离 (escape.pas/c/cpp) 【问题描述】 恶魔猎手尤迪安野心勃勃,他背叛了暗夜精灵,率领深;现在已知守望者的 魔法初值 M,他所在的初始位置与岛; 【输入】;在输入文件 escape.in 仅一行, 包括空格隔开;【输出】;在输出文件 escape.out 包括两行:;第 1 行为字符

串“Yes”或“No”(区分大小写);【限制】;30%的数据满足:1<=T<=10,;5 0%的数据满足:1<=T<

12 3 4

恶魔猎手尤迪安野心勃勃, 他背叛了暗夜精灵,率领深藏在海底的娜迦族企 图叛变。守望者在与尤迪安的交锋中遭遇了围杀,被困在一个荒芜的大岛上。为 了杀死守望者,尤迪安开始对这个荒岛施咒,这座岛很快就会沉下去。到那时, 岛上的所有人都会遇难。守望者的跑步速度为 17m/s,以这样的速度是无法逃离 荒岛的。庆幸的是守望者拥有闪烁法术,可在 1s 内移动 60m,不过每次使用闪烁 法术都会消耗魔法值 10 点。守望者的魔法值恢复的速度为 4 点/s,只有处在原 地休息状态时才能恢复。 现在已知守望者的魔法初值 M, 他所在的初始位置与岛的出口之间的距离 S, 岛沉没的时间 T。你的任务写写一个程序帮助守望者计算如何在最短的时间内逃 离荒岛,若不能逃出,则输出守望者在剩下的时间能走的最远距离。注意:守望 者跑步、闪烁或休息活动均以秒(s)为单位,且每次活动的持续时间为整数秒。 距离的单位为米(m)。 【输入】 在输入文件 escape.in 仅一行,包括空格隔开的三个非负整数 M,S,T。 【输出】

在输出文件 escape.out 包括两行: 第 1 行为字符串“Yes”或“No”(区分大小写),即守望者是否能逃离荒 岛。 第 2 行包含一个整数。第一行为“Yes”(区分大小写)时表示守望者逃离 荒岛的最短时间;第一行为“No” (区分大小写)时表示守望者能走的最远距离。 【限制】 30%的数据满足:1<=T<=10,1<=S<=100 50%的数据满足:1<=T<=1000,1<=S<=10000 100%的数据满足:1<=T<=300000,0<=M<=1000,1<=S<=108. 【试题分析】 典型的动态规划。 设 f[i,j]为第 i 秒,魔法值为 j 时可行的最大距离。 f[i,j]:=max{f[i-1,j]+17,f[i-1,j-10]+60,f[i-1,j+4]} (当 j≥10 时); f[i,j]:=max{f[i-1,j]+17,f[i-1,j+4]} (当 j<10 时) 按题目所说,最大魔法值为 1000,最大时间为 300000 秒,那么需要 30000 0000 的数组,空间会溢出,所以使用两个一维数组来迭代,只需 2000 的数组, 但是时间 复杂度为 O(t*m),有可能会超时。 【参考程序 1】

//第三题解法一 #include<stdio.h> #include<stdlib.h> Long a[10001],b[10001]; Long m,s,t,i,j; Long max(long a,long b,long c); /*三个数找最大值*/ Long k; { if (a>b) k=a; else k=b; if (k<c) k=c; max=k; } Int main() { FILE *input,*output; Input=fopen(“escape.in” ,” r” ); output=fopen(“escape.out” ,” w” );

fscanf(“%d %d %d” ,m,s,t); for( i=0;i<=10000;i++) /*{数组清 0}*/ { a[i]=0; b[i]=0; } For(i=1;i<=t;i++) { For( j=0;j<=9;j++) { b[j]=max(a[j]+17,a[j+4],0); /*动态规划}*/ if(b[j]>=s) { fprintf(output,” %s” ,” Yes” ); /*{找到最小解,提前退*/出} fprintf(output,” %d” ,i); fclose(input); fclose(output);

exit(); } } For(j=10;j<=m;j++) { b[j]=max(a[j]+17,a[j+4],a[j-10]+60); /*动态规划}*/ if (b[j]>=s) { fprintf(output,” %s” ,” Yes” ); /*找到最小解,提前退*/ fprintf(output,” %d” ,i); fclose(input); fclose(output); exit(); } } a=b; } fprintf(output,” %s” ,” No” ); /*无解}*/

fprintf(output,” %d” ,a[m]); fclose(input); fclose(output); } /*{注:此程序两个点超时}*/ //第三题解法二 #include<stdio.h> #include<stdlib.h> int main() { long m=36,s=255,t=10,ti;//M 魔法值 S 距离 T 时间 long ms[3][100000];//当前距离和魔法值 long ts[100000]; //当前时间 ms[2][0]=m; ts[0]=0; for (ti=1;ti<=t;ti++) /*动态规划*/ {

if (ms[2][ti-1]>=10)/*如果能使用闪烁,就是用*/ { ms[1][ti]=ms[1][ti-1]+60; ms[2][ti]=ms[2][ti-1]-10; printf("有魔 走的距离=%d---剩余魔法%d %d\n",ms[1][ti],ms[2][ti],t i); } else { ms[1][ti]=ms[1][ti-1]; /*恢复魔法值*/ ms[2][ti]=ms[2][ti-1]+4; printf("没魔 走的距离 法%d\n",ms[1][ti],ms[2][ti]); } if (ts[ti-1]+17>ms[1][ti]) ts[ti]=ts[ti-1]+17 ; else ts[ti]=ms[1][ti]; /*找出大的值*/

if (ts[ti]>=s) /*如果顺利逃出,输出结果*/ { printf("%s","Yes"); printf("%d",ti);getchar(); exit(0); } } printf("%s","no"); /*无法逃出,输出结果*/ printf("%d",ts[t]); getchar(); } /*此程序所有测试点全部通过*/ //第三题解法三 #include<stdio.h> #include<stdlib.h> #include<math.h> =%d---剩余魔

int main() { long mm=136,ss=1755,tt=50;//魔法值,距离,时间 long ss2=ss; long ss0=ss,tt0=tt; while((ss>0&&ss2>0)&&tt>0){ if(mm>=10) {--tt;mm-=10;ss-=60;ss2=ss;} else {--tt;mm+=4;ss2-=17;} printf(" ss=%3d ss2=%3d tt=%3d mm=%3d\n",ss,ss2,tt,mm); if(tt<=0&&(ss>0 && ss2>0)){printf("No 没逃出来,但跑了%d 米\n",ss< ss2?ss0-ss:ss0-ss2);goto abc;} if(tt>=0&&(ss<=0||ss2<=0)) {printf("Yes 用时%d 秒成功逃出\n",tt0tt);goto abc;} } abc:

getchar(); } 4.Hanoi 双塔问题 (hanoi.pas/c/cpp) 【问题描述】 给定 A、B、C 三根足够长的细柱,在 A 柱上放有 2n 个中间有孔的圆盘,共 有 n 个不同的尺 寸,每个尺寸都有两个相同的圆盘,注意这两个圆盘足不加区分的(下图为 n=3 的情形)。现要将 这些圆盘移到 C 柱上,在移动过程中可放在 B 柱上暂存。要求: (1)每次只能移动一个圆盘; (2)A、B、C 三根细柱上的圆盘都要保持上小下大的顺序; 任务: 设 An 为 2n 个圆盘完成上述任务所需的最少移动次数, 对于输入的 n, 输出 An;ABC;【输入】;输入文件 hanoi.in 为一个正整数 n,表示在 A; 【输出】;输出文件 hanoi.out 仅一行,包含一个正整数;【限制】;对于 50% 的数据,1<=n<=25;对于 100%的数据,l<=n<=20;【提示】;设法建立 An 与 A n-1 的递推关系式;【试题分析】;不难发现:;An=2An-1+2(特别的,A1=2);

123 4

输出 An。 A B C 【输入】 输入文件 hanoi.in 为一个正整数 n,表示在 A 柱上放有 2n 个圆盘。 【输出】 输出文件 hanoi.out 仅一行,包含一个正整数,为完成上述任务所需的最少 移动次数 An。 【限制】 对于 50%的数据,1<=n<=25 对于 100%的数据,l<=n<=200 【提示】 设法建立 An 与 An-1 的递推关系式。 【试题分析】 不难发现: An=2An-1+2(特别的,A1=2)

证明如下: 要将 A 柱上的 2n 个盘子移到 C 柱上,最佳的策略就是先将(2n-2)个盘子借 助 C 柱移到 B 柱上, 所需的次数为 An-1,再将 A 柱上最大的两个盘子直接移到 C 柱上,所 需的次数为 2,最后将 B 柱上的(2n-2)个盘子借助 A 柱移到 C 柱上,所需的 次数为 An-1。总次数 An=A n-1+2+An-1=An=2An-1+2。 进而,可以得出: An=2n+1-2 然后使用高精度计算。 【参考程序】 //第四题解法一 #include<stdio.h> long int count=0; int main() { void hanoi(int n,char AA,char BB,char CC); int m=13;

hanoi(m,'a','b','c'); printf("%d",count); getchar(); } //=============================================================== ========= void hanoi(int n,char AA,char BB,char CC) { int move(char x,char y);//声明函数 if(n==1) move(AA,CC); else { hanoi(n-1,AA,CC,BB);//喊上一个和尚把我前边的饼子借助 c 柱放到 b 柱 move(AA,CC);//然后呢,我把我的一个饼子从 a 柱放到 c 柱 hanoi(n-1,BB,AA,CC);//再然后呢, 喊上一个和尚把他的饼子们借助 A 柱放 到 C 柱不就完了,哈哈。 } }

//------------------------------------------------------------------------int move(char x,char y) {printf("%c-->%c\n",x,y); count++; } //第四题解法二 #include<stdio.h> long int count=0; int main() { void hanoi(int n,char A,char B,char C); int m=11; hanoi(m,'a','b','c'); printf("%d",count); getchar(); }

//=============================================================== ========= void hanoi(int n,char A,char B,char C) { int move(char x,char y);//声明函数 if(n==1) move(A,C); else { hanoi(n-1,A,C,B);//喊上一个和尚把我前边的饼子借助 c 柱放到 b 柱 mov e(A,C);//然后呢,我把我的一个饼子从 a 柱放到 c 柱 hanoi(n-1,B,A,C);//再然后呢,喊上一个和尚把他的饼子们借助 A 柱放到 C 柱不就完了,哈哈。 } } //------------------------------------------------------------------------int move(char x,char y) {printf("%c-->%c\n",x,y);

count++; }


相关文章:
第八届信息学奥赛普及组复赛答案
第八届信息学奥赛普及组复赛答案_学科竞赛_初中教育...的题目,NOIp97普及组的最后一题 就和本题几乎一模...2007年及之前历年信息学... 73页 免费 第十四届...
NOIP2007(pascal)第十三届全国青少年信息学奥林匹克联赛初赛试题
NOIP2007(pascal)第十三届全国青少年信息学奥林匹克...学奥林匹克联赛初赛试题( 普及组 Pascal 语言 二...在下列各软件,不属于 NOIP 竞赛(复赛)推荐使用的...
(NOIP2007)第13届全国青少年信息学奥林匹克联赛初赛试题普及组pascal
(NOIP2007)第13届全国青少年信息学奥林匹克联赛初赛试题普及组pascal_IT/计算机_...可以不理睬数据库中的冗余数据 9.在下列各软件,不属于 NOIP 竞赛(复赛)推荐...
NOIP2015普及组复赛试题
NOIP2015普及组复赛试题_学科竞赛_初中教育_教育专区。CCF 全国信息学奥林匹克...CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 CCF 全国信息学奥林匹克联赛(NOIP...
2013年NOIP信息学竞赛普及组参考答案
noip普及组模拟试题 2页 1财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 2013年NOIP信息学竞赛普及组参考答案 201...
2016第22届全国信息学奥林匹克联赛普及组复赛真题
2016第22届全国信息学奥林匹克联赛普及组复赛真题_学科竞赛_初中教育_教育专区。...NOIP2011复赛普及组试题... 5页 免费 十七届全国信息学奥林匹... 5页 2...
noip2011年第十七届全国青少年信息学奥林匹克联赛初赛答案
noip2011年第十七届全国青少年信息学奥林匹克联赛初赛答案_学科竞赛_初中教育_教育专区。NOIP2011 普及组(Pascal 语言)参考答案与评分标准 一、单项选择题(共 20 题...
NOIP2008信息学奥赛联赛普及组模拟题
NOIP2008信息学奥赛联赛普及组模拟题 noip复赛前做一下练练手noip复赛前做一下练练手隐藏>> 中华信息学竞赛网 www.100xinxi.com 官方总站:圣才学习网 www.100xu...
NOIP(2014)第二十届全国青少年信息学奥林匹克联赛初赛(普及组试题及答案)
NOIP(2014)第二十届全国青少年信息学奥林匹克联赛初赛(普及组试题及答案)_学科竞赛_高中教育_教育专区。NOIP(2014)第二十届全国青少年信息学奥林匹克联赛初赛(普及...
全国青少年信息学奥林匹克联赛初赛试题2009-2015
全国青少年信息学奥林匹克联赛初赛试题2009-2015_学科竞赛_初中教育_教育专区。第...; ; 第 9 页共 65 页 NOIP2009 年普及组(Pascal 语言)参考答案与评分标准...
更多相关标签:
noip2016普及组复赛 | noip2015普及组复赛 | noip2013普及组复赛 | noip2014普及组复赛 | noip2012普及组复赛 | noip2009普及组复赛 | noip2011普及组复赛 | noip2008普及组复赛 |