# NOIP复赛必记常用算法

1 折半查找(二分法查找) function binsearch(k:keytype):integer; var low,hig,mid:integer; begin low:=1;hig:=n; mid:=(low+hig) div 2; while (a[mid].key<>k) and (low<=hig) do begin if a[mid].key>k then hig:=mid-1 else low:=mid+1; mid:=(low+hig) div 2; end; if low>hig then mid:=0; binsearch:=mid; end;

2.小范围内判断一个数是否为质 数： function prime (n: integer): boolean; var I: integer; begin for I:=2 to trunc(sqrt(n)) do if n mod I=0 then begin prime:=false; exit; end; prime:=true; end;

for n:=3 to 100 do begin f:=true; for i:=2 to n-1 do if n mod i=0 then f:=false; if f=true then write(n:5); end; 冒泡法排序 for i:=1 to n-1 do for j:=i+1 to n do if b[i]>b[j] then begin k:=b[i];b[i]:=b[j];b[j]:=k;end; 选择法排序 for i:=1 to n-1 do begin k:=i; for j:=i+1 to 10 do if b[j]<b[k] then k:=j; if k<>i then begin t:=b[k];b[k]:=b[i];b[i]:=t;end; write(b[i]:3); end; writeln(b[n]:3); . 冒泡排序另一种写法

for i:=1 to n-1 do for j:=n downto i+1 do if a[j]<a[j-1] then swap( a[j],a[j-1]); {每次比较相邻元素的关系}

procedure insertsort; 插入法排序 var i,j,k:integer; f:boolean; begin b[1]:=a[1]; for i:=2 to 10 do begin j:=1;f:=false; while (j<=i-1) and (not f) do if a[i]<b[j] then begin for k:=i downto j+1 do b[k]:=b[k-1]; b[j]:=a[i];f:=true; end else j:=j+1; if not f then b[i]:=a[i]; end; for i:=1 to 10 do write(b[i]:3); writeln; end; procedure qsort(l,r:integer); //快速排序 var i,j,mid:integer; begin i:=l;j:=r; mid:=a[(l+r) div 2]; {将当前序列在中间位置的数定义为中间数} repeat while a<mid do inc(i); {在左半部分寻找比中间数大的数} while a[j]>mid do dec(j);{在右半部分寻找比中间数小的数} if i<=j then begin {若找到一组与排序目标不一致的数对则交换它们} swap(a,a[j]); inc(i);dec(j); {继续找} end; until i>j; if l<j then qsort(l,j); {若未到两个数的边界，则递归搜索左右区间} if i<r then qsort(i,r); end;{sort} 高精度数的定义：type hp=array[1..maxlen] of integer; 1．高精度加法 procedure plus ( a,b:hp; var c:hp); var i,len:integer; begin fillchar(c,sizeof(c),0); if a[0]>b[0] then len:=a[0] else len:=b[0]; for i:=1 to len do begin inc(c,a+b); if c>10 then begin dec(c,10); inc(c[i+1]); end; {进位} if c[len+1]>0 then inc(len); c[0]:=len; end;{plus}

2．高精度减法 procedure substract(a,b:hp;var c:hp); var i,len:integer; begin fillchar(c,sizeof(c),0); if a[0]>b[0] then len:=a[0] else len:=b[0]; for i:=1 to len do begin inc(c,a-b); if c<0 then begin inc(c,10);dec(c[i+1]); end; while (len>1) and (c[len]=0) do dec(len); c[0]:=len; end; 3．高精度乘以低精度 procedure multiply(a:hp;b:longint;var c:hp); var i,len:integer; begin fillchar(c,sizeof(c),0); len:=a[0]; for i:=1 to len do begin inc(c,a*b); inc(c[i+1],(a*b) div 10); c:=c mod 10; end; inc(len); while (c[len]>=10) do begin {处理最高位的进位} c[len+1]:=c[len] div 10; c[len]:=c[len] mod 10; inc(len); end; while (len>1) and (c[len]=0) do dec(len); {若不需进位则调整 len} c[0]:=len; end;{multiply} 4．高精度乘以高精度 procedure high_multiply(a,b:hp; var c:hp} var i,j,len:integer; begin fillchar(c,sizeof(c),0); for i:=1 to a[0] do for j:=1 to b[0] do begin inc(c[i+j-1],a*b[j]); inc(c[i+j],c[i+j-1] div 10); c[i+j-1]:=c[i+j-1] mod 10; end; len:=a[0]+b[0]+1; while (len>1) and (c[len]=0) do dec(len); c[0]:=len; end; procedure devide(a:hp;b:longint; var c:hp; var d:longint); {c:=a div b; d:= a mod b} var i,len:integer; begin fillchar(c,sizeof(c),0);

5．高精度除以低精度 procedure devide(a:hp;b:longint; var c:hp; var d:longint); {c:=a div b; d:= a mod b} var i,len:integer; begin fillchar(c,sizeof(c),0); len:=a[0]; d:=0; for i:=len downto 1 do begin d:=d*10+a; c:=d div b; d:=d mod b; end; while (len>1) and (c[len]=0) then dec(len); c[0]:=len; end;

6．高精度除以高精度 procedure high_devide(a,b:hp; var c,d:hp); var i,len:integer; begin fillchar(c,sizeof(c),0); fillchar(d,sizeof(d),0); len:=a[0];d[0]:=1; for i:=len downto 1 do begin multiply(d,10,d); d[1]:=a; while(compare(d,b)>=0) do {即 d>=b} begin Subtract(d,b,d); inc(c); end; end; while(len>1)and(c.s[len]=0) do dec(len); c.len:=len; end;

program sdss_8hh(input,output); label ss ,hs; {说明两个标号} var h,g:array [1..8] of integer; {h 数组存每行皇后所在列数， g 数组存每 行皇后已试放过的列数} t,i,s:integer; begin for i:=1 to 8 do h[i]:=0; t:=1;s:=0; {开始搜索} repeat ss: g[t]:=g[t]+1; {方向数增 1} if g[t]>8 then goto hs; {若超过允许的 8 个方向则回嗍} for i:=1 to t-1 do {否则检验 1 行到 8 行的皇后是否与本行皇后处在同 一列或同一斜线上} if (h[i]=g[t]) or (abs(i-t)=abs(g[t]-h[i])) then goto ss; {若在同一列或同 一斜线上则重新换向搜索} h[t]:=g[t]; {否则保存该行皇后的列位置} t:=t+1; {前进一步} until t>8; {直到第 8 行} for i:=1 to 8 do write (h[i]:2); {打印本方案} s:=s+1; writeln('---',s); t:=8; {从第 8 行开始回嗍} hs: g[t]:=0; {t 步方向清零} t:=t-1; {回嗍一步} if t>0 then goto ss; {若未到起点 则继续转搜索} writeln('end'); end.

program tm(output); 跳马问题深 度搜 索 label ss,hs; type sz=array[0..4,0..8] of integer; var g:array[1..50] of integer; {大约在 50 步以内完成} a,b:array[1..4] of integer; {a,b 是 4 个方向上的坐标的行、列增量数组} m:array[1..50,1..2] of integer; {m 数组存路线上各点的坐标} p:sz; {p 数组记录棋盘上各点是第几步走到的} i,j,t,x,y,s,hn,ln:integer; procedure pr(h:sz;hn,ln:integer); {打印每一种方案中的 p 数组} var i,j:integer; begin for i:=0 to hn do begin for j:=0 to ln do if h[i,j]<>0 then write(h[i,j]:3) else write('-':3); writeln; end; writeln('---------------------------------------'); end; begin {main} { clrscr;} write('hn,ln='); readln(hn,ln); {设定棋盘的行、列数，此处一般输入 4，8} for i:=0 to hn do for j:=0 to ln do p[i,j]:=0; writeln('t=0'); pr(p,hn,ln); a[1]:=2;b[1]:=1; {b[]---lie zen liang a[]---hang zen liang} a[2]:=1;b[2]:=2; a[3]:=-1;b[3]:=2; a[4]:=-2;b[4]:=1; t:=1;s:=0;x:=0;y:=0;m[t,1]:=x;m[t,2]:=y;p[hn-x,y]:=t; {搜索初始化} writeln('t=',t);pr(p,hn,ln); ss: {开始搜索} repeat g[t]:=g[t]+1; {方向数增 1} if g[t]>4 then goto hs; {若方向超界，则换向搜索} i:=x+a[g[t]];j:=y+b[g[t]]; {若未超界，则按此步试探的方向生成下一步可 能的落脚点坐标} if (i<=hn) and (i>=0) and (j<=ln) and (j>=0) then {若该点在棋盘内，则前 进一步，保存该点坐标和步数} begin t:=t+1; m[t,1]:=i;m[t,2]:=j; x:=i;y:=j; p[hn-x,y]:=t; end; until (x=hn) and (y=ln); {直到到达右上角为止} {print} for i:=1 to t do write('(',m[i,1],',',m[i,2],')->'); {打印这条路径} s:=s+1; writeln(t,'====',s);

for i:=1 to t do write('(',m[i,1],',',m[i,2],')->'); {打印这条路径} s:=s+1; writeln(t,'====',s); pr(p,hn,ln); {调用过程打印该路径对应的棋盘路线图} readln; {本句目的使 运行结果由手工控制，按一次回车，出一个结果} hs: {开始回溯} p[hn-x,y]:=0; {最后一步的 p 数组元素置零} g[t]:=0; {最后一步方向清零} t:=t-1; {回溯一步} if t>0 then begin x:=m[t,1];y:=m[t,2];goto ss ;end {若未到起点，则调出第 t 步的坐标 x,y 然后转搜索} else {否则 可行方案寻找完毕} writeln('end') end. program qpl(input,output); 全排列问题的深 度搜 索 label ss ,hs; var a,fx,b:array [1..30] of integer; {a 数组存每一步搜索到的字母，fx 数据存 每一步试探过的方向数，b 数组作标志（该字母被用过否} t,j,k,total,n:integer; {t 搜索深度， n 排列字母的个数， total 总方案数} begin write('input n=');readln(n); t:=1;total:=0; {搜索的初始状态} {开始搜索} repeat ss: fx[t]:=fx[t]+1; {方向数增 1} if fx[t]>n then goto hs; {若方向数超界则 回溯} if b[fx[t]]=1 then goto ss; {未超界，但该字母被用过也要重新搜索} a[t]:=fx[t]; {该字母可用，保存到 a 数组中，该字母标志置 1，表 示已被用} b[fx[t]]:=1; t:=t+1; {前进一步，搜索下一位置的字母} until t>n; {直到 n 个字母都搜索出来} for k:=1 to n do write(chr(a[k]+64)); {打印这一种方案} total:=total+1; writeln('---',total); t:=n; b[a[t]]:=0; {将最后一步用过的字母标志清零（换其它字母看行 否），继续搜索} goto ss; hs: {开始回溯} fx[t]:=0; {t 步用过的方向数清零} t:=t-1; {回溯一步} if t>0 then begin b[a[t]]:=0; {如果未回到起点，就将该步原来用过的字母标志清零，然 后转搜索} goto ss; end; writeln('end'); {否则所有可行方案已搜索完毕，结束} end.

procedure mglj(var mg:mgsz;ruko,chko:kjl); 广度搜索迷宫的过程 var x,y,i,j,v:integer; begin sq[1].h:=ruko.h;sq[1].l:=ruko.l;sq[1].pre:=0; front:=1;rear:=1;mg[1,1]:=2; {front 指向父结点，rear 指向该父结点对 应的子结点} while front<=rear do {当 front 超过 rear 时，表示所有子结点都已发展 完，否则就继续向下发展} begin x:=sq[front].h; {x,y 表示当前结点位置} y:=sq[front].l; for v:=1 to 4 do begin i:=x+zl[v].h; {i,j 表示可能的子结点位置} j:=y+zl[v].l; if mg[i,j]=0 then {该点有通路，则将其发展为一个子结点} begin rear:=rear+1; {子结点指针增 1，并将该子结点的位置及对应 父结点的编号记录到队列中} sq[rear].h:=i; sq[rear].l:=j; sq[rear].pre:=front; mg[i,j]:=2; {迷宫走过之处置 2，作标志，防回头路} end; if (i=chko.h) and(j=chko.l) then {如果当前子结点已到出口，则找 到了一条通路，打印该路径} begin writeln('front=',front); printlj(sq,rear); {mg[chko.h,chko.l]:=0; rear:=rear-1; front:=sq[sq[front].pre].pre; restore(mg); exit; } end; end; front:=front+1; end; writeln('no way'); end;

program tm_gdss(input,output);

{广度搜索跳马路径}

type mgsz=array[0..20,0..20] of integer; {存棋盘中马跳的各点步数方阵} sqtype=array[1..400] of record {队列，存放跳马过程中按广度方式发展 的各结点坐标和前趋结点号} h,l:integer; pre:0..400; end; kjl=record h,l:integer; {入口及出口的行列坐标记录类型} end; var mg:mgsz; sq:sqtype; zl:array[1..4] of record {马可跳的四个方向行列坐标增量数组} h,l:-2..2; end; front,rear,i,j,m,n,num:integer; {front--队列头指针,rear---队列尾指针} ruko,chko:kjl; {入口和出口坐标} procedure printlj(sq:sqtype;rear:integer); {打印搜索出的一条马跳路径} var i,j,k:integer; begin for i:=0 to m do for j:= 0 to n do mg[i,j]:=0; {棋盘方阵清零} i:=rear; k:=0; repeat {这一段逆向打印出马跳路径，并统计出所用的步数，该步数 将反映出马所跳位置步数} write('(',sq[i].h,',',sq[i].l,')<--');k:=k+1; i:=sq[i].pre; {沿前趋指针取出前趋结点号} until i=0; num:=num+1; writeln('==',num); i:=rear; repeat mg[m-sq[i].h,sq[i].l]:=k; {重新用 K 值改换棋盘方阵} i:=sq[i].pre; k:=k-1; until i=0; writeln('------------------------------------'); {打印出这种跳法的棋盘方阵} for i:=0 to m do begin for j:=0 to n do write(mg[i,j]:2); writeln; end; end; procedure tmlj(ruko,chko:kjl); {广度搜索所有跳马路径} var x,y,i,j,v:integer; {x,y---当前结点坐标， i,j---欲发展的子结点坐标， V---每点 4 个方向的循环变量} begin sq[1].h:=ruko.h;sq[1].l:=ruko.l;sq[1].pre:=0; {入口坐标进入队列}

procedure tmlj(ruko,chko:kjl); {广度搜索所有跳马路径} var x,y,i,j,v:integer; {x,y---当前结点坐标， i,j---欲发展的子结点坐标， V---每点 4 个方向的循环变量} begin sq[1].h:=ruko.h;sq[1].l:=ruko.l;sq[1].pre:=0; {入口坐标进入队列} front:=1;rear:=1; {队头、队尾指针初始化} while front<=rear do {队头指针未超过队尾指针，则队列还有可发展的 结点，继续} begin x:=sq[front].h; {取出队头指针所指结点的行列坐标，作为当前父结 点的行列坐标} y:=sq[front].l; for v:=1 to 4 do {沿 4 个方向分别检测是否存在可发展的子结点} begin i:=x+zl[v].h; {形成第 V 个方向上子结点的坐标} j:=y+zl[v].l; if ((i>=0) and (i<=m) and (j>=0) and (j<=n)) then {如果该子结点未超出 棋盘，则该子结点入队} begin rear:=rear+1; {队尾指针增 1} sq[rear].h:=i; {子结点行列坐标入队} sq[rear].l:=j; sq[rear].pre:=front; {子结点的父结点号入队} if (i=chko.h) and (j=chko.l) then {如果已到出口，则打印本条路径} begin writeln('front=',front,' rear=',rear); printlj(sq,rear);readln; {调用子过程，打印路径} end; end; end; front:=front+1; {当一个父结点的 4 个方向都发展完了时，队头指针增 1，指向下一个父结点} end; {while front<=rear} writeln('no way'); end; begin {main} m:=4;n:=8; {棋盘由 m 行，n 列构成} write('Input mg m,n=');{readln(m,n);} ruko.h:=0;ruko.l:=0; {设棋盘上马的起点和终点坐标} chko.h:=4;chko.l:=8; zl[1].h:=2;zl[1].l:=1; {马可跳的 4 个方向的增量} zl[2].h:=1;zl[2].l:=2; zl[3].h:=-1;zl[3].l:=2; zl[4].h:=-2;zl[4].l:=1; num:=0; {num 用于累计马可行的路线条数} tmlj(ruko,chko); {调用过程广度搜索所有可行路线} end.

{问题：有一个随机的三角形数字塔，顶点为根结点，每个结点有一个整数值。从 顶点出发，可以向左走，也可以向右走 编程找出一条从顶点到达最低层的通路，使经过的结点值之和达到最大} { 4 74 399 8455 59839 274357 6223134 27778931 448256156 } program dtgh_st(input,output); {动态规划算法 解决数字塔问题} const n=20; var i,j:integer; g:array[1..n,1..n,1..3] of integer; begin randomize; for i:=1 to n do begin for j:=1 to i do begin g[i,j,1]:=1+random(9); {生成随机的数字塔各结点值} {read(g[i,j,1]);} g[i,j,2]:=g[i,j,1]; {记录每个结点可提供的最大贡献值，初始时，假定 最大值就是结点本身} g[i,j,3]:=0; {记录最大和路径上各父结点的子女结点偏移量} write(g[i,j,1]:2); {0 表示左偏，1 表示右偏，j+g[i,j,3]就是下一层子女 结点所在列} end; writeln; end; for i:=n-1 downto 1 do {从倒数第二层开始，向上逐层计算各结点的最大贡献 值} for j:=1 to i do if g[i+1,j,2]>g[i+1,j+1,2] then g[i,j,2]:=g[i,j,2]+g[i+1,j,2] {若左子女>右子女} else {则取左子女的最大值+该父结点的值作为该父结点 的最大贡献值} begin g[i,j,2]:=g[i,j,2]+g[i+1,j+1,2]; {否则取右子女的最大值+该父结点的值作为 该父结点的最大贡献值} g[i,j,3]:=1; {记录前进方向，即向右下偏} end; writeln('-----------------------------'); write ('i:':3);for i:=1 to n do write(i:3); writeln; {显示 G[]数组内容} write ('j:':3);j:=1;write(j:3); for i:=1 to n-1 do begin j:=j+g[i,j,3]; {显示第 i 行取的元素所在列数} write(j:3); end;

write ('j:':3);j:=1;write(j:3); for i:=1 to n-1 do begin j:=j+g[i,j,3]; {显示第 i 行取的元素所在列数} write(j:3); end; writeln; write ('FX:':3);j:=1; for i:=1 to n-1 do begin write(g[i,j,3]:3); j:=j+g[i,j,3]; end; writeln; writeln('------------------------------------'); writeln('max=',g[1,1,2]); {输出最大和及经过的路径} write('(1,1)',g[1,1,1]); j:=1; for i:=1 to n-1 do begin j:=j+g[i,j,3]; write('---','(',i+1,',',j,')',g[i+1,j,1]); end; writeln; end. {13 7 9 16 38 24 37 18 44 19 21 22 63 15 求出的最长不下降序列的个数是 8 ,序列 为:7 9 16 18 19 21 22 63} program dtgh_bigup(input,output); {求最长的不下降序列} const n=14; {N 表示原始序列的长度} var i,j,k,len,l:integer; {B[i,1]---表示 I 号数据本身的值} b:array[1..n,1..3] of integer; {B[i,2]---表示 I 号数据后面存在的不下降序列 的最大长度} begin {B[i,3]---链接字，表示 I 号数据后面的链接者序号,即 后继最大长度节点的序号} writeln('=============================================='); randomize; writeln('Input 14 nuber...'); for i:=1 to n do begin { b[i,1]:=random(100);} read(b[i,1]); {输入 N 个数据的序列} b[i,2]:=1; {初始时，以每个结点开始的最长不下降序列长度均 设为 1} b[i,3]:=0; {初始时，每个结点的后继链接序号均设为 0，表示 无链接} end; for i:=1 to n do write(b[i,1]:3); writeln; for i:=1 to n do write(b[i,2]:3); writeln; for i:=1 to n do write(b[i,3]:3); writeln('-------------------------------------------');

for i:=n-1 downto 1 do {动态规划核心程序：从倒数第 2 项开始 计算各结点的最大长度和链接字} begin k:=0;len:=0; for j:=i+1 to n do if (b[j,1]>b[i,1]) and (b[j,2]>len) then {找出 I 号后面比 I 号结点数大，且 长度最大的结点号 K} begin k:=j; len:=b[j,2]; end; if len>0 then begin b[i,2]:=len+1; {如果长度>0 则长度增 1 作为该 I 号结点的 最大长度} b[i,3]:=k; {K 作为该 I 号结点的链接字} end; end; l:=1; for j:=2 to n do if b[j,2]>b[l,2] then l:=j; writeln('max=',b[l,2]); while l<>0 do begin write(b[l,1]:4); l:=b[l,3]; end; writeln; end.

{找出 B[I,2]中最大者作为最大长度}

{沿链接字输出最长不下降序列}

{地雷坑号:1 2 3 4 5 6 7 8 9 10} {地雷数量:8 14 2 17 33 26 15 17 19 6 } {如何挖,才能挖到最多的雷，可从任一坑开始挖，假设连线不分方向，只要 两坑 I J 之间有连线，就认为可以在挖完 I 号坑后继续去挖 J 号坑} prgoram wdl(input,output); const n=10; var i,j,k,l:integer; g:array[1..n,1..3] of integer; r:array[1..n,1..n] of 0..1; begin for i:=1 to n do for j:=1 to n do r[i,j]:=0; for i:=1 to n do begin readln(g[i,1]); g[i,2]:=g[i,1]; g[i,3]:=0; end; for i:=1 to n do begin for j:=1 to n do read(r[i,j]); readln; end; begin l:=0;k:=0; for j:=i+1 to n do {找出第 i 号坑之后，可以挖到最多雷数的坑} if (r[i,j]=1) and (g[j,2]>1) then begin l:=g[j,2];k:=j;

for i:=n-1 downto 1 do begin l:=0;k:=0; for j:=i+1 to n do {找出第 i 号坑之后，可以挖到最多雷数的坑} if (r[i,j]=1) and (g[j,2]>1) then begin l:=g[j,2];k:=j; end; if l>0 then begin g[i,2]:=g[i,2]+l; g[i,3]:=k; end; end; l:=1; for j:=2 to n do if g[j,2]>g[l,2] then l:=j; writeln('max=',g[l,2]); while l<>0 do begin write(g[l,1]:4); l:=g[l,3]; end; writeln; end. program tf2_2005(input,output); const max=100; {设定最多 100 个石头} skip=90; {设定桥长空档可压缩的最小长度} var stone:array[0..max] of longint; {石头位置原始数组} b,c,f:array[-10..max*skip] of longint; {b 标志压缩桥长后该位置有无石头， c 压缩数组，f(i)动规数组，存 i 位置前 s 至 t 点跳到 i 位置采到的最小石头 数} l,s,t,m:longint; {l 桥长，s、t 跬跳的最小和最大距离，m 石头总数} procedure init; {读入已知的数据} var i,j,temp:longint; begin fillchar(f,sizeof(f),0); {各数组清 0} fillchar(c,sizeof(c),0); fillchar(stone,sizeof(stone),0); fillchar(b,sizeof(b),0); assign(input,'river.in'); reset(input); assign(output,'river.out'); rewrite(output); readln(l); {读入桥长} readln(s,t,m); {读入跳跃的最小和最大距离以及石头的总数} for i:=1 to m do read(stone[i]); {读入各石头的原始位置} for i:=1 to m-1 do {对读入的石头位置按从小到大排序} for j:=i+1 to m do

readln(l); {读入桥长} readln(s,t,m); {读入跳跃的最小和最大距离以及石头的总数} for i:=1 to m do read(stone[i]); {读入各石头的原始位置} for i:=1 to m-1 do {对读入的石头位置按从小到大排序} for j:=i+1 to m do if stone[i]>stone[j] then begin temp:=stone[j];stone[j]:=stone[i];stone[i]:=temp;end; for i:=1 to m do {按照设定的 skip 压缩桥上的大空档，替换每一个石头 的位置，形成 C 数组和 b 数组} begin if stone[i]-stone[i-1]>=skip {如果后一石与前一石头间距超过 skip,则后一 石头新位置改成前一石位置+skip} then c[i]:=c[i-1]+skip else c[i]:=c[i-1]+stone[i]-stone[i-1]; {否则 后一石的新位置就是前一石位 置+两石原间距} b[c[i]]:=1; {在这个新位置标志有石头} end; {压缩完毕} end; procedure work; {动态规划} var i,j,min:longint; begin for i:=1 to s-1 do f[i]:=maxint; {S 前每个位置是不可达的，初始化为最大} for i:=s to c[m]+t do //从 S 位置至最后一个石子+t 位置的这一段，计算到 达每个 i 位置采到的最少石头数 f(i)=min{f(i-j)}+b[i] } begin min:=maxint; for j:=s to t do if f[i-j]<min then min:=f[i-j]; f[i]:=min+b[i]; end; min:=f[c[m]]; {先将最后一个石头处的 f()作为最少的石头数} for i:=c[m] to c[m]+t do {检查是否还存在越过最后一个石头后更小的 f(), 若存在则替换} if f[i]<min then min:=f[i]; writeln(min); {输出踩到最少的石头数} end; procedure work2; {处理 S=t 的情况} var i,sum:longint; begin if s<>t then work else begin sum:=0; for i:=1 to m do {将石头位置是 S 整倍数的那些石头数求和} if stone[i] mod s=0 then inc(sum); writeln(sum); {这就是 s=t 时踩到的最少石头数} end; end; begin init; work2; close(input); close(output);

begin init; work2; close(input); close(output); end. program equal1; 2005 年复赛第 4 题 等价表达式 const max=maxlongint; //用于超范围时求余，保证计算不会出现超界情况 com:array [1..7,1..7] of { //运算符级别的二维常量矩阵，用于比较运算的优先 级，有利于提高运算速度 } char=(('>','>','<','<','<','>','>'), ('>','>','<','<','<','>','>'), ('>','>','>','<','<','>','>'), ('>','>','>','>','<','>','>'), ('<','<','<','<','<','=','n'), ('>','>','>','>','n','>','>'), ('<','<','<','<','<','n','n')); fileIp1='equal8.in'; fileop1='equal.out'; var Ip1:array [0..26] of string; //存各表达式 value1:array[0..26,-7..7] of int64; //存各表达式的 a 代-7..7 计算后的值 IsSame1:array[0..26] of boolean; //标志是否与题干表达式等价 a,b:int64; //两个待运算的数值 flag:boolean; //标志，用于将表达式中的整数如 231，整体分离出来存入栈 的某一位置 num1:int64; // p,q:int64; //-----------------------------------procedure Input1; {输入表达式} var f1:text; s1:integer; begin assign(f1,fileip1); reset(f1); readln(f1,ip1[0]); //读入题干表达式 readln(f1,num1); //读入待判断的表达式个数 for s1:=1 to num1 do readln(f1,ip1[s1]); //读入每个表达式 close(f1); end; //--------------------------------------procedure Init1; {初始化值} var s1:integer; begin for s1:=0 to 26 do issame1[s1]:=true; //所有表达式均初始化为真 end; //--------------------------------------function GetIndex1(C1:char):integer;{定义运算符的序号} begin case c1 of '+':getindex1:=1;

function GetIndex1(C1:char):integer;{定义运算符的序号} begin case c1 of '+':getindex1:=1; '-':getindex1:=2; '*':getindex1:=3; '^':getindex1:=4; '(':getindex1:=5; ')':getindex1:=6; '#':getindex1:=7; end; end; //---------------------------------function compare(c1,c2:char):char; {比较运算符的优先级} var s1,s2:integer; begin s1:=getindex1(c1); //符号栈顶指针指向的运算符 s2:=getindex1(c2); //当前读到的运算符 compare:=com[s1,s2]; //算出两者的优先级（得到的结果是“<”或“>” “=”“n”） end; //-------------------------------------function process1(a:int64;c1:char;b:int64):int64;{根据运算符计算表达式的值} var s1:longint;tmp1:int64; begin case c1 of '+':tmp1:=(a+b) mod max; //求余的目的是保证不出现超界的情况，而且计 算速度加快 '-':tmp1:=(a-b) mod max; '*':tmp1:=(a*b) mod max; '^':begin tmp1:=1; for s1:=1 to b do tmp1:=tmp1*a mod max; end; end; process1:=tmp1; end; function exp(Str1:string;aa:longint):int64; {计算表达式的值} var s1:integer; ps1:char; stknum1:array [1..1000] of longint; {操作数栈} stkps1:array[1..1000] of char; {运算符栈} nownum1,nowps1:integer; {定义两个栈的栈顶指针} begin str1:=str1+'#'; //“#”作为一个表达式的结束标志, s1:=1; //读表达式中字符的指针 nownum1:=0;nowps1:=1; //数栈指针置 0（空），符栈指针置 1 fillchar(stknum1,sizeof(stknum1),0); stkps1[1]:='#';flag:=false; //#首先入符号栈,flag 用于标志多位的整数 while not ((str1[s1]='#')and (stkps1[nowps1]='#')) do //当符栈未空并且读表达 式未见到“#” begin if str1[s1] in ['0'..'9'] then {如果为数字字符，则转化为数字}

stkps1[1]:='#';flag:=false; //#首先入符号栈,flag 用于标志多位的整数 while not ((str1[s1]='#')and (stkps1[nowps1]='#')) do //当符栈未空并且读表达 式未见到“#” begin if str1[s1] in ['0'..'9'] then {如果为数字字符，则转化为数字} begin if not flag then //如果是数字的首字符，就直接入数栈 begin nownum1:=nownum1+1; //栈顶指针增 1 stknum1[nownum1]:=ord(str1[s1])-ord('0'); //数值的首字符入栈 flag:=true; //改标志，为拼接该整数的下一位做准备 s1:=s1+1; //读取表达式中一个字符后，表达式字符指针增 1 end else //否则是该整数的后续位字符，继续拼入 begin stknum1[nownum1]:=stknum1[nownum1]*10+ord(str1[s1])-ord('0'); s1:=s1+1; end; end else {if str1} if str1[s1]='a' then {如果为字母'a'则带入值} begin nownum1:=nownum1+1; stknum1[nownum1]:=aa; s1:=s1+1; end else if str1[s1]=' ' then {如果为空格，则指针后移} s1:=s1+1 else //否则该字符就是运算符号 begin flag:=false; case compare(stkps1[nowps1],str1[s1]) of //比较相邻两次迂到的运算符 '<':begin {当前读到的运算符级别高于符栈顶的运算符，将读到的 算符入栈，待下次再读到更低级运算符时，再弹出该符进行运算} nowps1:=nowps1+1; stkps1[nowps1]:=str1[s1]; //入栈 s1:=s1+1; end; '>':begin ps1:=stkps1[nowps1]; {当前读到的运算符低于符栈顶的运算 符，所以符栈顶的运算符出栈进行运算} nowps1:=nowps1-1; b:=stknum1[nownum1]; {操作数出栈} nownum1:=nownum1-1; a:=stknum1[nownum1]; {操作数出栈} stknum1[nownum1]:=process1(a,ps1,b); //按运算符计算这两个 数，结果继续入数栈 end; '=':begin nowps1:=nowps1-1;s1:=s1+1;end;{运算符出栈} 'n':begin s1:=s1+1 end; end; {End Select} end; end; exp:=stknum1[1]; //表达式最终算出的一个值

'=':begin nowps1:=nowps1-1;s1:=s1+1;end;{运算符出栈} 'n':begin s1:=s1+1 end; end; {End Select} end; end; exp:=stknum1[1]; //表达式最终算出的一个值 end; //--------------------------------------------procedure OutPut1; {输出结果} var f1:text;s1:integer; begin assign(f1,fileop1);rewrite(f1); for s1:=1 to num1 do begin if issame1[s1] then write(f1,chr(ord('A')+s1-1)) //输出等价表达式对应的标 号字母 end; writeln(f1); close(f1); end; //---------------------------------------------procedure Work1; {主过程} var s1,s2:integer; begin for s1:=0 to num1 do //循环检查每个表达式 if issame1[s1] then for s2:=-7 to 7 do begin value1[s1,s2]:=exp(ip1[s1],s2); if value1[s1,s2]<>value1[0,s2] then begin issame1[s1]:=false;break;end; //一旦发现不等价，立即跳出内循环， 不再代值计算，转去判断下一个表达式 end;{Next}{End If} end; //----------------------------------------------BEGIN {主程序} input1; //读入表达式数据 init1; //初始化 work1; //循环检查每一个表达式，并做标记 output1; //输出标记为真的表达式 end.

program jiangxuejing2005tf1(input,output); 2005 年复赛第 1 题奖学金计算 var n,i,sum,max,cj,py,lw:integer; xm,max_xm:string; gb,xb,ch:char; total:longint; begin assign(input,'scholar.in'); reset(input); assign(output,'scholar.out'); rewrite(output); total:=0;max:=0; readln(n); for i:=1 to n do begin sum:=0; xm:=''; repeat read(ch); xm:=xm+ch; until (ch=' '); read(cj);read(py);read(ch);read(gb);read(ch);read(xb);read(lw); readln; if (cj>80) and (lw>=1) then sum:=sum+8000; if (cj>85) and (py>80) then sum:=sum+4000; if (cj>90) then sum:=sum+2000; if (cj>85) and (xb='Y') then sum:=sum+1000; if (py>80) and (gb='Y') then sum:=sum+850; if sum>max then begin max:=sum;max_xm:=xm;end; total:=total+sum; end; writeln(max_xm); writeln(max); writeln(total); close(input); close(output); end.
program p1096; 2004 年复赛第 1 题津津储蓄计划 var i,j,k,m,n,b,c:longint; a:array[1..12] of integer; begin for i:=1 to 12 do read(a[i]); j:=0; c:=0; repeat inc(k); b:=b+300; b:=b-a[k]; if b<0 then begin j:=k;break;end; n:=b div 100; if n>0 then begin m:=m+n*100;b:=b-n*100;end; until k=12; if j=0 then begin writeln(m*1.2+b:0:0);end else writeln(0-j); end.

procedure mglj(mg:mgsz;ruko,chko:kjl); 走迷宫广度搜索的核心过程 var x,y,i,j,v:integer; begin sq[1].h:=ruko.h;sq[1].l:=ruko.l;sq[1].pre:=0; front:=1;rear:=1;mg[1,1]:=2; while front<=rear do {广度搜索的核心算法部分---按父结点指针（队 头指针）发展子结点，每发展一个结点就进入队列，} begin {直到头指针超过尾指针时，全部子结点都发展完毕，搜索结束} x:=sq[front].h; y:=sq[front].l; for v:=1 to 4 do begin i:=x+zl[v].h; j:=y+zl[v].l; if mg[i,j]=0 then begin rear:=rear+1; sq[rear].h:=i; sq[rear].l:=j; sq[rear].pre:=front; mg[i,j]:=2; end; if (i=chko.h) and(j=chko.l) then begin writeln('front=',front); printlj(sq,rear); end; end; front:=front+1; end; writeln('no way'); end; {问题：有一个容量为 M 的背包，有 N 种商品，已知每种商品的编号、占背 包容量和采购后可获得的利润，如何采购，能获利最大} program bbwt(input,output); {贪心法 求解背包问题} const n=3; type hwtype=array[1..100] of record bh:integer; dl,zy,cg:real; end; var hw:hwtype; i,j,k:integer; m:real; procedure sort(var hw:hwtype;n:integer); {性价比排序} var i,j:integer; t:hwtype; begin for i:=1 to n-1 do for j:=i+1 to n do if (hw[i].dl/hw[i].zy<hw[j].dl/hw[j].zy) then begin t[i]:=hw[i];hw[i]:=hw[j];hw[j]:=t[i]; end; for i:=1 to n do writeln('I=',hw[i].bh,' ','XJB=',hw[i].dl/hw[i].zy:6:2); end; procedure cgsf(var hw:hwtype;n:integer;m:real); var i:integer; s,mcu:real; begin mcu:=m; {采购算法}

procedure cgsf(var hw:hwtype;n:integer;m:real); var i:integer; s,mcu:real; begin mcu:=m; i:=1; while (hw[i].zy<mcu) and (i<=n) do begin hw[i].cg:=hw[i].zy; mcu:=mcu-hw[i].zy; i:=i+1; end; if i<=n then hw[i].cg:=mcu else writeln; s:=0; for i:=1 to n do begin writeln(hw[i].bh,' cg=',hw[i].cg:6:2); s:=s+(hw[i].dl/hw[i].zy)*hw[i].cg; end; writeln('total_dl=',s:6:2); end; begin {main} write('m=');readln(m); writeln('Input hw[].bh(dl,zy,cg)='); for i:=1 to n do readln(hw[i].bh,hw[i].dl,hw[i].zy); sort(hw,n); cgsf(hw,n,m); end.

{采购算法}

program fill2(input,output); 2004 年复赛第 2 题合并果子 var s1,s2:array[0..15000] of longint; //存放原各堆果子数和每次合并后的新堆果子数 s1low,s1hi,s2low,s2hi:integer; //存两个队列的左右指针，用于快速取两个最小 堆合并 r,l,s,x,i,min1,min2:longint; function peeksmall:longint; //从两个队列中取一个最小的 begin min1:=1000000000;min2:=1000000000; if s1low<>s1hi then min1:=s1[s1low]; //如果 S1 中还有最小，则取 S1 中最小的 if s2low<>s2hi then min2:=s2[s2low]; //如果 S2 中还有最小，则取 S2 中最小的 if min1<min2 then begin peeksmall:=s1[s1low];inc(s1low); end //再比较看哪个最 小取哪个 else begin peeksmall:=s2[s2low];inc(s2low); end; end; procedure swap(l:integer;r:integer); //交换两数位置（排序使用） var tmp:longint; begin tmp:=s1[r]; s1[r]:=s1[l];

procedure swap(l:integer;r:integer); //交换两数位置（排序使用） var tmp:longint; begin tmp:=s1[r]; s1[r]:=s1[l]; s1[l]:=tmp; end; procedure sort(low:integer; hi:integer); //快速排序子程序（升序） var l:longint; begin if low>=hi then exit else x:=s1[(low+hi)div 2]; swap(low,(low+hi)div 2); l:=low; r:=hi; while l<r do begin while ((l<r)and(s1[r]>=x)) do dec(r); s1[l]:=s1[r]; while ((l<r)and(s1[l]<=x)) do inc(l); s1[r]:=s1[l]; end; s1[l]:=x; sort(low,l-1); sort(r+1,hi); end; begin assign(input,'fruit9.in'); reset(input); read(s1hi); // 读入果子总堆数 for i:=0 to s1hi-1 do read(s1[i]); // 读入各堆果子数存入 S1[] close(input); sort(0,s1hi-1); //原始各堆快速排升序 s:=0; s2hi:=0; for i:=1 to s1hi-1 do //N 堆 果子要合并 N-1 次 begin s2[s2hi]:=peeksmall+peeksmall; //取当前两堆最小的合并，生成新堆，加入 到 S2 队列(注意：S2 队列一定是严格递增的，这也是为什么 S1 队列要按升 序排的原故) s:=s+s2[s2hi]; //累加新堆的总和（计算局部最小代价） inc(s2hi); //新堆总数增 1 end; write(s); //输出合并的最小代价 end.

noip复赛总结归纳(c++)

NOIP复赛谈
NOIP 复赛谈 ? 复赛的命题 1. 准循大纲:考察常用的数据结构和基本算法; 2....面值为 1 的邮票是必须的;此后每加进一种面值都要把当前所能 取得的金额记...
noip信息竞赛100个基本算法
noip信息竞赛100个基本算法_理学_高等教育_教育专区。算法noip 信息竞赛 100 个基本算法基本算法 1.数论算法 求两数的最大公约数 function gcd(a,b:integer):int...
2017-2018NOIP-实用算法(中国计算机学会编)
2017-2018NOIP-实用算法(中国计算机学会编)_学科竞赛...(以从小到大排序为例)取一个数作为标 记元素,将...动态规划越来越被NOIP 提高组命题者青睐,成为每年必...

NOIP复赛复习资料汇总
NOIP复赛复习资料汇总_IT认证_资格考试/认证_教育...(五) 常用算法 (1)字符串匹配的 KMP 算法 [源...{记下已访问标记} {进队列} 18 while not empty...
NOIP初赛复习——算法1
NOIP初赛复习——算法1_理学_高等教育_教育专区。OK...则记下} then begin k←j; if M[j]=f[i] ...但是,在规模减半过程 中,势必增加某些辅助工作,在...
2014 NOIP 实用算法(中国计算机学会编)
2014 NOIP 实用算法(中国计算机学会编)_学科竞赛_...(以从小到大排序为例)取一个数作为标 记元素,将...动态规划越来越被NOIP 提高组命题者青睐,成为每年必...
2014年noip的基本算法复习.doc
2014年noip基本算法复习.doc_工学_高等教育_教育专区。2014 年 noip 的基本...二、求最小生成树 A.Prim 算法: procedure prim(v0:integer); var lowcost...

noip基本算法必背 9页 5财富值 NOIP初赛复习——一些基本... 23页 免费 NOIP初赛复习——一些基本... 23页 免费喜欢此文档的还喜欢 NOIP2010提高组复赛复习资...