《2012年信息学特长生测试题》由会员分享，可在线阅读，更多相关《2012年信息学特长生测试题（9页珍藏版）》请在金锄头文库上搜索。
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解析：由于马的顺序不变，就能看出符合无效而且又像深搜，就能用动归。方程： i-1 到 x 的
4、最优值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(x1) else inc(x2); bi:=x1; wi:=x2; end; for i:=1 to n
5、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,jmin then min:=fi,j; end; fi,j:=min; end; write(fk,n);end.三、营救问题描述：铁塔尼号遇险了！他发出了求救信号。距离最近的哥伦比亚号收到了讯息，时间就是生命，必须尽快赶到那里。通过侦测，哥伦比亚号获取了一张海洋图。这张图将海洋部分化成n*n个比较小的单位，其中用1标明
6、的是陆地，用0标明是海洋。当然，船只能在海洋上行驶，且船只能从一个格子，移到相邻的四个格子。为了尽快赶到出事地点，哥伦比亚号最少需要走多远的距离。数据输入：从文件save.in中读入数据，第一行为n,下面是一个n*n的0，1矩阵，表示海洋地图，最后一行为四个小于n的整数，分别表示哥伦比亚号和铁塔尼号的位置。数据输出：哥伦比亚号到铁塔尼号的最短距离，答案精确到整数。输入输出样例：save.in30011011001 1 3 3save.out4数据范围说明：N=1000。解析：广搜+标记, 也是基础题const fx:array1.4,1.2 of longint=(1,0),(-1,0),(0
7、,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); readln; end; readln(sx,sy,px,py); for i:=1 To n do for j:=1
8、To n do di,i:=100000000; end; dsx,sy:=0; h:=0; t:=1; list1,1:=sx; list1,2:=sy; while h=1) and (x1=1) and (y1=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准备建一个栅栏来围住他的牧场。他已经确定了栅栏的形状，但是他在木料方面
9、有些问题。当地的杂货储存商扔给John一些木板，而John必须从这些木板中找出尽可能多所需的木料。 当然，John可以切木板。因此，一个9英尺的木板可以切成一个5英尺和一个4英尺的木料 (当然也能切成3个3英尺的，等等)。John有一把梦幻之锯，因此他在切木料时，不会有木料的损失。 所需要的木料规格都已经给定，每种规格的木材最多需要1块（注意：如果给定的规格值相同，则也各要一块），当然也有可能某些规格的木料无法切出。数据输入：从文件fence.in中读入数据，文件的第1行是一个数 N (1 = N = 30), 表示提供的木板的数目，第2行到第N+1行（ 共N行）：每行包括一个整数，表示各个木
10、板的长度。第N+2行是一个数 R (1 = R = 1023), 表示所需木料的数目，第N+3行到第N+R+3行（共 R行）：每行包括一个整数(1 = ri = 128)表示所需木料的长度。数据输出：结果输出到 fence.out中，只有一行，一个数字，表示能切出的最多的所需木料的数目。当然，并不是任何时候都能切出所有所需木料。注意： 每种规格的木材只需要切一块，即使ri=rj 也看成是两种不同规格的木材，各需要一块。输入输出样例1：fence.in4304050251015161718192021252430fence.out7输入输出样例2fence.in25060445251525fen
11、ce.out4解析： 先排序，然后进行预处理+深搜程序：var nr,nb,boardtot,trashtot,havedelay,left,right,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:
12、longint;begin if stop-startrailj then swap(raili,railj);由小到大排序 exit; end; k:=rail(start+stop) div 2; i:=start; j:=stop; repeat while railik do dec(j); if ij; if starti 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 boardiboardj then swap(boardi,boardj
