信息学奥赛基础知识讲解

信息学奥赛基础知识讲解第一页，共一百一十三页，2022年，8月28日精心备课，突破疑点难点，追求直观高效。第二页，共一百一十三页，2022年，8月28日

分析：将十进数转换成二进制数,一般采用除二取余法。如果用一个数组b来存放二进制数,可以依次把所得的余数存入b[0]、b[1]、…、b[n],最后按b[n]、b[n-1]、…、b[1]、b[0]的顺序输出这些余数,就得到了所求的二进制数。

1、读入一个十进制自然数，将其转换成二进制数后输出。第三页，共一百一十三页，2022年，8月28日例如：余数：2521226232120输出结果为：11001010110123456第四页，共一百一十三页，2022年，8月28日vari,j,n:longint;b:array[0..31]of0..1;beginreadln(n);write(n,'=(');i:=0;while（）dobegin（）;i:=i+1;{指定下一个余数的存放位置}

n:=ndiv2{产生的商将作为新的被除数}

end;forj:=（）dowrite(b[j]);writeln(')2')end.n<>0

b[i]:=nmod2

i-1downto0

后进先出第五页，共一百一十三页，2022年，8月28日Str1=‘3210’Str2=‘98765’a0123b567895791101j对位相加进位2、高精度加法第六页，共一百一十三页，2022年，8月28日varstr1,str2:string;a,b:array[1..100]of0..9;l1,l2,i,j,k:integer;beginreadln(str1);readln(str2);

l1:=length(str1);l2:=length(str2);ifl1>l2thenj:=l1elsej:=l2;

k:=0;fori:=l1downto1dobegink:=k+1;a[k]:=ord(str1[i])-ord('0');end;

k:=0;fori:=l2downto1dobegink:=k+1;b[k]:=ord(str2[i])-ord('0');end;fori:=1tojdobegina[i]:=a[i]+b[i];

ifa[i]>=10thenbegin

a[i]:=（）;a[i+1]:=（）;end;end;ifa[i+1]=0thenj:=j-1;fori:=j+1downto1dowrite(a[i]);

writeln;end.处理进位从低位到高位依次将各位数相加用字符串形式输入加数和被加数a[i]-10a[i+1]+1第七页，共一百一十三页，2022年，8月28日

分析：类似加法，可以用竖式求乘法。在做乘法运算时，同样也有进位，同时对每一位进行乘法运算时，必须进行错位相加。84823×25441696195043*8+0+0=24c[1]=4x=a[i]*b[j]+xdiv10+c[i+j-1]

c[i+j-1]=xmod103*4+2+0=14c[2]=43*8+1+0=25c[3]=5

c[4]=22*8+0+4=20c[2]=02*4+2+5=15c[3]=52*8+1+2=19c[4]=9

c[5]=13、高精度乘法第八页，共一百一十三页，2022年，8月28日vars1,s2:string;a,b:array[1..100]of0..9;c:array[1..200]of0..9;la,lb,lc,i,j,x,y,z,w:integer;beginreadln(s1);readln(s2);la:=length(s1);lb:=length(s2);lc:=la+lb;{积的位数为la+lb-1或者la+lb；}fori:=ladownto1doa[la-i+1]:=ord(s1[i])-ord('0');fori:=lbdownto1dob[lb-i+1]:=ord(s2[i])-ord('0');fori:=lcdownto1doc[i]:=0;fori:=1toladobeginx:=0;{上次乘积进位初始化}

forj:=1tolbdo{对乘数的每一位进行处理}

beginx:=a[i]*b[j]+xdiv10+c[i+j-1];c[i+j-1]:=xmod10;end;c[i+j]:=xdiv10;end;while(c[lc]=0)and(lc>1)dolc:=lc-1;

fori:=lcdownto1dowrite(c[i]);writeln;end.第九页，共一百一十三页，2022年，8月28日varyh:array[1..5,1..5]ofinteger;i,j:integer;beginyh[1,1]:=1;fori:=2to5dobeginyh[i,1]:=1;yh[i,i]:=1;forj:=2toi-1do

yh[i,j]:=yh[i-1,j-1]+yh[i-1,j];end;fori:=1to5dobeginforj:=1toidowrite(yh[i,j]:3);

writeln;end;end.1111121133114644、阅读程序，写出运行结果。第十页，共一百一十三页，2022年，8月28日5、2001年普及组、提高组初赛试题（穷举法）在A、B两个城市之间设有N个路站(如下图中的S1，且N<100)，城市与路站之间、路站和路站之间各有若干条路段(各路段数<=20，且每条路段上的距离均为一个整数)。

A，B的一条通路是指：从A出发，可经过任一路段到达S1，再从S1出发经过任一路段，…最后到达B。通路上路段距离之和称为通路距离(最大距离<=1000)。当所有的路段距离给出之后，求出所有不同距离的通路个数(相同距离仅记一次)。

例如：下图所示是当N=1时的情况：从A到B的通路条数为6，但因其中通路5+5=4+6，所以满足条件的不同距离的通路条数为5。

数据结构：N记录A，B间路站的个数；

数组D[i，0]记录第i-1个到第i个路站间路段的个数;

D[i，1]，D[i，2]，…，记录每个路段的距离;

数组G记录可取到的距离。第十一页，共一百一十三页，2022年，8月28日864537401118+4+3=15g[15]=101128+4+4=16g[16]=101218+5+3=16g[16]=101228+5+4=17g[17]=101318+7+3=18g[18]=101328+7+4=19g[19]=102116+4+3=13g[13]=102126+4+4=14g[14]=102216+5+3=14g[14]=102226+5+4=15g[15]=102316+7+3=16g[16]=102326+7+4=17g[17]=1b[0]b[1]b[2]b[3]1111穷举结束D[1，0]=2,D[1，1]=8,D[1，2]=6D[2，0]=3,D[2，1]=4,D[2，2]=5，

D[2，3]=7D[3，0]=2,D[3，1]=3,D[3，2]=4第十二页，共一百一十三页，2022年，8月28日vari,j,n,s:integer;

b:array[0..100]ofinteger;

d:array[0..100,0..20]ofinteger;

g:array[0..1000]of0..1;

begin

readln(n);

fori:=1ton+1do

begin

readln(d[i,0]);

forj:=1tod[i,0]doread(d[i,j]);

end;

d[0,0]:=1;

fori:=1ton+1dob[i]:=1;

b[0]:=0;

fori:=1to1000dog[i]:=0;while()do

begin

s:=0;

fori:=1ton+1do

s:=();

g[s]:=1;

j:=n+1;

while()doj:=j-1;

b[j]:=b[j]+1;

fori:=j+1ton+1dob[i]:=1;

end;

s:=0;

fori:=1to1000do();

writeln(s);readln;

end.b[0]<>1s+d[i,b[i]]b[j]=d[j,0]s:=s+g[i]穷举用循环开关求当前通路的距离统计不同的通路条数作记录产生一种新的方案第十三页，共一百一十三页，2022年，8月28日要求在国际象棋棋盘上放置八个皇后，使她们不能互相攻击，即任何两个皇后不能处在同一行、同一列、同一条线上。请找出所有的摆法。分析：

如果我们把8*8的棋盘看成是一个平面直角坐标系，那么任意两个皇后在平面上的坐标应同时满足以下三个条件：⑴两个皇后的横坐标不相等。⑵两个皇后的纵坐标不相等。⑶两个皇后的横坐标之差的绝对值不等于纵坐标之差的绝对值。

我们用数组x[i]来描述八个皇后在棋盘上的状态，x[i]

=j表示在第i行的第j列放置了一个皇后。I≠K当I≠K时，X[I]≠X[K]当I≠K时，|I-K|≠|X[I]-X[K]|6、八皇后问题（回溯法）第十四页，共一百一十三页，2022年，8月28日constn=8;

vari,j,k:integer;

x:array[1..n]ofinteger;

functionplace(k:integer):boolean;

vari:integer;

begin

place:=true;

fori:=1tok-1do

if()or(abs(x[i]-x[k])=abs(i-k))then()

;

end;

procedureprint;

vari:integer;

begin

fori:=1tondowrite(x[i]:4);

writeln;

end;proceduretry(k:integer);

vari:integer;

begin

if()thenbeginprint;exitend;

fori:=1tondo

begin

();

if()thentry(k+1);

end;

end;

begin

try(1);

end.x[i]=x[k]k=n+1place:=falsex[k]:=iplace(k)第十五页，共一百一十三页，2022年，8月28日如下图所示为一个数字三角形，请编程计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。（只要求输出总和）规定：⑴一步可沿左斜线向下或右斜线向下走；⑵图形行数小于等于100；⑶三角形中的数字为0，1，…，99;测试数据通过键盘逐行输入，如下图数据应以如下所示格式输入：5738810274445265输出：307、数字三角形（动态规划）第十六页，共一百一十三页，2022年，8月28日

逆推法:按三角形的行划分阶段，若行数为n，则可把问题看做一个n-1个阶段的决策问题。先求出第n-1阶段(第n-1行上各点)到第n行的最大和，再依次求出第n-2阶段、第n-3阶段…第1阶段(起始点)各决策点至第n行的最大和。设f[i,j]为从第i阶段中的点j至第n行的最大的数字和；则f[n,j]=a[n,j]（1<=j<=n）

f[i,j]=max{a[i,j]+f[i+1,j],a[i,j]+f[i+1,j+1]}（1<=j<=i）

f[1,1]即为所求。第十七页，共一百一十三页，2022年，8月28日constmaxn=100;varn,i,j:integer;a:array[1..maxn,1..maxn]ofinteger;f:array[1..maxn,1..maxn]ofinteger;beginreadln(n);fori:=1tondoforj:=1toidoread(a[i,j]);

fori:=1tondof[n,i]:=a[n,i];fori:=n-1downto1doforj:=1toido

iff[i+1,j]>f[i+1,j+1]thenf[i,j]:=f[i+1,j]+a[i,j]elsef[i,j]:=f[i+1,j+1]+a[i,j];

writeln(f[1,1]);end.阶段状态决策状态转移方程452657121010201310232130第十八页，共一百一十三页，2022年，8月28日8、深度优先遍历基本思想：第一步，从图中某个顶点V0出发，首先访问V0；第二步，找出刚访问过的顶点Vi的第一个未被访问的邻接点，然后访问该顶点。以该顶点为新顶点，重复本步骤，直到当前的顶点没有未被访问的邻接点为止；第三步，返回前一个访问过的且仍有未被访问的邻接点的顶点，找出并访问该顶点的下一个未被访问的邻接点，然后执行第二步步骤；若此时图中尚有顶点未访问，则另选图中一个未被访问的顶点作起始点，重复第一步至第三步，直至图中所有顶点都被访问到为止。第十九页，共一百一十三页，2022年，8月28日123754689ABDCEFGHI该图的深度优先搜索的输出序列为：ABCFEGDHI以F作为起始点，该图的深度优先搜索的输出序列为：FCBADGEHI或FCBADGHIE或FCBAEGDHI或FCBAEGHID或FCBEADGHI或FCBEGHIDA或FCBEGDAHI第二十页，共一百一十三页，2022年，8月28日任取一个顶点加入生成树，然后对那些一个端点在生成树中，而另一个端点不在生成树中的边进行排序，取权值最小的边，将它和另一个端点加进生成树中。重复上述步骤直到所有顶点都进入了生成树为止。9、构造最小生成树的prim算法第二十一页，共一百一十三页，2022年，8月28日12345616192133111418656121635第一步，U＝{1}，V－U＝{2,3,4,5,6}，TE＝第二步，U＝{1,2}，V－U＝{3,4,5,6}，TE＝{(1,2)}第三步，U＝{1,2,3}，V－U＝{4,5,6}，TE＝{(1,2)，(2,3)}第四步，U＝{1,2,3,4}，V－U＝{5,6}，TE＝{(1,2)，(2,3)，(2,4)}第五步，U＝{1,2,3,4,6}，V－U＝{5}，TE＝{(1,2)，(2,3)，(2,4)，(2,6)}第六步，U＝{1,2,3,4,6,5}，V－U＝，TE＝{(1,2)，(2,3)，(2,4)，(2,6)，(4,5)}46611518第二十二页，共一百一十三页，2022年，8月28日第一步，U＝{1}，V－U＝{2,3,4,5,6}，TE＝第二步，U＝{1,2}，V－U＝{3,4,5,6}，TE＝{(1,2)}第三步，U＝{1,2,3}，V－U＝{4,5,6}，TE＝{(1,2)，(2,3)}第四步，U＝{1,2,3,4}，V－U＝{5,6}，TE＝{(1,2)，(2,3)，(3,4)}第五步，U＝{1,2,3,4,6}，V－U＝{5}，TE＝{(1,2)，(2,3)，(3,4)，(2,6)}第六步，U＝{1,2,3,4,6,5}，V－U＝，TE＝{(1,2)，(2,3)，(3,4)，(2,6)，(4,5)}12163546115186说明：最小生成树也不是唯一的12345616192133111418656第二十三页，共一百一十三页，2022年，8月28日所谓后缀表达式是指这样的一种表达式：式中不再引入括号，运算符放在两个运算对象之后。所有计算按运算符出现的顺序，严格地由左而右进行，不再考虑运算符的优先规则。例如5*（7-3）+9对应的后缀表达式为573-*9+，其中每个操作数后都有一个空格。输入：后缀表达式a

输出：表达式的值10、计算后缀表达式的值第二十四页，共一百一十三页，2022年，8月28日分析：

设后缀表达式串为a，操作数、中间结果和最终结果都存放在栈S中，S的元素类型为实型。计算过程如下：由左向右处理a中的每一个字符。若遇到一个操作数，就送入栈S中保存；遇到一个操作符，就从栈中取出栈顶的两个操作数进行计算，然后将计算结果重新压入栈中。依次类推，直至表达式最后一个操作符处理完毕，这时的栈顶元素值即为最终计算结果。第二十五页，共一百一十三页，2022年，8月28日表达式：573-*9+top第二十六页，共一百一十三页，2022年，8月28日表达式：573-*9+top5第二十七页，共一百一十三页，2022年，8月28日表达式：573-*9+top57第二十八页，共一百一十三页，2022年，8月28日表达式：573-*9+top573第二十九页，共一百一十三页，2022年，8月28日表达式：573-*9+top573第三十页，共一百一十三页，2022年，8月28日表达式：573-*9+top573-=4第三十一页，共一百一十三页，2022年，8月28日表达式：573-*9+top54第三十二页，共一百一十三页，2022年，8月28日表达式：573-*9+top54第三十三页，共一百一十三页，2022年，8月28日表达式：573-*9+top54*=20第三十四页，共一百一十三页，2022年，8月28日表达式：573-*9+top20第三十五页，共一百一十三页，2022年，8月28日表达式：573-*9+top209第三十六页，共一百一十三页，2022年，8月28日表达式：573-*9+top209第三十七页，共一百一十三页，2022年，8月28日表达式：573-*9+top209+=29第三十八页，共一百一十三页，2022年，8月28日表达式：573-*9+top29第三十九页，共一百一十三页，2022年，8月28日typestack=recorddata:array[1..100]ofreal;top:0..100;end;vars:stack;i:integer;x:real;a:string;ch:char;functionpop(vars:stack):real;{出栈}

beginpop:=s.data[s.top];s.top:=s.top-1;end;procedurepush(vars:stack;x:real);{入栈}

begins.top:=s.top+1;s.data[s.top]:=x;end;begin{主程序}

readln(a);s.top:=0;{置空栈}第四十页，共一百一十三页，2022年，8月28日

i:=1;ch:=a[i];while（）dobegin

casechof‘0’..‘9’:begin{取出操作数}

x:=0;while（）dobeginx:=x*10+ord(ch)-ord('0');i:=i+1;ch:=a[i];end;end;'+‘:x:=pop(s)+pop(s);‘-’:beginx:=pop(s);x:=pop(s)-x;end;'*‘:x:=pop(s)*pop(s);‘/’:beginx:=pop(s);x:=pop(s)/x;end;end;（）;i:=i+1;ch:=a[i];{继续扫描字符串a}end;writeln(:0:0);end.i<=length(a)ch<>''push(s,x)pop(s)第四十一页，共一百一十三页，2022年，8月28日

现有1g、2g、3g、5g、10g、20g的砝码各若干枚，问用这些砝码可以称出多少种不同的重量。（设砝码的总重不超过1000g，且砝码只能放在天平的一端）输入：a1a2a3a4a5a6（表示1g砝码有a1个，2g砝码有a2个，…，20g砝码有a6个）输出：total=n（n表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）如输入：110000则输出：total=3（表示可以称出1g，2g，3g三种不同的重量）

由一个砝码也不取开始扩展结点，当扩展出的某一个结点所对应的质量数在前面已经出现过时，则不再从该结点扩展下去，并删掉该结点；如此重复，直到没有结点可扩展为止。统计扩展的结点总数，就可得到可以称出的质量总数。11、砝码称重：第四十二页，共一百一十三页，2022年，8月28日constw:array[1..6]ofinteger=(1,2,3,5,10,20);{每种砝码的单位质量}

maxweight=1000;{队列的最大长度}typetlist=array[0..maxweight]ofrecord

we:integer;{当前结点所对应砝码组合的总质量}

sn:array[1..6]ofinteger;{各砝码个数}

end;vara:tlist;{队列}

s:array[1..6]ofinteger;{存放每种砝码的数量}

b:array[1..1000]ofboolean;{标记某个质量是否可被称出}

i,head,tail:integer;cw:integer;beginfori:=1to6doread(s[i]);readln;{读入每种砝码的数量}

fillchar(a,sizeof(a),0);fillchar(b,sizeof(b),0);1220001231213212223313233132133231

2322333313321332233123321332223321第四十三页，共一百一十三页，2022年，8月28日

head:=0;tail:=0;{置队空}

while（）do{还有结点可扩展,则执行循环体}

beginfori:=1to6do{试探每种砝码}

if（）{新组合可以得到}

thenbegincw:=a[head].we+w[i];{cw为新组合的总质量}

if（）thenbegin{入队}

tail:=tail+1;（）b[cw]:=true;{标记}

a[tail].sn:=a[head].sn;（）end;end;

（）;{出队}

end;writeln('total=',tail);end.head<=taila[head].sn[i]<s[i]notb[cw]a[tail].we:=cw;inc(a[tail].sn[i])head:=head+1第四十四页，共一百一十三页，2022年，8月28日多做老题，立足基本算法，引导一题多解。穷举法、回溯法、动态规划第四十五页，共一百一十三页，2022年，8月28日【问题描述】金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：

v[j1]*w[j1]+v[j2]*w[j2]+…+v[jk]*w[jk]请你帮助金明设计一个满足要求的购物单。开心的金明(2006年普及组复赛)第四十六页，共一百一十三页，2022年，8月28日【输入文件】输入文件happy.in的第1行，为两个正整数，用一个空格隔开：Nm（其中N（<30000）表示总钱数，m（<25）为希望购买物品的个数。）从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整数vp（其中v表示该物品的价格(v<=10000)，p表示该物品的重要度(1~5)）【输出文件】输出文件happy.out只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<100000000）。【输入样例】1000580024005300540032002【输出样例】3900第四十七页，共一百一十三页，2022年，8月28日varv,p:array[1..25]ofinteger;b:array[0..25]of0..1;n,m,i,j,max,s,yu,l:longint;beginreadln(n,m);fori:=1tomdoreadln(v[i],p[i]);fori:=0tomdob[i]:=0;whileb[0]=0dobegin

j:=m;whileb[j]=1doj:=j-1;

b[j]:=1;

forl:=j+1tomdob[l]:=0;s:=0;yu:=0;fori:=1tomdoif(b[i]=1)thenbeginyu:=yu+v[i];s:=s+v[i]*p[i];end;if(yu<=n)and(s>max)thenmax:=s;end;writeln(max);end.可以通过8个测试点1、用穷举法解第四十八页，共一百一十三页，2022年，8月28日

2001年普及组、提高组初赛试题在A、B两个城市之间设有N个路站(如下图中的S1，且N<100)，城市与路站之间、路站和路站之间各有若干条路段(各路段数<=20，且每条路段上的距离均为一个整数)。

A，B的一条通路是指：从A出发，可经过任一路段到达S1，再从S1出发经过任一路段，…最后到达B。通路上路段距离之和称为通路距离(最大距离<=1000)。当所有的路段距离给出之后，求出所有不同距离的通路个数(相同距离仅记一次)。

例如：下图所示是当N=1时的情况：从A到B的通路条数为6，但因其中通路5+5=4+6，所以满足条件的不同距离的通路条数为5。

数据结构：N记录A，B间路站的个数；

数组D[i，0]记录第i-1个到第i个路站间路段的个数;

D[i，1]，D[i，2]，…，记录每个路段的距离;

数组G记录可取到的距离。第四十九页，共一百一十三页，2022年，8月28日vari,j,n,s:integer;

b:array[0..100]ofinteger;

d:array[0..100,0..20]ofinteger;

g:array[0..1000]of0..1;

begin

readln(n);

fori:=1ton+1do

begin

readln(d[i,0]);

forj:=1tod[i,0]doread(d[i,j]);

end;

d[0,0]:=1;

fori:=1ton+1dob[i]:=1;

b[0]:=0;

fori:=1to1000dog[i]:=0;while()do

begin

s:=0;

fori:=1ton+1do

s:=();

g[s]:=1;

j:=n+1;

while()doj:=j-1;

b[j]:=b[j]+1;

fori:=j+1ton+1dob[i]:=1;

end;

s:=0;

fori:=1to1000do();

writeln(s);readln;

end.b[0]<>1s+d[i,b[i]]b[j]=d[j,0]s:=s+g[i]第五十页，共一百一十三页，2022年，8月28日

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

程序说明：以n=4为例，即有16个0，16个1，数组a用以记录32个0，1的排法，数组b统计二进制数出现的可能性。2000年提高组初赛试题第五十一页，共一百一十三页，2022年，8月28日var

a:array[1..36]of0..1;

b:array[0..31]ofinteger;

i,j,k,s,p:integer;

begin

fori:=1to36doa[i]:=0;

fori:=28to32doa[i]:=1;

p:=1;a[6]:=1;

fori:=1to32doforj:=itoi+4dowrite(a[j]);writeln

end.while(p=1)do

begin

j:=27

whilea[j]=1doj:=j-1;

()

fori:=j+1to27do()

fori:=0to31dob[i]:=0;

fori:=1to32do

begin

()

fork:=itoi+4dos:=s*2+a[k];

()

end;

s:=0;

fori:=0to31dos:=s+b[i];

if()thenp:=0

end;a[j]:=1a[i]:=0s:=0b[s]:=1s=32第五十二页，共一百一十三页，2022年，8月28日

将n个整数分成k组(k≤n,要求每组不能为空),显然这k个部分均可得到一个各自的和s1,s2,……,sk,定义整数P为:

P=(S1-S2)2+(S1一S3)2+……+(S1-Sk)2+(s2-s3)2+……+(Sk-1-Sk)2

问题求解:求出一种分法,使P为最小(若有多种方案仅记一种〉。程序说明:

数组:a[1],a[2],...a[n]存放原数s[1],s[2],...,s[k]存放每个部分的和b[1],b[2],...,b[n]穷举用临时空间d[1],d[2],...,d[n]存放最佳方案2002年普及组初赛试题第五十三页，共一百一十三页，2022年，8月28日vari,j,n,k:integer;a:array[1..100]ofinteger;b,d:array[0..100]ofinteger;s:array[1..30]ofinteger;beginreadln(n,k);fori:=1tondoread(a[i]);fori:=0tondob[i]:=1;cmin:=1000000;while(b[0]=1)do

beginfori:=1tokdo();

fori:=1tondo();

sum:=0;fori:=1tok-1doforj:=()

sum:=sum+(s[i]-s[j])*(s[i]-s[j]);

if()thenbegincmin:=sum;

fori:=1tondod[i]:=b[i];end;

j:=n;while()j:=j-1;b[j]:=b[j]+1;fori:=j+1tondo()end;writeln(cmin);fori:=1tonwrite(d[i]:40);end.s[i]:=0s[b[i]]:=s[b[i]]+a[i]i+1tokdocmin>sumb[j]=kb[i]:=1第五十四页，共一百一十三页，2022年，8月28日有n种基本物质(n≤10),分别记为P1,P2,……,Pn,用n种基本物质构造物品,这些物品使用在k个不同地区(k≤20),每个地区对物品提出自己的要求,这些要求用一个n位的数表示:α1α2……αn,其中:αi=1表示所需物质中必须有第i种基本物质=-1表示所需物质中必须不能有第i种基本物质=0无所谓问题求解:

当k个不同地区要求给出之后,给出一种方案,指出哪些物质被使用,哪些物质不被使用。

程序说明:

数组b[1],b[2],...,b[nJ表示某种物品a[1..k,1..n]记录k个地区对物品的要求,其中:a[i,j]=1表示第i个地区对第j种物品是需要的a[i,j]=0表示第i个地区对第j种物品是无所谓的a[i,j]=-1表示第i个地区对第j种物品是不需要的2002年提高组初赛试题第五十五页，共一百一十三页，2022年，8月28日vari,j,k,n:integer;p:boolean;b:array[0..20]of0..1;a:array[1..20,1..10]dinteger;beginreadln(n,k);fori:=1tokdobeginforj:=1tondoread(a[i,j]);readln;end;fori:=0tondob[i]:=0;p:=true;while()dobegin

j:=n;whileb[j]=1doj:=j-1;();fori:=j+1tondob[i]:=0;

();fori:=1tokdoforj:=1tondoif(a[i,j]=1)and(b[j]=0)or()thenp:=true;end;if()thenwriteln('找不到!‘)elsefori:=1tondoif(b[i]=1)thenwriteln('物质',i,’需要')elsewriteln('物质',i,'不需要');end.pand(b[0]=0)b[j]:=1p:=false(a[i,j]=-1)and(b[j]=1)p第五十六页，共一百一十三页，2022年，8月28日

一个正整数（非素数）可以表示成它的因子（1与其本身除外）的乘积。例如：12有因子2，2，3，4，6，所以可表示为：12=2*2*3=4*3=2*6给出任一个整数n，求出它所有的因子乘积表达式（交换律得出的不同式子算同一种）。

算法说明：读入一个整数n，首先求出它的所有的因子以及每个因子可能的次数。例如：整数48因子：23468121624次数：41211111将上面的结果存入二维数组a中，其中：a[i，1]表示因子；a[i，2]表示次数。然后用穷举法求出所有可能的表示：数组b记录取数情况； 数组c工作单元。1997年普及组、提高组初赛试题第五十七页，共一百一十三页，2022年，8月28日vara:array[0..20,1..2]ofinteger;c,b:array[0..20]ofinteger;n,m,i,j,s,k,l:integer;beginreadln(n);fori:=1to20doa[i,1]:=0;j:=0;fori:=2ton-1dobegins:=0;m:=n;while(m<>0)and(mmodi=0)dobeginm:=mdivi;（

）;end;if（）thenbeginj:=j+1;（）;a[j,2]:=（）;endend;

s:=s+1

s>0

a[j,1]:=is第五十八页，共一百一十三页，2022年，8月28日

fori:=0tojdob[i]:=0;whileb[0]=0dobegin

k:=j;while（）dok:=k-1;b[k]:=b[k]+1;forl:=（）dob[l]:=0;s:=1;fori:=1tojdoifb[i]<>0thenforl:=1tob[i]do（）;ifs=nthenbegin

endendend.

fori:=1tojdoc[i]:=b[i];write('(');m:=1;fori:=1tojdowhile(c[i]>0)and(m<>n)dobeginm:=m*a[i,1];ifm=nthenwrite(a[i,1])elsebeginwrite(a[i,1],'*‘）;c[i]:=c[i]-1;end;end; writeln(')');b[k]=a[k,2]k+1tojs:=s*a[i,1]输出表达式第五十九页，共一百一十三页，2022年，8月28日

有一个箱子容量为V（正整数，0≤V≤20000），同时有n个物品（0<n≤30），每个物品的体积值为正整数。要求从n个物品中，任取若干个装入箱内，使箱子的剩余空间最小。输入：一行整数，第一个数表示箱子的容量，第二个数表示有n个物品，后面n个数分别表示这n个物品各自的体积。输出：一个整数，表示箱子的剩余空间。

样例：输入：2468312797输出：0装箱问题（2001年普及组复赛第4题）第六十页，共一百一十三页，2022年，8月28日选数（2002年普及组复赛第2题）已知n（1<=n<=20）个整数x1,x2,…,xn（1<=xi<=5000000），以及一个整数k（k<n）。从n个整数中任选k个整数相加，可分别得到一系列的和。例如当n=4，k=3，4个整数分别为3，7，12，19时，可得到的全部组合及它们的和为3+7+12=22，3+7+19=29，7+12+19=38，3+12+19=34。现在，要求你计算出和为素数的组合共有多少种。如上例中，只有一种组合的和为素数：3+7+19=29。输入：n,kx1，x2，…，xn输出：一个整数(满足条件的组合个数)

样例

输入：43371219输出：1第六十一页，共一百一十三页，2022年，8月28日问题描述：辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？输入文件medic.in：第一行有两个整数T（1<=T<=1000）和M（1<=M<=100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。输出文件medic.out：包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。样例输入：7037110069112样例输出：3采药(2005年普及组第3题)第六十二页，共一百一十三页，2022年，8月28日

varw,v,a,s:array[0..100]oflongint;i,m,n,max:longint;proceduretry(k,use,now:longint);

{K为待选购物品的序号，use是已用去的钱，now是现有的价值和}

beginifk=m+1thenbeginifnow>maxthenmax:=now;

exit;end;ifuse+w[k]<=nthentry(k+1,use+w[k],now+a[k]);{钱还够，就买入此物品，待选下一物品}

try(k+1,use,now);{不买此物品,待选下一物品}

end;2、用回溯法解第六十三页，共一百一十三页，2022年，8月28日beginreadln(n,m);{总钱数和物品数}

fori:=1tomdobeginread(w[i],v[i]);a[i]:=w[i]*v[i];end;max:=0;try(1,0,0);writeln(max);

end.第六十四页，共一百一十三页，2022年，8月28日下面程序的功能是利用递归方法生成从1到n(n<10)的n个数的全部可能的排列（不一定按升序输出）。例如，输入3，则应该输出（每行输出5个排列）：123132213231321312

求全排列（2006年普及组初赛）第六十五页，共一百一十三页，2022年，8月28日vari,n,k:integer;a:array[1..10]ofinteger;count:longint;procedureperm(k:integer);varj,p,t:integer;beginif

thenbegin

;forp:=1tokdowrite(a[p]:1);write('');if

thenwriteln;exit;end;forj:=ktondobegint:=a[k];a[k]:=a[j];a[j]:=t;perm(k+1);t:=a[k];

;

endend;beginread(n);count:=0;fori:=1tondoa[i]:=i;

;end.k=ninc(count)countmod5=0a[k]:=a[j];a[j]:=tperm(1)第六十六页，共一百一十三页，2022年，8月28日设有一个n*m的棋盘（2≤n≤20，2≤m≤20），如下图，在棋盘上左下角有一个中国象棋马。（n,m）

(1,1)马走的规则为：①马走日字；②马只能向右走；即如下图如示：

问题：当n，m输入之后，找出一条从左下角到右上角的路径。若不存在路径，则输出’NO’。样例输入：44输出：（1，1）->(2,3)->(4,4)

马骑士游历问题(1997年高中组第三题)第六十七页，共一百一十三页，2022年，8月28日

问题描述:将整数n分成k份，且每份不能为空，任意两种分法不能相同(不考虑顺序)。例如：n=7，k=3，下面三种分法被认为是相同的：1，1，5;1，5，1;5，1，1;问有多少种不同的分法。输入：n，k(6<n<=200，2<=k<=6)输出：一个整数，即不同的分法。样例：输入：

73输出：

4{四种分法为：1，1，5;1，2，4;1，3，3;2，2，3;}数的划分（2001年提高组复赛第2题）第六十八页，共一百一十三页，2022年，8月28日【问题描述】棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。棋盘用坐标表示，A点(0,0)、B点(n,m)(n,m为不超过15的整数)，同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。【输入】一行四个数据，分别表示B点坐标和马的坐标。【输出】一个数据，表示所有的路径条数。【样例】输入:6633