信息学奥赛基础知识讲解（课堂PPT）

1、1辅导信息学奥赛的几点体会辅导信息学奥赛的几点体会2精心备课，突破疑点难点，追求直观高效。精心备课，突破疑点难点，追求直观高效。3 分析：分析：将十进数转换成二进制数将十进数转换成二进制数, ,一般采用除二取余法。一般采用除二取余法。如果用一个数组如果用一个数组b b来存放二进制数来存放二进制数, ,可以依次把所得的余数存可以依次把所得的余数存入入b0b0、b1b1、bn,bn,最后按最后按bnbn、bn-1bn-1、b1b1、b0b0的顺序输出这些余数的顺序输出这些余数, ,就得到了所求的二进制数。就得到了所求的二进制数。 1 1、读入一个十进制自然数，将其转换成二进制数后输出。、读入一个十

2、进制自然数，将其转换成二进制数后输出。4例如：例如：余数：余数：25252 212122 26 62 23 32 21 12 20 0输出结果为：输出结果为：11001110010 01 10 01 11 101234565var var i,j,n: i,j,n:longintlongint; ; b:array 0.31 of 0.1; b:array 0.31 of 0.1;beginbegin readln(n); readln(n); write(n,=(); write(n,=(); i:=0; i:=0; while while（ ）dodo begin begin （ ）; ;

3、 i:=i+1; i:=i+1; 指定下一个余数的存放位置指定下一个余数的存放位置 n:=n div 2 n:=n div 2 产生的商将作为新的被除数产生的商将作为新的被除数 end;end; for j:= for j:=（ ）do write(bj);do write(bj); writeln()2) writeln()2)end.end.n0n0 bi:=n mod 2bi:=n mod 2 i-1 downto 0i-1 downto 0 后进先出后进先出6Str1=3210Str2=98765a 0 1 2 3b 5 6 7 8 957911 01j对位对位相加相加进位进位2、高精

4、度加法、高精度加法7var str1,str2:string; a,b:array1.100 of 0.9; l1,l2,i,j,k:integer;begin readln(str1); readln(str2); l1:=length(str1); l2:=length(str2); if l1l2 then j:=l1 else j:=l2; k:=0; for i:=l1 downto 1 do begin k:=k+1; ak:=ord(str1i)-ord(0); end; k:=0; for i:=l2 downto 1 do begin k:=k+1; bk:=ord(str2

5、i)-ord(0); end; for i:=1 to j do begin ai:=ai+bi; if ai=10 then begin ai:=（ ）; ai+1:=（ ）; end; end; if ai+1=0 then j:=j-1; for i:=j+1 downto 1 do write(ai); writeln;end.处理进位处理进位从低位到高位依次从低位到高位依次将各位数相加将各位数相加用字符串形式输用字符串形式输入加数和被加数入加数和被加数ai-10ai+1+18 分析：分析：类似加法，可以用竖式求乘法。在做乘法运算时，类似加法，可以用竖式求乘法。在做乘法运算时，同样也有

6、进位，同时对每一位进行乘法运算时，必须进行错同样也有进位，同时对每一位进行乘法运算时，必须进行错位相加。位相加。8 4 8 2 3 2 5 4 4 1 6 9 61 9 5 0 43*8+0+0=24 c1=4x= aix= ai* *bj+ x div 10+ ci+j-1bj+ x div 10+ ci+j-1 ci+j-1= x mod 10ci+j-1= x mod 103*4+2+0=14 c2=43*8+1+0=25 c3=5 c4=22*8+0+4=20 c2=02*4+2+5=15 c3=52*8+1+2=19 c4=9 c5=13、高精度乘法、高精度乘法9var s1,s2:

7、string; a,b:array1.100of 0.9; c:array1.200of 0.9; la,lb,lc, i,j,x,y,z,w:integer;begin readln(s1); readln(s2); la:=length(s1); lb:=length(s2); lc:=la+lb; 积的位数为积的位数为la+lb-1或者或者la+lb； for i:=la downto 1 do ala-i+1:=ord(s1i)-ord(0); for i:=lb downto 1 do blb-i+1:=ord(s2i)-ord(0); for i:=lc downto 1 do c

8、i:=0; for i:=1 to la do begin x:=0; 上次乘积进位初始化上次乘积进位初始化 for j:=1 to lb do 对乘数的每一位进行处理对乘数的每一位进行处理 begin x:=ai*bj+x div 10+ci+j-1; ci+j-1:= x mod 10; end; ci+j:= x div 10; end; while (clc=0) and (lc1) do lc:=lc-1; for i:=lc downto 1 do write(ci); writeln;end.10varvar yh:array1.5,1.5of integer; yh:array

9、1.5,1.5of integer; i,j:integer; i,j:integer;beginbegin yh1,1:=1; yh1,1:=1; for i:=2 to 5 do for i:=2 to 5 do begin begin yhi,1:=1;yhi,i:=1; yhi,1:=1;yhi,i:=1; for j:= for j:=2 to i-12 to i-1 do do yhi,j:=yhi-1,j-1 + yhi-1,j;yhi,j:=yhi-1,j-1 + yhi-1,j; end; end; for i:=1 to 5 do for i:=1 to 5 do begi

10、n begin for j:=1 to i do write(yhi,j:3); writeln; for j:=1 to i do write(yhi,j:3); writeln; end; end;end.end.1111121133114644 4、阅读程序，写出运行结果。、阅读程序，写出运行结果。11 5、20012001年普及组、提高组初赛试题（穷举法）年普及组、提高组初赛试题（穷举法） 在在A、B两个城市之间设有两个城市之间设有N个路站个路站(如下图中的如下图中的S1，且且N100)，城市与城市与路站之间、路站和路站之间各有若干条路段路站之间、路站和路站之间各有若干条路段(各路段数

11、各路段数=20，且每条路段上，且每条路段上的距离均为一个整数的距离均为一个整数)。 A，B的一条通路是指：从的一条通路是指：从A出发，可经过任一路段到达出发，可经过任一路段到达S1，再从再从S1出出发经过任一路段，发经过任一路段，最后到达最后到达B。通路上路段距离之和称为通路距离通路上路段距离之和称为通路距离(最大距最大距离离=1000)。当所有的路段距离给出之后，求出所有不同距离的通路个数。当所有的路段距离给出之后，求出所有不同距离的通路个数(相相同距离仅记一次同距离仅记一次)。 例如：下图所示是当例如：下图所示是当N=1时的情况：时的情况： 从从A到到B的通路条数为的通路条数为6，但因其中

12、通路，但因其中通路5+5=4+6，所以满足条件的不同，所以满足条件的不同距离的通路条数为距离的通路条数为5。 数据结构：数据结构： N记录记录A，B间路站的个数；间路站的个数； 数组数组Di，0记录第记录第i-1个到第个到第i个路站间路段的个数个路站间路段的个数; Di，1，Di，2，记录每个路段的距离记录每个路段的距离; 数组数组G记录可取到的距离。记录可取到的距离。128645374 0 1 1 1 8+4+3=15 g15=10 1 1 2 8+4+4=16 g16=10 1 2 1 8+5+3=16 g16=10 1 2 2 8+5+4=17 g17=10 1 3 1 8+7+3=18

13、 g18=10 1 3 2 8+7+4=19 g19=10 2 1 1 6+4+3=13 g13=10 2 1 2 6+4+4=14 g14=10 2 2 1 6+5+3=14 g14=10 2 2 2 6+5+4=15 g15=10 2 3 1 6+7+3=16 g16=10 2 3 2 6+7+4=17 g17=1b0 b1 b2 b31 1 1 1 穷举结束穷举结束D1，0=2, D1，1=8, D1，2=6D2，0=3, D2，1=4, D2，2=5， D2，3=7D3，0=2, D3，1=3, D3，2=413var i,j,n,s:integer; b:array0.100 of

14、integer; d:array0.100,0.20 of integer; g:array0.1000 of 0.1;begin readln(n); for i:=1 to n+1 do begin readln(di,0); for j:=1 to di,0 do read(di,j); end; d0,0:=1; for i:=1 to n+1 do bi:=1; b0:=0; for i:=1 to 1000 do gi:=0; while( )do begin s:=0; for i:=1 to n+1 do s:=( ); gs:=1; j:=n+1; while( )do j:

15、=j-1; bj:=bj+1; for i:=j+1 to n+1 do bi:=1; end; s:=0; for i:=1 to 1000 do( ); writeln(s); readln;end.b01s+d i , bi bj=dj,0s:=s+gi穷举用穷举用循环开关循环开关求当前通求当前通路的距离路的距离统计不同的统计不同的通路条数通路条数作记录作记录产生一种产生一种新的方案新的方案14 要求在国际象棋棋盘上放置八个皇后，使她们不能互相攻击要求在国际象棋棋盘上放置八个皇后，使她们不能互相攻击，即任何两个皇后不能处在同一行、同一列、同一条线上。请找，即任何两个皇后不能处在同一行、同

16、一列、同一条线上。请找出所有的摆法。出所有的摆法。 分析：分析： 如果我们把如果我们把8*8的棋盘看成是一个平面直角坐标系，那么任意的棋盘看成是一个平面直角坐标系，那么任意两个皇后在平面上的坐标应同时满足以下三个条件：两个皇后在平面上的坐标应同时满足以下三个条件：两个皇后的横坐标不相等。两个皇后的横坐标不相等。两个皇后的纵坐标不相等。两个皇后的纵坐标不相等。两个皇后的横坐标之差的绝对值不等于纵坐标之差的绝对值。两个皇后的横坐标之差的绝对值不等于纵坐标之差的绝对值。 我们用数组我们用数组xixi来描述八个皇后在棋盘上的状态，来描述八个皇后在棋盘上的状态， xixi =j=j表表示在第示在第i i

17、行的第行的第j j列放置了一个皇后。列放置了一个皇后。IKIK当当IKIK时，时，XI XKXI XK当当IKIK时，时，| |I-K|XI-XK|I-K|XI-XK|6、八皇后问题八皇后问题（回溯法）（回溯法）15const n=8;var i,j,k:integer; x:array1.n of integer;function place(k:integer):boolean; var i:integer; begin place:=true; for i:=1 to k-1 do if ( ) or (abs(xi-xk)=abs(i-k) then( ) ; end;procedur

18、e print; var i:integer; begin for i:=1 to n do write(xi:4); writeln; end;procedure try(k:integer); var i:integer; begin if( )then begin print; exit end; for i:= 1 to n do begin ( ); if( )then try(k+1); end; end ;begin try(1);end.xi=xkk=n+1place:=falsexk:=iplace(k)16 如下图所示为一个数字三角形，请编程计算从顶到底的如下图所示为一个数

19、字三角形，请编程计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。（只要某处的一条路径，使该路径所经过的数字总和最大。（只要求输出总和）求输出总和） 规定：规定： 一步可沿左斜线向下或右斜线向下走；一步可沿左斜线向下或右斜线向下走； 图形行数小于等于图形行数小于等于100100； 三角形中的数字为三角形中的数字为0 0，1 1，99;99; 测试数据通过键盘逐行输入，如下图数据应以如下所示测试数据通过键盘逐行输入，如下图数据应以如下所示格式输入：格式输入：5 57 73 83 88 1 08 1 02 7 4 42 7 4 4 4 5 2 6 5 4 5 2 6 5 输出：输出：30

20、307 7、数字三角形（动态规划）、数字三角形（动态规划）17 逆推法逆推法: : 按三角形的行划分阶段，若行数为按三角形的行划分阶段，若行数为n n，则可把问题看做一个则可把问题看做一个n-1n-1个阶段的决策问题。先求出第个阶段的决策问题。先求出第n-1n-1阶段阶段( (第第n-1n-1行上各点行上各点) )到第到第n n行的最大和，再依次求出第行的最大和，再依次求出第n-2n-2阶段、第阶段、第n-3n-3阶段阶段第第1 1阶段阶段( (起始起始点点) )各决策点至第各决策点至第n n行的最大和。行的最大和。 设设fi,jfi,j为从第为从第i i阶段中的点阶段中的点j j至第至第n

21、n行的最大的数字和；行的最大的数字和； 则则fn,j=an,jfn,j=an,j（1=j=n1=j=n） fi,j= fi,j= maxmax ai,j+fi+1,j ai,j+fi+1,j , , ai,j+fi+1,j+1 ai,j+fi+1,j+1 （1=j=i1=jfi+1,j+1 then fi,j:=fi+1,j+ai,j if fi+1,jfi+1,j+1 then fi,j:=fi+1,j+ai,j else fi,j:=fi+1,j+1+ai,j; else fi,j:=fi+1,j+1+ai,j; writeln(f1,1); writeln(f1,1);end.end.阶

22、段阶段状状态态决策决策状态转移方程状态转移方程45265712 10 1020 13 1023 2130198 8、深度优先遍历、深度优先遍历 基本思想：基本思想：n第一步，从图中某个顶点第一步，从图中某个顶点V0出发，首先访问出发，首先访问V0；n第二步，找出刚访问过的顶点第二步，找出刚访问过的顶点Vi的第一个未被访问的邻接的第一个未被访问的邻接点，然后访问该顶点。以该顶点为新顶点，重复本步骤，点，然后访问该顶点。以该顶点为新顶点，重复本步骤，直到当前的顶点没有未被访问的邻接点为止；直到当前的顶点没有未被访问的邻接点为止；n第三步，返回前一个访问过的且仍有未被访问的邻接点的第三步，返回前一个

23、访问过的且仍有未被访问的邻接点的顶点，找出并访问该顶点的下一个未被访问的邻接点，然顶点，找出并访问该顶点的下一个未被访问的邻接点，然后执行第二步步骤；后执行第二步步骤；n若此时图中尚有顶点未访问，则另选图中一个未被访问的若此时图中尚有顶点未访问，则另选图中一个未被访问的顶点作起始点，重复第一步至第三步，直至图中所有顶点顶点作起始点，重复第一步至第三步，直至图中所有顶点都被访问到为止。都被访问到为止。20123754689ABDCEFGHI该图的深度优先搜索的输出序列为：该图的深度优先搜索的输出序列为：ABCFEGDHI以以F作为起始点，该图的深度作为起始点，该图的深度优先搜索的输出序列为：优先

24、搜索的输出序列为：FCBADGEHI 或或FCBADGHIE 或或FCBAEGDHI 或或FCBAEGHID 或或FCBEADGHI 或或FCBEGHIDA 或或FCBEGDAHI21 任取一个顶点加入生成树，然后对那些一个任取一个顶点加入生成树，然后对那些一个端点在生成树中，而另一个端点不在生成树中的端点在生成树中，而另一个端点不在生成树中的边进行排序，取权值最小的边，将它和另一个端边进行排序，取权值最小的边，将它和另一个端点加进生成树中。重复上述步骤直到所有顶点都点加进生成树中。重复上述步骤直到所有顶点都进入了生成树为止。进入了生成树为止。9、构造最小生成树的、构造最小生成树的prim算法

25、算法2212345616192133111418656121635第一步，第一步，U1，VU2,3,4,5,6，TE 第二步，第二步，U1,2，VU3,4,5,6，TE(1,2)第三步，第三步，U1,2,3，VU4,5,6，TE(1,2)，(2,3)第四步，第四步，U1,2,3,4，VU5,6，TE(1,2)，(2,3)，(2,4)第五步，第五步，U1,2,3,4,6，VU5，TE(1,2)，(2,3)，(2,4)，(2,6)第六步，第六步，U1,2,3,4,6,5，VU ，TE(1,2)，(2,3)，(2,4)，(2,6)，(4,5)4661151823第一步，第一步，U1，VU2,3,4,

26、5,6，TE 第二步，第二步，U1,2，VU3,4,5,6，TE(1,2)第三步，第三步，U1,2,3，VU4,5,6，TE(1,2)，(2,3)第四步，第四步，U1,2,3,4，VU5,6，TE(1,2)，(2,3)，(3,4)第五步，第五步，U1,2,3,4,6，VU5，TE(1,2)，(2,3)，(3,4)，(2,6)第六步，第六步，U1,2,3,4,6,5，VU ，TE(1,2)，(2,3)，(3,4)，(2,6)，(4,5)12163546115186说明：说明：最小生成树也不是唯一的最小生成树也不是唯一的1234561619213311141865624 所谓后缀表达式是指这样的一

27、种表达式：式中不再所谓后缀表达式是指这样的一种表达式：式中不再引入括号，运算符放在两个运算对象之后。所有计算按引入括号，运算符放在两个运算对象之后。所有计算按运算符出现的顺序，严格地由左而右进行，不再考虑运运算符出现的顺序，严格地由左而右进行，不再考虑运算符的优先规则。例如算符的优先规则。例如5 5* *（7-37-3）+9+9对应的后缀表达式对应的后缀表达式为为5 7 3 -5 7 3 -* *9 +9 +，其中每个操作数后都有一个空格。，其中每个操作数后都有一个空格。 输入：后缀表达式输入：后缀表达式a a 输出：表达式的值输出：表达式的值 1010、计算后缀表达式的值、计算后缀表达式的值

28、25分析：分析： 设后缀表达式串为设后缀表达式串为a a，操作数、中间结果和最终结果操作数、中间结果和最终结果都存放在栈都存放在栈S S中，中，S S的元素类型为实型。的元素类型为实型。 计算过程如下：由左向右处理计算过程如下：由左向右处理a a中的每一个字符。若中的每一个字符。若遇到一个操作数，就送入栈遇到一个操作数，就送入栈S S中保存；遇到一个操作符，中保存；遇到一个操作符，就从栈中取出栈顶的两个操作数进行计算，然后将计算就从栈中取出栈顶的两个操作数进行计算，然后将计算结果重新压入栈中。依次类推，直至表达式最后一个操结果重新压入栈中。依次类推，直至表达式最后一个操作符处理完毕，这时的栈顶

29、元素值即为最终计算结果。作符处理完毕，这时的栈顶元素值即为最终计算结果。 26表达式：表达式：5 7 3 - * 9 + top27表达式：表达式：5 7 3 - * 9 + top528表达式：表达式：5 7 3 - * 9 + top5729表达式：表达式：5 7 3 - * 9 + top57330表达式：表达式：5 7 3 - * 9 + top57331表达式：表达式：5 7 3 - * 9 + top573-=432表达式：表达式：5 7 3 - * 9 + top5433表达式：表达式：5 7 3 - * 9 + top5434表达式：表达式：5 7 3 - * 9 + top5

30、4*=2035表达式：表达式：5 7 3 - * 9 + top2036表达式：表达式：5 7 3 - * 9 + top20937表达式：表达式：5 7 3 - * 9 + top20938表达式：表达式：5 7 3 - * 9 + top209+=2939表达式：表达式：5 7 3 - * 9 + top2940type stack=record data:array1.100of real; top:0.100; end;var s:stack; i:integer; x:real; a:string; ch:char;function pop (var s:stack):real; 出

31、栈出栈 begin pop:=s.datas.top; s.top:=s.top-1; end;procedure push (var s:stack;x:real); 入栈入栈 begin s.top:=s.top+1; s.datas.top:=x; end;begin 主程序主程序 readln(a); s.top:=0; 置空栈置空栈41 i:=1; ch:=ai; while （ ）do begin case ch of 0.9: begin 取出操作数取出操作数 x:=0; while（ ） do begin x:=x*10+ord(ch)-ord(0); i:=i+1; ch:=

32、ai; end; end; + : x:=pop(s)+pop(s); - : begin x:=pop(s); x:=pop(s)-x; end; * : x:=pop(s)*pop(s); / : begin x:=pop(s); x:=pop(s)/x; end; end; （ ）; i:=i+1; ch:=ai; 继续扫描字符串继续扫描字符串a end; writeln( :0:0);end.i=length(a)ch push(s,x)pop(s)42 现有现有1 1g g、2g2g、3g3g、5g5g、10g10g、20g20g的砝码各若干枚，问用这些砝码可以称出多的砝码各若干枚，

33、问用这些砝码可以称出多少种不同的重量。（设砝码的总重不超过少种不同的重量。（设砝码的总重不超过10001000g g，且砝码只能放在天平的一端）且砝码只能放在天平的一端） 输入：输入：a1 a2 a3 a4 a5 a6a1 a2 a3 a4 a5 a6 （表示表示1 1g g砝码有砝码有a1a1个，个，2 2g g砝码有砝码有a2a2个，个，2020g g砝码有砝码有a6a6个）个） 输出：输出：total=ntotal=n （ n n表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）不用的情况） 如输入：如输入：1 1

34、 0 0 0 01 1 0 0 0 0 则输出：则输出：total=3total=3（表示可以称出表示可以称出1 1g g，2g2g，3g3g三种不同的重量）三种不同的重量） 由一个砝码也不取开始扩展结点，当扩展出的某一个结点所对应由一个砝码也不取开始扩展结点，当扩展出的某一个结点所对应的质量数在前面已经出现过时，则不再从该结点扩展下去，并删掉该结的质量数在前面已经出现过时，则不再从该结点扩展下去，并删掉该结点；如此重复，直到没有结点可扩展为止。统计扩展的结点总数，就可点；如此重复，直到没有结点可扩展为止。统计扩展的结点总数，就可得到可以称出的质量总数。得到可以称出的质量总数。1111、砝码称

35、重：、砝码称重：43constconst w:array1.6 of integer=(1,2,3,5,10,20); w:array1.6 of integer=(1,2,3,5,10,20);每种砝码的单位质量每种砝码的单位质量 maxweight=1000; maxweight=1000; 队列的最大长度队列的最大长度 type type tlist=array0.maxweight of record tlist=array0.maxweight of record we:integer;we:integer; 当前结点所对应砝码组合的总质量当前结点所对应砝码组合的总质量 sn: ar

36、ray1.6 of integer;sn: array1.6 of integer; 各砝码个数各砝码个数 end;end;var a:tlist; var a:tlist; 队列队列 s: array1.6 of integer; s: array1.6 of integer; 存放每种砝码的数量存放每种砝码的数量 b:array1.1000 of boolean; b:array1.1000 of boolean; 标记某个质量是否可被称出标记某个质量是否可被称出 i,i,head,tailhead,tail:integer; :integer; cw:integer; cw:intege

37、r;beginbegin for i:=1 to 6 do read(si);readln; for i:=1 to 6 do read(si);readln; 读入每种砝码的数量读入每种砝码的数量 fillchar(a,sizeof(a),0);fillchar(a,sizeof(a),0); fillchar(b,sizeof(b),0); fillchar(b,sizeof(b),0); 1 2 2 0 0 01 2 3 12 13 21 22 23 31 32 33 132 133 231 232 233 331 332 1332 2331 2332 13322 2332144 hea

38、d:=0; tail:=0; head:=0; tail:=0; 置队空置队空 whilewhile（ ）do do 还有结点可扩展还有结点可扩展, ,则执行循环体则执行循环体 begin begin for i:=1 to 6 do for i:=1 to 6 do 试探每种砝码试探每种砝码 if if （ ） 新组合可以得到新组合可以得到 then beginthen begin cw:=ahead.we+wi; cw cw:=ahead.we+wi; cw为新组合的总质量为新组合的总质量 ifif（ ）then begin then begin 入队入队 tail:=tail+1;tai

39、l:=tail+1;（ ） bcw:=true; bcw:=true;标记标记 atail.sn:=ahead.sn;atail.sn:=ahead.sn; （ ） end; end; end; end; （ ）; ; 出队出队 end;end; writeln(total=,tail); writeln(total=,tail); end.end.head=tailhead=tailahead.snisiahead.snisinot bcwnot bcwatail.we:=cw;atail.we:=cw;inc(atail.sni)inc(atail.sni)head:=head+1head

40、:=head+145多做老题，立足基本算法，引导一题多解。多做老题，立足基本算法，引导一题多解。穷举法、回溯法、动态规划穷举法、回溯法、动态规划46【问题描述】【问题描述】 金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行元钱就行”。今。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超

41、过妈妈限天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的定的N元。于是，他把每件物品规定了一个重要度，分为元。于是，他把每件物品规定了一个重要度，分为5等：用整数等：用整数15表示，第表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过元）。他希望在不超过N元（可以等于元（可以等于N元）的前提下，使每件物品的价元）的前提下，使每件物品的价格与重要度的乘积的总和最大。格与重要度的乘积的总和最大。 设第设第j件物品的价格为件物品的价格为vj，重要度为重要度为wj，共选中了共选中了k件物品，编件

42、物品，编号依次为号依次为j1，j2，jk，则所求的总和为：则所求的总和为： vj1*wj1+vj2*wj2+ +vjk*wjk 请你帮助金明设计一个满足要求的购物单。请你帮助金明设计一个满足要求的购物单。开心的金明开心的金明(2006年普及组复赛年普及组复赛)47【输入文件输入文件】 输入文件输入文件happy.in 的第的第1行，为两个正整数，用一个空格隔开：行，为两个正整数，用一个空格隔开：N m（其中其中N（30000）表示总钱数，表示总钱数，m（25）为希望购买物品的个数。）为希望购买物品的个数。） 从第从第2行到第行到第m+1行，第行，第j行给出了编号为行给出了编号为j-1的物品的基

43、本数据，每行有的物品的基本数据，每行有2个非负整数个非负整数v p（其中其中v表示该物品的价格表示该物品的价格(v=10000)，p表示该物品的重表示该物品的重要度要度(15)）【输出文件输出文件】 输出文件输出文件happy.out只有一个正整数，为不超过总钱数的物品的价格与只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（重要度乘积的总和的最大值（100000000）。）。【输入样例输入样例】 1000 5 1000 5 800 2 800 2 400 5 400 5 300 5 300 5 400 3 400 3 200 2 200 2【输出样例输出样例】 39004

44、8var v,p:array1.25 of integer; b:array0.25 of 0.1; n,m,i,j,max,s,yu,l:longint;begin readln(n,m); for i:=1 to m do readln(vi,pi); for i:=0 to m do bi:=0; while b0=0 do begin j:=m; while bj=1 do j:=j-1; bj:=1; for l:= j+1 to m do bl:=0; s:=0; yu:=0; for i:=1 to m do if (bi=1) then begin yu:=yu+vi; s:=

45、s+vi*pi; end; if (yumax) then max:=s; end; writeln(max);end.可以通过可以通过8个测试点个测试点1、用穷举法解、用穷举法解49 20012001年普及组、提高组初赛试题年普及组、提高组初赛试题 在在A、B两个城市之间设有两个城市之间设有N个路站个路站(如下图中的如下图中的S1，且且N100)，城市与城市与路站之间、路站和路站之间各有若干条路段路站之间、路站和路站之间各有若干条路段(各路段数各路段数=20，且每条路段上，且每条路段上的距离均为一个整数的距离均为一个整数)。 A，B的一条通路是指：从的一条通路是指：从A出发，可经过任一路段到

46、达出发，可经过任一路段到达S1，再从再从S1出出发经过任一路段，发经过任一路段，最后到达最后到达B。通路上路段距离之和称为通路距离通路上路段距离之和称为通路距离(最大距最大距离离=1000)。当所有的路段距离给出之后，求出所有不同距离的通路个数。当所有的路段距离给出之后，求出所有不同距离的通路个数(相相同距离仅记一次同距离仅记一次)。 例如：下图所示是当例如：下图所示是当N=1时的情况：时的情况： 从从A到到B的通路条数为的通路条数为6，但因其中通路，但因其中通路5+5=4+6，所以满足条件的不，所以满足条件的不同距离的通路条数为同距离的通路条数为5。 数据结构：数据结构： N记录记录A，B间

47、路站的个数；间路站的个数； 数组数组Di，0记录第记录第i-1个到第个到第i个路站间路段的个数个路站间路段的个数; Di，1，Di，2，记录每个路段的距离记录每个路段的距离; 数组数组G记录可取到的距离。记录可取到的距离。50var i,j,n,s:integer; b:array0.100 of integer; d:array0.100,0.20 of integer; g:array0.1000 of 0.1;begin readln(n); for i:=1 to n+1 do begin readln(di,0); for j:=1 to di,0 do read(di,j); en

48、d; d0,0:=1; for i:=1 to n+1 do bi:=1; b0:=0; for i:=1 to 1000 do gi:=0; while( )do begin s:=0; for i:=1 to n+1 do s:=( ); gs:=1; j:=n+1; while( )do j:=j-1; bj:=bj+1; for i:=j+1 to n+1 do bi:=1; end; s:=0; for i:=1 to 1000 do( ); writeln(s); readln;end.b01s+d i , bi bj=dj,0s:=s+gi51 将将2n个个0和和2n个个1，排成

49、一圈。从任一个位置开始，每次按逆时针的方向，排成一圈。从任一个位置开始，每次按逆时针的方向以长度为以长度为n+1的单位进行数二进制数。要求给出一种排法，用上面的方法产的单位进行数二进制数。要求给出一种排法，用上面的方法产生出来的生出来的2n+1个二进制数都不相同。例如，当个二进制数都不相同。例如，当n=2时，即时，即22个个0和和22个个1排成如排成如下一圈：下一圈： 比如，从比如，从A位置开始，逆时针方向取三个数位置开始，逆时针方向取三个数000，然后再从，然后再从B位置上开始位置上开始取三个数取三个数001，接着从，接着从C开始取三个数开始取三个数010，.可以得到可以得到000，001，

50、010，101，011，111，110，100共共8个二进制数且都不相同。个二进制数且都不相同。 程序说明：程序说明： 以以n=4为例，即有为例，即有16个个0，16个个1，数组，数组a用以记录用以记录32个个0，1的排法，数的排法，数组组b统计二进制数出现的可能性。统计二进制数出现的可能性。20002000年提高组初赛试题年提高组初赛试题52 var a:array1.36 of 0.1; b:array0.31 of integer; i,j,k,s,p:integer;begin for i:=1 to 36 do ai:=0; for i:=28 to 32 do ai:=1; p:=

51、1; a6:=1; for i:=1 to 32 do for j:=i to i+4 do write(aj); writeln end. while ( p=1 ) do begin j:=27 while aj=1 do j:=j-1; ( ) for i:=j+1 to 27 do ( ) for i:=0 to 31 do bi:=0; for i:=1 to 32 do begin( )for k:=i to i+4 do s:=s*2+ak; ( )end; s:=0; for i:=0 to 31 do s:=s+bi; if ( ) then p:=0 end;aj:=1ai

52、:=0s:=0bs:=1s=3253 将将n个整数分成个整数分成k组组(kn,要求每组不能为空要求每组不能为空),显然这显然这k个部分均可得个部分均可得到一个各自的和到一个各自的和s1,s2,sk,定义整数定义整数P为为: P=(S1-S2)2+(S1一一S3)2+(S1-Sk)2+(s2-s3)2+(Sk-1-Sk)2 问题求解问题求解: 求出一种分法求出一种分法,使使P为最小为最小(若有多种方案仅记一种。若有多种方案仅记一种。 程序说明程序说明: 数组数组:a1,a2,.an存放原数存放原数 s1,s2,.,sk存放每个部分的和存放每个部分的和 b1,b2,.,bn穷举用临时空间穷举用临时

53、空间 d1,d2,.,dn存放最佳方案存放最佳方案20022002年普及组初赛试题年普及组初赛试题54var i,j,n,k : integer; a :array 1.100 of integer; b,d:array 0.100 of integer; s :array1.30 of integer;begin readln(n,k); for i:=1 to n do read(ai); for i:=0 to n do bi:=1; cmin:=1000000; while (b0=1) do begin for i:=1 to k do ( ); for i:=1 to n do(

54、); sum:=0; for i:=1 to k-1 do for j:=( ) sum:=sum+(si-sj)*(si-sj); if( )then begin cmin:=sum; for i:=1 to n do di:=bi; end; j:=n; while( )j:=j-1; bj:=bj+1; for i:=j+1 to n do( ) end; writeln(cmin); for i:=1 to n write(di:40);end.si:=0sbi:=sbi+aii+1 to k docminsumbj=kbi:=155 有有n种基本物质种基本物质(n10),分别记为分别

55、记为P1,P2,Pn,用用n种基本物质构造物品种基本物质构造物品,这些物品使用在这些物品使用在k个不同地区个不同地区(k20),每个地区对物品提出自己的要求每个地区对物品提出自己的要求,这些要这些要求用一个求用一个n位的数表示位的数表示:12n,其中其中: i =1表示所需物质中必须有第表示所需物质中必须有第i种基本物质种基本物质 =-1表示所需物质中必须不能有第表示所需物质中必须不能有第i种基本物质种基本物质 =0无所谓无所谓 问题求解问题求解: 当当k个不同地区要求给出之后个不同地区要求给出之后,给出一种方案给出一种方案,指出哪些物质被使用指出哪些物质被使用,哪些物哪些物质不被使用。质不被

56、使用。 程序说明程序说明: 数组数组b1,b2,.,bnJ表示某种物品表示某种物品 a1.k,1.n记录记录k个地区对物品的要求个地区对物品的要求,其中其中: ai,j=1表示第表示第i个地区对第个地区对第j种物品是需要的种物品是需要的 ai,j=0表示第表示第i个地区对第个地区对第j种物品是无所谓的种物品是无所谓的 ai,j=-1表示第表示第i个地区对第个地区对第j种物品是不需要的种物品是不需要的20022002年提高组初赛试题年提高组初赛试题56var i, j ,k, n :integer; p:boolean; b :array 0.20 of 0.1; a :array1.20,1.

57、10d integer;begin readln(n,k); for i:=1 to k do begin for j:=1 to n do read(ai,j); readln; end; for i:=0 to n do bi:=0; p:=true; while( )do begin j:=n; while bj=1 do j:=j-1; ( ); for i:=j+1 to n do bi:=0; ( ); for i:=1 to k do for j :=1 to n do if(ai,j=1)and(bj=0)or( ) then p:=true; end; if( )then w

58、riteln(找不到!) else for i:=1 to n do if (bi=1) then writeln(物质,i,需要) else writeln(物质,i,不需要);end.p and (b0=0) bj:=1 p:=false (ai,j=-1)and(bj=1) p 57 一个正整数（非素数）可以表示成它的因子（一个正整数（非素数）可以表示成它的因子（1与其本身除外）的与其本身除外）的乘 积 。 例 如 ：乘 积 。 例 如 ： 1 2 有 因 子有 因 子 2 ， 2 ， 3 ， 4 ， 6 ， 所 以 可 表 示 为 ：， 所 以 可 表 示 为 ：12=2*2*3=4*

59、3=2*6 给出任一个整数给出任一个整数n，求出它所有的因子乘积表达式（交换律得出的求出它所有的因子乘积表达式（交换律得出的不同式子算同一种）。不同式子算同一种）。 算法说明：算法说明：读入一个整数读入一个整数n，首先求出它的所有的因子以及每个因首先求出它的所有的因子以及每个因子可能的次数。子可能的次数。 例如：整数例如：整数48 因子：因子：2 3 4 6 8 12 16 24 次数：次数：4 1 2 1 1 1 1 1 将上面的结果存入二维数组将上面的结果存入二维数组a中，其中：中，其中：ai，1表示因子；表示因子；ai，2表表示次数。然后用穷举法求出所有可能的表示：示次数。然后用穷举法求

60、出所有可能的表示： 数组数组b记录取数情况；记录取数情况； 数组数组c工作单元。工作单元。19971997年普及组、提高组初赛试题年普及组、提高组初赛试题58var var a:array0.20,1.2 of integer; a:array0.20,1.2 of integer; c,b:array0.20 of integer; c,b:array0.20 of integer; n,m,i,j,s,k,l:integer; n,m,i,j,s,k,l:integer;beginbegin readln(n); readln(n); for i:=1 to 20 do ai,1:=0;