信息学特长生测试题

1、一、安全密码问题描述：密码在我们日常生活中经常要用到，如邮箱密码、QQ密码等，设置一般的密码很容易破解的哦，千万不要用你的出生年月作为你的密码，那样很不安全。小K用到了一种比较安全的密码设置方法：密码由三个正整数a,b,c经过计算a的b次方除以c的余数得到。现在请你编写一个程序，计算ab mod c 的值。数据输入：从文件password.in中读入数据，文件中只有一行，依次为三个正整数a,b,c,三个正整数之间用空格隔开。数据输出结果输出到文件password.out中，只有一个数，表示计算得到的结果。输入输出样例password.in2 3 7password.out1数据范围说明：60%

2、的数据中，a的b次方的值在longint范围内。70%的数据中，a的b次方的值在int64范围内.100%的数据中，a,b,c 的值小于1000 。解析：基础题，直接用 a(b) mod c 就可以了程序：var a,b,c,d,i:longint;begin readln(a,b,c); d:=1; for i:=1 to b do d:=d*a mod c; writeln(d);end.二、农场主问题描述：小张是一个养马农场的农场主，他要把N只马分配到K个马房里，放置的规则是：第1 到 第Pi只马放入第一个马房，第Pi+1 到第Pk只放入第二个马房，.以此类推。此外对于每一个马房都有一个

3、叫做“不高兴系数”，即白色马的数量*黑色马的数量。你的任务是合理地分配这N只马，使得它所有马房的“不高兴系数”和最小。 数据输入：从文件farmer.in中读入数据，文件中第一行有 2 个整数：  N ( 1 <= N <= 500 ) 和  K ( 1 <= K <= N)。接下来的N行有N个数。第 I 行为第 I 只马的颜色： 1 是黑色， 0 是白色。 数据输出：   将结果输出到文件farmer.out中，其结果为最小的“不高兴系数”的总和。输入输出样例：farmer.in6 3110101farmer.out2

4、解析：由于马的顺序不变，就能看出符合无效而且又像深搜，就能用动归。方程： i-1 到 x 的最优值fi,j:=min( fi-1,x+(wj-wx)*(bj-bx) ) i-1<=x<=j-1 白马*黑马 枚举：I, x, j程序：var i,j,k,n,x1,x2,min,x:longint; a,b,w,d:array0.500 of longint; f:array1.500,1.500 of longint;begin readln(n,k); x1:=0; x2:=0; for i:=1 to n do begin readln(ai); if ai=1 then inc

5、(x1) else inc(x2); bi:=x1; wi:=x2; end; for i:=1 to n do f1,i:=wi*bi; for i:=2 to k do for j:=i to n-k+i do begin min:=10000000; for x:=i-1 to j-1 do begin fi,j:=fi-1,x+(wj-wx)*(bj-bx); if fi,j<min then min:=fi,j; end; fi,j:=min; end; write(fk,n);end.三、营救问题描述：铁塔尼号遇险了！他发出了求救信号。距离最近的哥伦比亚号收到了讯息，时间就是

6、生命，必须尽快赶到那里。通过侦测，哥伦比亚号获取了一张海洋图。这张图将海洋部分化成n*n个比较小的单位，其中用1标明的是陆地，用0标明是海洋。当然，船只能在海洋上行驶，且船只能从一个格子，移到相邻的四个格子。为了尽快赶到出事地点，哥伦比亚号最少需要走多远的距离。数据输入：从文件save.in中读入数据，第一行为n,下面是一个n*n的0，1矩阵，表示海洋地图，最后一行为四个小于n的整数，分别表示哥伦比亚号和铁塔尼号的位置。数据输出：哥伦比亚号到铁塔尼号的最短距离，答案精确到整数。输入输出样例：save.in30011011001 1 3 3save.out4数据范围说明：N<=1000。解

7、析：广搜+标记, 也是基础题const fx:array1.4,1.2 of longint=(1,0),(-1,0),(0,1),(0,-1);var n,i,j,sx,sy,px,py:longint; h,t,x,y,x1,y1,k:longint; map:array1.1000,1.1000 of char; d:array1.1000,1.1000 of longint; list:array1.1000*1000,1.2 of longint;begin readln(n); for i:=1 To n do begin for j:=1 To n do read(mapI,J)

8、; readln; end; readln(sx,sy,px,py); for i:=1 To n do for j:=1 To n do di,i:=100000000; end; dsx,sy:=0; h:=0; t:=1; list1,1:=sx; list1,2:=sy; while h<t do begin inc(h); x:=listh,1; y:=listh,2; for k:=1 to 4 do begin x1:=x+fxk,1; y1:=y+fxk,2; if (x1>=1) and (x1<=n) and (y1>=1) and (y1<=

9、n) then if mapx1,y1='0' then if dx1,y1=maxnum then begin dx1,y1:=dx,y+1; inc(t); listt,1:=x1; listt,2:=y1; end end end; writeln(dpx,py);end.四、栅栏的木料问题描述：农民John准备建一个栅栏来围住他的牧场。他已经确定了栅栏的形状，但是他在木料方面有些问题。当地的杂货储存商扔给John一些木板，而John必须从这些木板中找出尽可能多所需的木料。 当然，John可以切木板。因此，一个9英尺的木板可以切成一个5英尺和一个4英尺的木料 (当然也能切

10、成3个3英尺的，等等)。John有一把梦幻之锯，因此他在切木料时，不会有木料的损失。 所需要的木料规格都已经给定，每种规格的木材最多需要1块（注意：如果给定的规格值相同，则也各要一块），当然也有可能某些规格的木料无法切出。数据输入：从文件fence.in中读入数据，文件的第1行是一个数 N (1 <= N <= 30), 表示提供的木板的数目，第2行到第N+1行（ 共N行）：每行包括一个整数，表示各个木板的长度。第N+2行是一个数 R (1 <= R <= 1023), 表示所需木料的数目，第N+3行到第N+R+3行（共 R行）：每行包括一个整数(1 <= ri

11、<= 128)表示所需木料的长度。数据输出：结果输出到 fence.out中，只有一行，一个数字，表示能切出的最多的所需木料的数目。当然，并不是任何时候都能切出所有所需木料。注意： 每种规格的木材只需要切一块，即使ri=rj 也看成是两种不同规格的木材，各需要一块。输入输出样例1：fence.in4304050251015161718192021252430fence.out7输入输出样例2fence.in25060445251525fence.out4解析： 先排序，然后进行预处理+深搜程序：var nr,nb,boardtot,trashtot,havedelay,left,righ

12、t,dfsid:longint; board:array1.30 of longint; rail,sum:array1.1024 of longint; okey:boolean;procedure swap(var a,b:longint); 交换var temp:longint;begin temp:=a; a:=b; b:=temp;end;procedure qsort(start,stop:longint); 快排var i,j,k:longint;begin if stop-start<=10 then begin 加优化 for i:=start to stop-1 do

13、 for j:=i+1 to stop do if raili>railj then swap(raili,railj);由小到大排序 exit; end; k:=rail(start+stop) div 2; i:=start; j:=stop; repeat while raili<k do inc(i); while railj>k do dec(j); if i<=j then begin swap(raili,railj); inc(i); dec(j); end; until i>j; if start<j then qsort(start,j)

14、; if stop>i then qsort(i,stop);end;procedure init;var i,j:longint;begin readln(nb); for i:=1 to nb do readln(boardi); for i:=1 to nb-1 do for j:=i+1 to nb do if boardi<boardj then swap(boardi,boardj); 由大到小排序 readln(nr); for i:=1 to nr do readln(raili); qsort(1,nr);end;procedure find(k,x:longin

15、t); 深搜var i,start:longint;begin if k=0 then begin 能够实现 okey:=true; exit; end; if havedelay>trashtot then exit; 排除不能实现的情况 if railk=railk+1 then start:=x else start:=1; 相同规格的木料 for i:=start to nb do if railk<=boardi then begin 能被裁出 dec(boardi,railk); 改变状态 if boardi<rail1 then inc(havedelay,bo

16、ardi); 浪费的木料 find(k-1,i); if boardi<rail1 then dec(havedelay,boardi); 恢复状态 inc(boardi,railk); if okey=true then exit; 退出 end;end;procedure solve;var i,k:longint;begin boardtot:=0; for i:=1 to nb do inc(boardtot,boardi); 木板总长度 sum1:=rail1; for i:=2 to nr do sumi:=sumi-1+raili; 记录1到i的需要木板的长度 right:

17、=nr; while railright>board1 do dec(right); 排除一定裁不出的木料 while sumright>boardtot do dec(right); 排除一定裁不出的连续的木料 left:=1; while railleft<boardleft do inc(left); dec(left); 能够用最长的木板可裁的木料数 k:=0; for i:=1 to nb do if boardi<rail1 then inc(k,boardi); 浪费的木料 while left<right do begin 类似二分 dfsid:=(le