tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

冲刺NOIP必掌握


冲刺 NOIP2014 必掌握资料
NOIP 2014,我一定能成功! 注: ‘*’表示重要程度。

一、基本函数
⑴ ⑵ ⑶ ⑷ ⑸ ⑹ 绝对值函数 abs(x) abs(-2.3); { 2.3 } 取整函数 int(x) int(123.567); { 123.0 } 截尾函数 trunc(x) trunc(1.4) {1} 四舍五入

函数 round(x) round(9.456) { 9 } 取小数函数 frac(x) frac(-123.456) { -0.456 } 求平方根函数 sqrt(x)和平方函数 sqr(x) sqrt(64) {8} sqr(8) {64} ⑺ 随机函数 random:随机产生一个 0~1(不含 1)之间的小数。 ⑻ 求字符串长度函数 length length(‘asdf’) { 4 } ⑼ 复制子串或求子串的函数 copy copy(‘window’,4,3) { dow } ⑽ 插入子串或插入字符串 insert 例如:若 st2:=‘wins’;执行 insert(‘dow’,st2,4)后 st2 的值是‘windows’ ⑾ 删除子串 delete 例如:若 st=‘excel’;执行 delete(st,4,2)后 st 的值是‘exc’ ⑿ 字符串转为数值 val val(‘359’,a,c1)执行后将使变量 a 得到数值 359(可参加四则运算) val(‘124.32’,b,c2)执行后将使变量 b 得到数值 124.32(可参加四则运算) val(‘adb’,c,c3)执行后,c3 将会出现错误值。 ⒀ 数值转为字符串 str str(128,s1)执行后字符串变量 s1 得到‘128’ ⒁ 查找子串起始位置 pos pos(‘in’,‘windows’)的值是 2,pos(‘+’,‘13+418=’) 的值是 3 ⒂ 字符完全串连+ ‘Bei’+‘jing’+‘2008’的值是 Beijing2008 ⒃ 求字符的 ASCII 码的函数。也称序数函数。 ord(‘A’)的值是 65 ord(‘Z’)的值是 90 ⒄ 求 ASCII 码对应的字符的函数。也称字符函数 chr(78)的值是 N, chr(57)的值是 9 ⒅ 求前趋 pred 的函数 pred(‘D’)的值是 C pred(‘65’)的值是 64 ⒆ 后继 succ 的函数 succ(‘D’)的值是 E ,succ(‘65’)的值是 66

二、数学算法
1.欧几里得(最大公约数)

**

function gcd(a,b:longint):longint; begin if b=0 then exit(a) else gcd:=gcd(b,a mod b);

充满无不能的精神

坚定必成功的信念!

1

end; 2.最小公倍数

**

function lcm(a,b:longint):longint; begin lcm:=a*b div gcd(a,b); end; 3.同余方程 //同余 即: a mod b=n mod b,也可表达为 a≡n(mod b); var a,b,n,i,j,k,d,e:longint; x,y:longint; function gcd(a,b:longint; var x,y:longint):longint; var t:longint; begin if b=0 then begin x:=1;y:=0; exit(a); end; gcd:=gcd(b, a mod b,x,y); t:=x; x:=y; y:=t-(a div b)*x; end; procedure noans; begin writeln('按题目要求'); end; begin readln(a,b,n); d:=gcd(a,n,x,y); if n mod d<>0 then noans; e:=x*(b div d) mod n; while e<0 do begin e:=(e+(n div d)) mod n; end; writeln(e); end. //解同余方程组 var a,b,x,y,k,n,m2,m1,a2,a1,g,t,c:longint; flag:boolean; function extended_gcd(a,b:longint;var x,y:longint):longint; var

充满无不能的精神

坚定必成功的信念!

2

t:longint; begin if b=0 then begin x:=1; y:=0; exit(a); end; extended_gcd:=extended_gcd(b,a mod b,x,y); t:=x; x:=y; y:=t - (a div b)*y; end; begin read(n); read(m1,a1); while n>1 do begin dec(n); read(m2,a2); g:=extended_gcd(m1,m2,x,y); c:=a2-a1; if c mod g<>0 then begin flag:=true;break;end; k:=m2 div g; t:=(c div g *x mod k+k) mod k; a1:=a1+t*m1; m1:=m1 div g *m2; end; if flag=false then write(a1) else write(-1); close(input);close(output); end. 4.快速幂//求解 ans=a^b mod c;

**

function soso(a,b:longint):longint; var total:longint; begin total:=1; while b>0 do begin if odd(b) then total:=(total*a) mod c; b:=b shr 1; a:=(a*a) mod c; end; exit(total); end; 5.筛选法求素数

**
充满无不能的精神 坚定必成功的信念!
3

Procedure get_prime(n:longint); var

i,j:longint; begin for i:=2 to n do if not f[i] then begin inc(top); list[top]:=i; J:=i+i; while j<=n do begin f[j]:=true; inc(j,i); end; end; end; 6.分解质因数//x=(p1^i1)*(p2^i2)*(pl^i3)....

**

var x,p,i,t:longint; begin readln(x); p:=2;t:=trunc(sqrt(x)); while (x<>1)and(p<=t)do begin if x mod p=0 then begin i:=0; while x mod p=0 do begin x:=x div p;inc(i); end; writeln(p,' ',i); end; inc(p); end; if x<>1 then writeln(x,' ',1); end. 7.中国剩余定理 {中国剩余余定理: 应用条件: 被除数互素 余数已知 如: 孙子算经中的一个问题 今有物不知几何,三三数至于二;五五数之余三;七七数之余二。问物几何? 答曰:二十三。 标准程序如下:} var n,m,i,j,k,l,x,z,y:longint; a,b,c:array[1..10]of longint; function gcd(x,y:longint):longint;

充满无不能的精神

坚定必成功的信念!

4

begin if y=0 then exit(x) else gcd:=gcd(y,x mod y); end; procedure init; begin assign(input,'number.in');reset(input); assign(output,'number.out');rewrite(output); end; procedure guan; begin close(input); close(output); end; begin //init; readln(n); fillchar(c,sizeof(c),0); for i:=1 to n do readln(a[i],b[i]); if n=1 then begin writeln(a[1]+b[1]);halt;end; x:=a[1]; for i:=2 to n do begin z:=gcd(x,a[i]); x:=x*a[i] div z; end; for i:=1 to n do begin c[i]:=1; for j:=1 to n do begin if j=i then continue; if j<>i then begin z:=gcd(c[i],a[j]); c[i]:=c[i]*a[j] div z; end; end; for z:= 1 to 100 do if ((z*c[i]) mod a[i]=1) then begin c[i]:=z*c[i]; break; end; end; for i :=1 to n do begin

充满无不能的精神

坚定必成功的信念!

5

writeln('c[',i,']',':=',c[i]); y:=c[i]*b[i]+y; end; writeln(x); y:=y mod x; writeln(y); end. 8.高斯消元

*

procedure gao si xiao yuan; const zero=0.0000001; var i,j,n:longint; x:array[0..maxn]of double; a:array[0..maxn,0..maxn+1]of double; procedure xiao; var i,j,k,l:longint; t:double; begin l:=1; for i:=1 to n do begin k:=l; for j:=l+1 to n do if abs(a[j,i])-abs(a[k,i])>zero then k:=j; if abs(a[k,i])<=zero then continue; if k<>l then for j:=i to n+1 do swap(a[l,j],a[k,j]); for j:=l+1 to n do begin t:=-a[j,i]/a[l,i]; for k:=i to n+1 do a[j,k]:=t*a[l,k]+a[j,k]; end; inc(l); end; end; procedure dai; var i,j,k:longint; begin k:=n; while (abs(a[k,n])<=zero)and(k>0) do begin if abs(a[k,n+1])>zero then begin writeln('no solution'); exit; end; dec(k); end; if k<n then begin writeln('untold solution');

充满无不能的精神

坚定必成功的信念!

6

for i:=n downto 1 do begin x[i]:=a[i,n+1]/a[i,i]; if abs(x[i])<=zero then x[i]:=0; for j:=1 to i-1 do a[j,n+1]:=a[j,n+1]-x[i]*a[j,i]; end; for i:=1 to n do if abs(x[i])<=zero then write(0,' ') else write(x[i]:0:2,' '); writeln; end; begin readln(n); for i:=1 to n do for j:=1 to n+1 do read(a[i,j]); xiao; back; end; 9.矩阵乘法 设 A 是 n 行 r 列的矩阵,B 是 r 行 m 列的矩阵,则矩阵 A,B 可相乘 矩阵 A,B 相乘后得到 n 行 m 列的 S 矩阵 且满足 S[i,j]=Σ (A[i,k]*B[k,j]),其中 1<=k<=r (应用) 若 A= { Fn-1 Fn-2 } B= 1 1 1 0 A*B={f[n],f[n-1]} 用此法可以计算较大项斐波那契数列取模后的值。

三、高精度运算
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[i],a[i]+b[i]); if c[i]>10 then begin dec(c[i],10); inc(c[i+1]); end; end; if c[len+1]>0 then inc(len); c[0]:=len; end;
7

充满无不能的精神

坚定必成功的信念!

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[i],a[i]-b[i]); if c[i]<0 then begin inc(c[i],10);dec(c[i+1]); end; 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[i],a[i]*b); inc(c[i+1],(a[i]*b) div 10); c[i]:=c[i] 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); c[0]:=len; end; 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

充满无不能的精神

坚定必成功的信念!

8

for j:=1 to b[0] do begin inc(c[i+j-1],a[i]*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; 5.高精度除以低精度 function devide(a:hp;b:longint; var c:hp; var d:longint):hp;{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[i]; c[i]:=d div b; d:=d mod b; end; while (len>1) and (c[len]=0) then dec(len); c[0]:=len; exit(c); end;

四、图论
1.spfa

**

var a,b,e:array[1..1000] of longint; vis:array[1..2000] of boolean; q,d,f:array[1..2001] of longint; n,m,i,s,t:longint; procedure qsort(l,r:longint); var i,j,x,y:longint; begin i:=l; j:=r; x:=a[(l+r) shr 1]; repeat while a[i]<x do inc(i); while a[j]>x do dec(j); if not(i>j) then begin y:=a[i]; a[i]:=a[j]; a[j]:=y;

充满无不能的精神

坚定必成功的信念!

9

y:=b[i]; b[i]:=b[j]; b[j]:=y; y:=e[i]; e[i]:=e[j]; e[j]:=y; inc(i); dec(j); end; until i>j; if i<r then qsort(i,r); if l<j then qsort(l,j); end; procedure spfa(s:longint); var i,k,l,t:longint; begin fillchar(vis,sizeof(vis),0); for i:=1 to n do d[i]:=maxlongint; d[s]:=0; l:=0; t:=1; q[1]:=s; vis[s]:=true; repeat l:=l mod 10000 +1; k:=q[l]; for i:=f[k] to f[k+1]-1 do if d[k]+e[i]<d[b[i]] then begin d[b[i]]:=d[k]+e[i]; if not vis[b[i]] then begin t:=t mod 10000 +1; q[t]:=b[i]; vis[b[i]]:=true; end; end; vis[k]:=false; until l=t; end; begin readln(n,m); for i:=1 to m do readln(a[i],b[i],e[i]); qsort(1,m); for i:=1 to m do if f[a[i]]=0 then f[a[i]]:=i; f[n+1]:=m+1; for i:=n downto 1 do if f[i]=0 then f[i]:=f[i+1]; readln(s,t); spfa(s); writeln(d[t]); end. program spfa;{By Zine.Chant}

充满无不能的精神

坚定必成功的信念!

10

type link=^node; node=record x,y:longint;{x 是指向的节点,y 是边权} next:link; end; var i,n,m,x,y,z,start,head,tail:longint; f:array[1..10000] of longint;{当前最优值} a:array[1..10000] of link; {每个点连出的边的链表的头} d:array[1..1000000] of longint; {队列} o:array[1..10000] of boolean;{检验元素是否在未被处理的队列中} r:link; procedure setup; begin assign(input,'spfa.in'); reset(input); assign(output,'spfa.out'); rewrite(output); end; procedure endit; begin close(input); close(output); end; begin setup; readln(n,m);{点和边的个数} readln(start);{起点} for i:=1 to n do begin new(a[i]); fillchar(a[i]^,sizeof(a[i]^),0);{要有初始化的好习惯} end; for i:=1 to m do begin readln(x,y,z); new(r); r^.x:=y; r^.y:=z; r^.next:=a[x]^.next; a[x]^.next:=r; new(r); r^.x:=x; r^.y:=z; r^.next:=a[y]^.next; a[y]^.next:=r; end; {读入边} head:=0; tail:=1; d[1]:=start;

充满无不能的精神

坚定必成功的信念!

11

for i:=1 to n do f[i]:=maxlongint; f[start]:=0; fillchar(o,sizeof(o),false); while head<tail do begin inc(head); o[d[head]]:=false; {这三处是 spfa 的核心优化} r:=a[d[head]]; while r^.next<>nil do begin r:=r^.next; if f[d[head]]+r^.y<f[r^.x] then begin f[r^.x]:=f[d[head]]+r^.y; if o[r^.x] then continue; {这三处是 spfa 的核心优化} inc(tail); d[tail]:=r^.x; o[d[tail]]:=true; {这三处是 spfa 的核心优化} end; end; end; for i:=1 to n do writeln(i:5,':',f[i]:8); {输出起点到每一个点的最短路径} endit; end. 2.dijkstra

**

var dist:Array[1..1001,1..1001] of longint; n,m,i,j:longint; aa,bb,zz:longint; v:array[1..1001] of boolean; procedure dijkstra(s:longint); var i,j,min,k:longint; begin v[s]:=true;dist[s,s]:=0; for i:=1 to n-1 do begin min:=10000000; for j:=1 to n do if (dist[s,j]<min)and(not v[j]) then begin k:=j; min:=dist[s,j]; end; v[k]:=true; for j:=1 to n do if dist[k,j]>0 then if (dist[s,k]+dist[k,j]<dist[s,j])or(dist[s,j]=0) then dist[s,j]:=dist[s,k]+dist[k,j]; end;

充满无不能的精神

坚定必成功的信念!

12

end; begin fillchar(dist,szieof(dist),127); readln(n,m); for i:=1 to m do begin readln(aa,bb,zz); dist[aa,bb]:=zz; end; dijkstra(1); for i:=2 to n do writeln(dist[1,i]); end. 3. kruskal

**

function find(v:longint):longint; begin if f[v]=v then exit(v) else begin f[v]:=find(f[v]);find:=f[v];end; end; begin kuaipai(1,k);//把边排序 for i:=1 to n do f[i]:=i; total:=0; for i:=1 to k do begin x:=find(a[i]); y:=find(b[i]); if x<>y then begin inc(total,w[i]); f[x]:=y; end; end; writeln(total); end. kruskal(MST) const maxn=10000; maxm=100000; var u,v,w:array[1.. maxm]of longint; fa:array[1.. maxn]of longint; n,m,x,y,i,left:longint; function getfa(i:longint):longint; begin if fa[i]=0 then exit(i); fa[i]:=getfa(fa[i]);

充满无不能的精神

坚定必成功的信念!

13

exit(fa[i]); end; begin readln(n,m); for i:=1 to m do readln(u[i],v[i],w[i]); sort(1,m); left:=n-1; for i:=1 to m do begin x:=getfa(u[i]); y:=getfa(v[i]); if x=y then continue; fa[x]:=y; writeln(u[i],' ',v[i],' ',w[i]); dec(left); if left=0 then break; end; end. 最小树形图(有向图的最小生成树) var n,m,i,ans:longint; q:array[0..102]of longint; a:array[0..102,0..102]of longint; f:array[0..102]of boolean; vis:array[0..102]of boolean; procedure init; var i,j,k,l:longint; begin readln(n,m); for i:=1 to n do for j:=1 to n do a[i,j]:=maxlongint; for i:=1 to m do begin readln(j,k,l); if l<a[j,k] then a[j,k]:=l; end; end; procedure dfs(x:longint); var j:longint; begin vis[x]:=true; for j:=1 to n do if a[x,j]<maxlongint then if not(vis[j]) then dfs(j);

充满无不能的精神

坚定必成功的信念!

14

end; function min(a,b:longint):longint; begin if a<b then exit(a); exit(b); end; procedure zhuliu; var i,j,k:longint; begin fillchar(f,sizeof(f),true); while true do begin for i:=2 to n do if f[i] then begin a[i,i]:=maxlongint; q[i]:=i; for j:=1 to n do if f[j] then if a[j,i]<a[q[i],i] then q[i]:=j; end; i:=2; while i<=n do begin if not(f[i]) then begin inc(i); continue; end; j:=i; fillchar(vis,sizeof(vis),false); while (not(vis[j]))and(j<>1) do begin vis[j]:=true; j:=q[j]; end; if j=1 then begin inc(i); continue; end; i:=j; inc(ans,a[q[i],i]); j:=q[i]; while j<>i do begin inc(ans,a[q[j],j]); f[j]:=false; j:=q[j]; end; for j:=1 to n do if f[j] then if a[j,i]<maxlongint then dec(a[j,i],a[q[i],i]); j:=q[i];

充满无不能的精神

坚定必成功的信念!

15

while j<>i do begin for k:=1 to n do if f[k] then begin if a[j,k]<maxlongint then a[i,k]:=min(a[i,k],a[j,k]); if a[k,j]<maxlongint then a[k,i]:=min(a[k,i],a[k,j]-a[q[j],j]); end; j:=q[j]; end; break; end; if i>n then begin for j:=2 to n do if f[j] then inc(ans,a[q[j],j]); break; end; end; end; begin assign(input,'raceline.in'); reset(input); assign(output,'raceline.out'); rewrite(output); fillchar(q,sizeof(q),0); fillchar(vis,sizeof(vis),false); init; dfs(1); for i:=1 to n do if not(vis[i]) then begin writeln('impossible'); close(input); close(output); halt; end; ans:=0; zhuliu; writeln(ans); close(input); close(output); end.

4.匈牙利算法 function find(v:longint):boolean; //从 v 出发找匹配 var i:longint; begin for i:=1 to m do //枚举与 v 相连的点 i if g[v,i] and (not y[i]) then //如果 i 与 v 相连且还未被访问过 begin y[i]:=true; //标记 i 已被访问过

充满无不能的精神

坚定必成功的信念!

16

if (link[i]=0)or find(link[i]) then //如果 i 无匹配或原来的匹配点 link[i]可以另找一个匹配 begin link[i]:=v; //让 v-i 与 i 匹配 find:=true; //匹配成功并返回 exit; end; end; find:=false; end; 5. Floyd // 匹配不成功

**

最短路: for k:=1 to n do for i:=1 to n do for j:=1 to n do if d[i,j]>d[i,k]+d[k,j] then d[i,j]:=d[i,k]+d[k,j]; 最小环: fillchar(f,sizeof(f),$3f div 2); fillchar(a,sizeof(a),$3f div 2); ans:=10000000; for k:=1 to n do begin for i:=1 to k-1 do for j:=i+1 to k-1 do ans:=min(ans,f[i,j]+a[i,k]+a[k,j]); for i:=1 to n do for j:=1 to n do f[i,j]:=min(f[i,j],f[i,k]+f[k,j]); end; 无向带权图最小环 program zuixiaohuan; var d,g:array[0..100,0..100] of longint; n,m,x,y,w,i,j,k,ans:longint; function min(x,y:int64):int64; begin if x>y then exit(y) else exit(x); end; begin readln(n,m); for i:=1 to n do for j:=1 to n do if i<>j then d[i,j]:=maxlongint div 3 else d[i,j]:=0; for i:=1 to m do begin readln(x,y,w); d[x,y]:=w;

充满无不能的精神

坚定必成功的信念!

17

d[y,x]:=w; end; g:=d; ans:=maxlongint div 3; for k:=1 to n do begin for i:=1 to k-1 do for j:=i+1 to k-1 do ans:=min(ans,d[i,j]+g[i,k]+g[k,j]); for i:=1 to n do for j:=1 to n do d[i,j]:=min(d[i,j],d[i,k]+d[k,j]); end; if ans<>maxlongint div 3 then writeln(ans) //输出最小环的大小 else writeln('He will never come back.'); end.

6. prime

**

procedure prim(v0:integer); var lowcost,closest:array[1..maxn] of integer; i,j,k,min,ans:integer; begin for i:=1 to n do begin lowcost[i]:=cost[v0,i]; closest[i]:=v0; //若不用输出路径,可以不用这一数组 end; for i:=1 to n-1 do begin min:=maxint; for j:=1 to n do if (lowcost[j]<min) and (lowcost[j]<>0) then begin min:=lowcost[j]; k:=j; end; inc(ans, lowcost[k]); lowcost[k]:=0; for j:=1 to n do if cost[k,j]<lowcost[j] then begin lowcost[j]:=cost[k,j]; closest[j]:=k; end; end; writeln(ans);

充满无不能的精神

坚定必成功的信念!

18

end; 7.次短路 ⑴ 删边:每次删最短路上的一条边,用 Dijkstra+堆求单源最短路径,则每次求最短路径时间复杂度为 O(N*log(N+M) + M),所以总的时间复杂度为 O(N*M*log(N+M) + M^2)。 ⑵ 2 遍 SPFA(尚有争议) ⑶ 每次更新数组 d 时保存一个 d0 次小值 8.次小生成树 {O(n^3)} 先求 MST 并记录选择的边 依次删掉这些边(n-1 次)做 MST 求出新的生成树的值 则这些值中最小的即为 the Second MST {O(n^2)} 在求 MST 的同时,对于新加入的节点,max[i][j]记录已加入的节点 i 到新加入节点 j 的路径上边权最大 的值。 求完后 mst 记录最小生成树的权值和, 枚举每一条不在树中的边 u~v, 必然与 MST 形成一个圈, max[u][v] 中 存 的 就 是 圈 中 除 了 新 加 入 的 边 外 最 大 的 边 了 。 那 么 加 入 u~v 后 , 生 成 树 的 权 值 min=mst+g[u][v]-max[u][v]; 最小的 min 就是次小生成树

9.并查集

**

begin for i:=1 to n do f[i]:=i; function find(v:longint):longint; begin if f[v]=v then exit(v) else begin f[v]:=find(f[v]); exit(f[v]); end; end; for i:=1 to n do find(i); end;

procedure find(x:longint);路径压缩 begin if father[x]=x then exit(x); father[x]:=find(father[x]); exit(father[x]); end;
trajan ① (强连通分量)

*
充满无不能的精神 坚定必成功的信念!
19

var v,f:array[1..100]of boolean;

dfn,low:array[1..100]of integer; a:array[0..100,0..100]of integer; i,j,n,m,x,y,deep,d:integer; count:longint; stack:array[1..100]of integer; function min(x,y:longint):integer; begin if x>y then exit(y) else exit(x); end; procedure print(x:integer); begin while stack[deep]<>x do begin write(stack[deep],' '); f[stack[deep]]:=false; dec(deep); end; writeln(stack[deep]); f[stack[deep]]:=false; dec(deep); end; procedure dfs(x:integer); var i:integer; begin inc(d); dfn[x]:=d; low[x]:=d; inc(deep); stack[deep]:=x; f[x]:=true; for i:=1 to a[x,0] do if not v[a[x,i]] then begin v[a[x,i]]:=true; dfs(a[x,i]); low[x]:=min(low[a[x,i]],low[x]); end else if f[a[x,i]] then begin inc(count); low[x]:=min(low[x],dfn[a[x,i]]);end; if dfn[x]=low[x] then print(x); end; begin count:=0; readln(n,m); fillchar(a,sizeof(a),0); for i:=1 to m do

充满无不能的精神

坚定必成功的信念!

20

begin readln(x,y); inc(a[x,0]); a[x,a[x,0]]:=y; end; for i:=1 to n do if not v[i] then begin v[i]:=true; dfs(i); end; writeln(count); end. ② (求 LCA) var n,m,q:longint; f,colour:array[1..1000]of longint; lca:array[1..1000,1..1000]of longint; g:array[1..1000,1..1000]of boolean; function find(x:longint):longint; begin if f[x]=x then exit(x); find:=find(f[x]); end; procedure tarjan(u:longint); var i,j:longint; begin f[u]:=u;colour[u]:=1; for i:=1 to n do if (g[u,i])and(colour[i]=0) then begin tarjan(i);f[i]:=u;end; for i:=1 to n do if (colour[i]=2)then begin lca[u,i]:=find(i);lca[i,u]:=lca[u,i];end; colour[u]:=2; end; procedure init; var i,j,x,y:longint; begin read(n,m,q); for i:=1 to m do begin read(x,y); g[x,y]:=true;g[y,x]:=true; end; for i:=1 to n do f[i]:=i; end;
21

充满无不能的精神

坚定必成功的信念!

procedure main; var i,j:longint; begin for i:=1 to n do if f[i]=i then tarjan(i); end; procedure print; var i,j,x,y:longint; begin for i:=1 to q do begin read(x,y); write(lca[x,y]); end; end; begin init; main; print; End.

五、动态规划
1.线性动规

*

① 最大递增子序列和: ans:=0;a[0]:=-1; for i:=1 to n do for j:=0 to i-1 do if (a[j]<a[i]) then begin f[i]:=max(f[i],int64(f[j])+a[i]); ans:=max(ans,f[i]); end; ② 最大连续子序列和: f[1]:=a[1]; for i:=2 to n do begin f[i]:=max(f[i-1]+a[i],a[i]); ans:=max(ans,f[i]); end; ③ 最长公共子序列和: for i:=1 to length(s1) do for j:=1 to length(s2) do if s1[i]=s2[j] then f[i,j]:=f[i-1,j-1]+1 else f[i,j]:=max(f[i-1,j],f[i,j-1]); ④ 字符串转换。 给定 A 串与 B 串,有以下三种操作:删除一个字符,插入一个字符,将一个字符改为另一个字符。求

充满无不能的精神

坚定必成功的信念!

22

将 A 串转化为 B 串的最少操作步数。 F[i,j]表示把 A 的前 i 个字符变成 B 的前 j 个字符所用的最少步数。 for i:=0 to length(A) do f[i,0]:=i; for j:=0 to length(B) do f[0,i]:=i; for i:=1 to length(A) do for j:=1 to length(B) do if A[i]=B[i] then f[i,j]:=f[i-1,j-1] else f[i,j]:=min(min(f[i-1,j],f[i,j-1]),f[i-1,j-1])+1;

⑤ 最长不下降子序列
var i,j,k:longint; procedure find(i:longint); var l,r,mid,ans:longint; begin l:=0; r:=k; repeat mid:=(l+r) shr 1; if g[mid]<=a[i] then begin ans:=mid; l:=mid+1; end else r:=mid-1; until l>r; if (g[ans+1]>a[i])or(g[ans+1]=0) then g[ans+1]:=a[i]; if ans=k then inc(k); end; begin readln(n); for i:=1 to n do read(a[i]); g[1]:=a[1]; k:=1; for i:=2 to n do find(i); writeln(k); end;

2.坐标类型动规

*

公交汽车 var a:array[1..100,1..100]of longint; f:array[1..100,1..100]of longint; i,j,k,x,y,t,n,m:longint; begin readln(n,m,k); for i:=1 to k do begin read(x,y,t); a[x,y]:=t; end; f[1,1]:=a[1,1];

充满无不能的精神

坚定必成功的信念!

23

for i:=1 to n do for j:=1 to m do begin if i-1>0 then f[i,j]:=f[i-1,j]; if j-1>0 then f[i,j]:=max(f[i,j],f[i,j-1]); inc(f[i,j],a[i,j]); end; writeln(f[n,m]); end.

3.区间型动态规划

*

区间动规的模板就是:for l:=1 to n do(枚举长度) for i:=1 to n-l+1 do(枚举区间起点) begin j:=i+l-1;(计算出区间终点); for k:=i to j do (遍历区间) f[i,j]:=按题目叙述; end;

能量项链 var h,t:array[1..202]of integer; f:array[1..202,1..202]of longint; i,j,k,l,n,ans:longint; function max(x,y:longint):longint; begin if x>y then exit(x);exit(y); end; begin assign(input,'energy.in');reset(input); assign(output,'energy.out');rewrite(output); readln(n); for i:=1 to n do begin read(h[i]); h[i+n]:=h[i]; if i>1 then begin t[i-1]:=h[i]; t[i-1+n]:=t[i-1]; end; end; t[n]:=h[1]; t[n*2]:=t[n]; for l:=1 to n-1 do for i:=1 to 2*n-l-1 do

充满无不能的精神

坚定必成功的信念!

24

begin j:=i+l; for k:=i to j-1do begin f[i,j]:=max(f[i,j],f[i,k]+f[k+1,j]+h[i]*t[k]*t[j]); end; end; for i:=1 to n do ans:=max(ans,f[i,i+n-1]); writeln(ans); close(input);close(output); end. 4.背包型动态规划

**

01 背包 var i,j:longint; begin for i:=1 to n do for j:=m downto w[i] do f[j]:=max(f[j],f[j-w[i]]+v[i]); end; 02 背包 var i,j:longint; begin for i:=1 to n do for j:=w[i] to m do f[j]:=max(f[j],f[j-w[i]]+v[i]); end; 分组背包 for k:=所有的组 do for j:=c downto 0 do for i:=组中所有的物品 do if j>=v[i] then f[j]:=max(f[j],f[j-v[i]]+w[i]); 二维费用的背包: for i:=1 to n do for j:=c1 downto v1[i] do for k:=c2 downto v2[i] do f[j,k]:=max(f[j,k],f[j-v1[i],k-v2[i]]+w[i]);

背包问题中的前 k 优解的问题*
var w,c:array[0..400]of longint; f:array[0..6000,0..100]of longint; q1,q2:array[0..50]of longint; n,v,k:longint; procedure init ;

充满无不能的精神

坚定必成功的信念!

25

begin assign(input,'RQNOJ123.in'); assign(output,'RQNOJ123.out'); reset(input); rewrite(output); end; procedure prepare; var i,j:longint; begin readln(k,v,n); for i:=1 to n do begin readln(w[i],c[i]); end; for i:=0 to v do for j:=0 to k do f[i,j]:=-maxlongint div 2; end; procedure outit; begin close(input) ; close(output); end; procedure main; var i,j,l,x1,x2,ans:longint; begin f[0,1]:=0; for i:=1to n do for j:=v downto w[i] do if f[j-w[i],1]>=0 then begin fillchar(q1,sizeof(q1),0); fillchar(q2,sizeof(q2),0); x1:=1; x2:=1; for l:=1 to k do begin q1[l]:=f[j-w[i],l]+c[i]; q2[l]:=f[j,l]; if q1[x1]>=q2[x2] then begin f[j,l]:=q1[x1]; inc(x1); end else begin f[j,l]:=q2[x2]; inc(x2);

充满无不能的精神

坚定必成功的信念!

26

end; end; end; ans:=0; for i:=1to k do ans:=ans+f[v,i]; writeln(ans); end; begin init; prepare; main; outit; end.

5.树形动规

*

二叉苹果树:在二叉苹果树上有一些苹果,先在要剪掉一些树枝,但要留下的苹果数最多。 //a[i,j]:i 节点以下删 j 个树枝的最大苹果保留数; //四种决策:①左右儿子下的树枝全删(条件是要求删的和其下树枝总数相同) // ②左子树全删,右子树删除部分(条件是要求删的≥左子树树枝总和) // ③右子树全删,左子树删除部分(条件类似上一种情况) // ④左右子树均删除部分; program apple; var tree:array[1..100]of record le,ri,lg,rg:longint; end; a:array[1..100,0..100]of longint;//每个树枝上的苹果不过 3 万不代表加起来不到 3 万 app,son:array[1..100]of longint; b:array[1..100]of boolean; i,j,k,l,n,q:longint; function max(x,y:longint):longint; begin if x>y then exit(x); exit(y); end; procedure dfs1(x,h:integer); var i,j:integer; begin if b[x]then exit; b[x]:=true;son[x]:=h; for i:=1 to n do if(a[x,i]<>-1)and(not b[i])then dfs1(i,h+1); end; procedure dfs2(x:integer); begin if tree[x].le=0 then begin

充满无不能的精神

坚定必成功的信念!

27

son[x]:=0; exit; end; dfs2(tree[x].le); dfs2(tree[x].ri); son[x]:=son[tree[x].le]+son[tree[x].ri]+2; end; procedure dfs3(x:integer); begin if son[x]=0 then begin app[x]:=0;exit;end; dfs3(tree[x].le);dfs3(tree[x].ri); app[x]:=app[tree[x].le]+app[tree[x].ri]+tree[x].lg+tree[x].rg; end; procedure dfs(x,y:integer); var i,j,k:longint;//i 要存左右儿子的苹果总数,可能会超 maxint; begin if a[x,y]<>0 then exit;//求过无需再求; if y=0 then begin a[x,y]:=app[x];exit;end;//删除数为零,直接返回其下苹果数 if(son[x]=2)then//到了叶子节点上一级节点; begin if y=1 then begin a[x,y]:=max(tree[x].lg,tree[x].rg); exit; end; if y=2 then a[x,y]:=0; exit; end; if son[x]=y then begin a[x,y]:=0;exit;end; if son[x]>y then begin if son[x]-2>=y then for k:=0 to y do begin if(son[tree[x].le]>=k)and(son[tree[x].ri]>=y-k)then begin dfs(tree[x].le,k);dfs(tree[x].ri,y-k); i:=tree[x].lg+tree[x].rg; a[x,y]:=max(a[x,y],i+a[tree[x].le,k]+a[tree[x].ri,y-k]); end; end; if y>son[tree[x].le] then begin dfs(tree[x].ri,y-1-son[tree[x].le]); a[x,y]:=max(a[x,y],a[tree[x].ri,y-1-son[tree[x].le]]+tree[x].rg); end; if y>son[tree[x].ri] then begin

充满无不能的精神

坚定必成功的信念!

28

dfs(tree[x].le,y-1-son[tree[x].ri]); a[x,y]:=max(a[x,y],a[tree[x].le,y-1-son[tree[x].ri]]+tree[x].lg); end; exit; end; end; begin assign(input,'apple.in');reset(input); assign(output,'apple.out');rewrite(output); readln(n,q);q:=n-1-q;//注意 q 是要保留的! fillchar(b,sizeof(b),false); fillchar(a,sizeof(a),$Ff);//树枝上可能只有 0 个苹果,所以初始化为-1; fillchar(son,sizeof(son),0);//双重作用,首先存每个节点的深度,后来为节点以下的树枝数; fillchar(app,sizeof(app),0);//每个节点以下的苹果数; fillchar(tree,sizeof(tree),0); for i:=1 to n-1 do begin readln(j,k,l); a[k,j]:=l; a[j,k]:=l; end; dfs1(1,1);//递归求出每个节点的深度; for i:=1 to n do//建树 for j:=i+1 to n do begin if(a[i,j]<>-1)and(son[i]+1=son[j])then begin if tree[i].le=0 then begin tree[i].le:=j; tree[i].lg:=a[i,j]; end else begin tree[i].ri:=j; tree[i].rg:=a[i,j]; end; end; if(a[i,j]<>-1)and(son[i]-1=son[j])then begin if tree[j].le=0 then begin tree[j].le:=i; tree[j].lg:=a[i,j]; end else begin tree[j].ri:=i;

充满无不能的精神

坚定必成功的信念!

29

tree[j].rg:=a[i,j]; end; end; end; fillchar(son,sizeof(son),0); dfs2(1);//求树枝数; dfs3(1);//求苹果数; fillchar(a,sizeof(a),0);//a[i,j]i 节点以下删 j 个树枝的最大苹果保留数; dfs(1,q); writeln(a[1,q]); close(input);close(output); end. 提前处理: 1.数组 l[i],r[i],分别表示 i 的左右子树的根节点; 2.数组 sumt[i],,表示以 i 为结点的子树有多少条树枝; 3.数组 map[I,j],表示(i,j)这条枝上的苹果数。 用 F[I,j]表示以 i 为结点的树删掉 j 条枝还剩下的最多苹果,三种情况: 1. 只在两棵子树中删掉 j 条枝: f[I,j]:=max(f[l[i],k]+f[r[i],j-k]+map[I,l[i]]+map[I,r[i]]) (方程成立的条 件:sumt[l[i]]>=k 且 sumt[r[i]]>=j-k) ; 2.删掉整棵左子树,那么右子树还需删掉 j-sumt[l[i]]-1 条枝:f[I,j]:=f[r[i], j-sumt[l[i]]-1]+map[I,r[i]](方 程成立条件:j>= j-sumt[l[i]]-1) ; 3.删掉整棵右子树,那么左子树还需删掉 j-sumt[r[i]]-1 条枝:f[I,j]:=f[l[i], j-sumt[r[i]]-1]+map[I,l[i]](方 程成立条件:j>= j-sumt[l[i]]-1) ; 三种情况取较大者。 program apple; type node=record x,y,w:longint; end; var f,map:Array[0..100,0..100] of longint; sumt,l,r,w:array[1..100] of longint; dep:array[0..100] of longint; e:array[0..100] of node; b:array[0..100] of boolean; n,q,x,y,ap,i,lz:longint; function max(x,y:longint):longint; begin if x>y then exit(x) else exit(y); end; procedure build(i:longint); var j:longint; begin if i>n then exit; for j:=1 to n do if (not b[j])and(map[i,j]<>-1) then begin

充满无不能的精神

坚定必成功的信念!

30

if l[i]=0 then begin l[i]:=j; b[j]:=true; build(j); continue; end; if r[i]=0 then begin r[i]:=j; b[j]:=true; build(j); end; end; end; procedure dfss(i:longint); begin if l[i]=0 then begin sumt[i]:=0; exit; end; dfss(l[i]); dfss(r[i]); sumt[i]:=sumt[l[i]]+sumt[r[i]]+2; end; procedure work(i:longint); var j,k:longint; begin if l[i]=0 then exit; if l[i]<>0 then work(l[i]); if r[i]<>0 then work(r[i]); for j:=0 to sumt[i] do begin for k:=0 to j do if (sumt[l[i]]>=k)and(sumt[r[i]]>=j-k) then f[i,j]:=max(f[i,j],f[l[i],k]+f[r[i],j-k]+map[i,l[i]]+map[i,r[i]]); if (j>=sumt[l[i]]+1)and(sumt[r[i]]>=j-sumt[l[i]]-1) then f[i,j]:=max(f[i,j],f[r[i],j-sumt[l[i]]-1]+map[i,r[i]]); if (j>=sumt[r[i]]+1)and(sumt[l[i]]>=j-sumt[r[i]]-1) then f[i,j]:=max(f[i,j],f[l[i],j-sumt[r[i]]-1]+map[i,l[i]]); end; end; begin assign(input,'apple.in');reset(input); assign(output,'apple.out');rewrite(output); readln(n,q);

充满无不能的精神

坚定必成功的信念!

31

fillchar(map,sizeof(map),$ff); for i:=1 to n-1 do begin readln(x,y,ap); map[x,y]:=ap; map[y,x]:=ap; end; b[1]:=true; build(1); dfss(1); work(1); writeln(f[1,n-1-q]); close(input); close(output); end.

六、基本算法策略
1.KMP(字符串匹配) var s:ansistring; m,ans:longint; next,l,r,temp:array[0..10000]of longint; procedure get_next(t:ansistring); var i,j,k,l:longint; begin l:=length(t); k:=0; next[1]:=0; for i:=2 to l do begin while (k>0)and(t[i]<>t[k+1]) do k:=next[k]; if t[i]=t[k+1] then inc(k); next[i]:=k; end; end; procedure kmp1(s,t:ansistring); var i,j,l1,l2,k:longint; begin fillchar(next,sizeof(next),0); get_next(t); k:=0; l1:=length(s);l2:=length(t); for i:=1 to l1 do begin while (k>0)and(s[i]<>t[k+1]) do k:=next[k]; if s[i]=t[k+1] then inc(k); l[i]:=k; if k=l2 then exit;

充满无不能的精神

坚定必成功的信念!

32

end; end; procedure uget_next(t:ansistring); var i,j,l,k:longint; begin fillchar(next,sizeof(next),0); l:=length(t); k:=l+1;next[l]:=k; for i:=l-1 downto 1 do begin while (k<l+1)and(t[i]<>t[k-1]) do k:=next[k]; if t[i]=t[k-1] then dec(k); next[i]:=k; end; end; procedure kmp2(s,t:ansistring); var i,j,l1,l2,k:longint; begin uget_next(t); l1:=length(s);l2:=length(t); k:=l2+1; for i:=l1 downto 1 do begin while (k<l2+1)and(t[k-1]<>s[i]) do k:=next[k]; if s[i]=t[k-1] then dec(k); r[i]:=l2+1-k; if k=1 then exit; end; end; procedure check(s,ss:ansistring); var i,j,l1,l2:longint; begin l1:=length(s);l2:=length(ss); for i:=1 to l1 do if l[i]<l[i-1] then l[i]:=l[i-1]; for i:=1 to l1-1 do if l[i]+r[i+1] >=l2 then begin inc(ans);break;end; end; procedure main; var i,j,n:longint;ss:ansistring; begin readln(s); readln(m); for i:=1 to m do begin readln(ss); if length(ss)<2 then continue; kmp1(s,ss);kmp2(s,ss);

充满无不能的精神

坚定必成功的信念!

33

check(s,ss); end; end; begin main; write(ans); End. 2.RMQ(倍增) var fmax,fmin:array[0..20,1..51000] of longint; n,i,j,ma,mi,l,r,q,t:longint; function max(x,y:longint):longint; begin if x>y then exit(x) else exit(y); end; function min(x,y:longint):longint; begin if x>Y then exit(y) else exit(x); end; begin readln(n,q); t:=trunc(ln(n)/ln(2)); for i:=1 to n do begin readln(fmax[0,i]); fmin[0,i]:=fmax[0,i]; end; for i:=1 to t do for j:=1 to n do begin fmax[i,j]:=max(fmax[i-1,j],fmax[i-1,j+(1 << (i-1))]); fmin[i,j]:=min(fmin[i-1,j],fmin[i-1,j+(1 << (i-1))]); end; for i:=1 to q do begin readln(l,r); t:=trunc(ln(r-l+1)/ln(2)); ma:=max(fmax[t,l],fmax[t,r-(1 << t)+1]); mi:=min(fmin[t,l],fmin[t,r-(1 << t)+1]); writeln(ma,' ',mi); end; end. 3.单调队列 var temp,ans:int64; n,p,q,i,j:longint;

*

充满无不能的精神

坚定必成功的信念!

34

a:array[0..400000] of longint; b,r,l:array[0..400000] of longint; begin readln(n); for i:=1 to n do read(a[i]); p:=1;q:=0; for i:=1 to n+1 do begin while (p<=q) and (a[i]<a[b[q]]) do begin r[b[q]]:=i; dec(q); end; inc(q);b[q]:=i; end; fillchar(b,sizeof(b),0); p:=1;q:=0; for i:=n downto 0 do begin while (p<=q) and (a[i]<a[b[q]]) do begin l[b[q]]:=i; dec(q); end; inc(q);b[q]:=i; end; for i:=1 to n do begin temp:=(r[i]-l[i]-1)*a[i]; if temp>ans then ans:=temp; end; writeln(ans); end. 4.树状数组//《全国青少年信息学竞赛培训教材》 ⑴ ① (求逆序对) var c,a,b:array[0..100]of longint; q,n,ans:longint; procedure sqort(l,r:longint); var i,j,med,k:longint; begin if l>=r then exit; i:=l-1;j:=r+1; med:=a[random(r-l)+l]; while i<j do begin repeat inc(i); until a[i]>=med;

充满无不能的精神

坚定必成功的信念!

35

repeat dec(j); until a[j]<=med; if i<j then begin k:=a[i];a[i]:=a[j];a[j]:=k; k:=b[i];b[i]:=b[j];b[j]:=k; end; end; sqort(l,j);sqort(j+1,r); end; procedure init; var i,j:longint; begin read(n); for i:=1 to n do begin read(a[i]); b[i]:=i; end; randomize; sqort(1,n); c:=a; end; procedure add(x:longint); var i,j:longint; begin i:=x; while i<=n do begin c[i]:=c[i]+1; i:=i+(i and(-i)); end; end; function sum(k:longint):longint; var i,j:longint; begin i:=k; j:=0; while i>0 do begin j:=j+c[i]; i:=i-(i and (-i)); end; exit(j); end; procedure main;

充满无不能的精神

坚定必成功的信念!

36

var i,j,k:longint; begin k:=0; for i:=1 to n do if c[i]<>c[i-1] then begin inc(k);a[b[i]]:=k;end else a[b[i]]:=k; fillchar(c,sizeof(c),0); for i:=1 to n do begin inc(ans,sum(k)-sum(a[i])); add(a[i]); end; i:=1; end; begin init; main; write(ans); end. ② (区间求和) var c,a:array[1..10000]of longint; n,q:longint; function orbit(i:longint):longint; var p:longint; begin p:=i and (i xor (i-1)); exit(p); end; procedure chang(i,t:longint); var j:longint; begin j:=i; while j<=n do begin c[j]:=c[j]+a[i]; j:=j+orbit(j); end; end; procedure init; var i,j:longint; begin read(n,q); for i:=1 to n do begin read(a[i]);

充满无不能的精神

坚定必成功的信念!

37

chang(i,a[i]); end; end; function check(k:longint):longint; var i,j,tot:longint; begin j:=k;tot:=0; while j>=1 do begin inc(tot,c[j]); j:=j-orbit(j); end; exit(tot); end; procedure main; var i,j,l,r,p1,q1:longint; begin for i:=1 to q do begin read(l,r); p1:=check(l-1);q1:=check(r); writeln(q1-p1); end; end; begin init; main; End. ⑵ 单点修改,区间求和: program szsz; var n,m,a,b,t,i:longint; date,c:array[1..100001] of longint; function lowbit(x:longint):longint; begin exit(x and -x); end; procedure modify(x,a:longint); begin while x<=n do begin inc(c[x],a); inc(x,lowbit(x)); end; end;

充满无不能的精神

坚定必成功的信念!

38

function sum(x:longint):longint; begin sum:=0; while x>0 do begin inc(sum,c[x]); dec(x,lowbit(x)); end; end; begin readln(n,m); for i:=1 to n do begin read(date[i]); modify(i,date[i]); end; for i:=1 to m do begin readln(t,a,b); if t=0 then begin modify(a,-date[a]); modify(a,b); date[a]:=b; end else writeln(sum(b)-sum(a-1)); end; end. ⑶ 区间修改,区间求和: program szsz_qujianxiugai; var c,f:array[0..400000] of int64; s1,s2,a1,a2,a3,a4:int64; n,m,i,a,b,d:longint; s:array[0..100001] of int64; ch:char; function lowbit(x:longint):longint; begin exit(x and -x); end; procedure insert(k:longint;a:int64); begin while k<=n do begin c[k]:=c[k]+a; k:=k+lowbit(k); end;

充满无不能的精神

坚定必成功的信念!

39

end; function sum(k:longint):int64; begin sum:=0; while k>0 do begin sum:=sum+c[k]; k:=k-lowbit(k); end; end; procedure insert1(k:longint;a:int64); begin while k<=n do begin f[k]:=f[k]+a; k:=k+lowbit(k); end; end; function sum1(k:longint):int64; begin sum1:=0; while k>0 do begin sum1:=sum1+f[k]; k:=k-lowbit(k); end; end; begin readln(n,m); for i:=1 to n do begin read(a); s[i]:=s[i-1]+a; end; readln; for i:=1 to m do begin read(ch); if ch='C' then begin readln(a,b,d); insert(a,d); insert(b+1,-d); insert1(a,d*a); insert1(b+1,-d*(b+1)); end else begin

充满无不能的精神

坚定必成功的信念!

40

readln(a,b); a1:=sum(b); a2:=sum(a-1); a3:=sum1(b); a4:=sum1(a-1); s1:=a1*(b+1)-a3+s[b]; s2:=a2*a-a4+s[a-1]; writeln(s1-s2); end; end; end.

5.堆操作

**

var big,small:array[1..20000]of longint; n,l,tot1,tot2:longint; procedure up1(x:longint); var i,j,b:longint; begin b:=small[x]; j:=x; while j>1 do begin i:=j shr 1; if small[i]>b then begin small[j]:=small[i];j:=i;end; if small[i]<=b then break; end; small[j]:=b; end; procedure up2(x:longint); var i,j,b:longint; begin b:=big[x]; j:=x; while j>1 do begin i:=j shr 1; if big[i]<b then begin big[j]:=big[i];j:=i;end; if big[i]>=b then break; end; big[j]:=b; end; procedure down1(x:longint); var i,j,b:longint; begin j:=1;b:=big[1]; while j<x do

充满无不能的精神

坚定必成功的信念!

41

begin i:=j shl 1; if i>x then break; if big[i]<big[i+1] then inc(i); if big[i]>b then begin big[j]:=big[i];j:=i;end; if big[i]<=b then break; end; big[j]:=b; end; procedure down2(x:longint); var i,j,b:longint; begin b:=small[1];j:=1; while j<x do begin i:=j shl 1; if i>x then break; if small[i]>small[i+1] then inc(i); if small[i]<b then begin small[j]:=small[i];j:=i;end; if small[i]>=b then break; end; small[j]:=b; end; procedure work1; var i,j,x:longint; begin readln(x); if l=0 then begin inc(tot2);small[tot2]:=x;up1(tot2);exit;end; if (tot1>0)and(x<big[1]) then begin inc(tot2);small[tot2]:=big[1];up1(tot2); big[1]:=x;down1(tot1); end else begin inc(tot2);small[tot2]:=x;up1(tot2); end; end; procedure work2; var i,j:longint; begin readln;inc(l); inc(tot1);big[tot1]:=small[1];up2(tot1); small[1]:=small[tot2];dec(tot2);down2(tot2); end;
42

充满无不能的精神

坚定必成功的信念!

procedure main; var i,j:longint;ch:char;ff:boolean; begin readln(n); for i:=1 to n do begin read(ch); if ch='M' then work1; if ch='L' then work2; if ch='W' then begin writeln(big[1]); end; end; end; begin main; end. 6.计算凸包 const maxn=500; type p=record x,y:longint; end; var n,top:longint; a:array[0..maxn]of p; s:array[0..maxn]of longint; procedure swap(var a,b:p); var t:p; begin t:=a; a:=b; b:=t; end; function cha(p1,p2,p0:p):longint; begin exit((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y)); end; function comp(p1,p2:p):boolean; var t:longint; begin t:=cha(p1,p2,a[0]); if (t>0)or ((t=0)and (sqr(p1.x-a[0].x)+sqr(p1.y-a[0].y)<sqr(p2.x-a[0].x)+sqr(p2.y-a[0].y)))

充满无不能的精神

坚定必成功的信念!

43

then exit(true) else exit(false); end; procedure graham; var i:longint; begin for i:=1 to 3 do s[i]:=i-1; top:=3; for i:=3 to n-1 do begin while cha(a[i],a[s[top]],a[s[top-1]])>=0 do dec(top); inc(top); s[top]:=i; end; for i:=1 to top do writeln('(',a[s[i]].x,' ',a[s[i]].y,')'); end; procedure sort(l,r:longint); var i,j:longint; x:p; begin if r-l+1<=5 then begin for j:=l+1 to r do begin i:=j; while (i>1)and(comp(a[i],a[i-1])) do begin swap(a[i],a[i-1]); dec(i); end; end end else begin x:=a[l+random(r-l+1)]; i:=l; j:=r; repeat while comp(a[i],x) do inc(i); while comp(x,a[j]) do dec(j); if not(i>j) then begin swap(a[i],a[j]); inc(i); dec(j); end; until i>j; if l<j then sort(l,j); if i<r then sort(i,r); end; end;

充满无不能的精神

坚定必成功的信念!

44

procedure init; var i:longint; begin readln(n); for i:=0 to n-1 do begin readln(a[i].x,a[i].y); if (a[i].y<a[0].y)or((a[i].y=a[0].y)and(a[i].x<a[0].x)) then swap(a[i],a[0]); end; sort(1,n-1); end; begin init; graham; End. 7.线段树 Type//简单求数轴上线段长度 treetype=record a,b,li,ri,cov:longint; end; var tre:array[0..10000]of treetype; numb,tot,c,d:longint; procedure maketree(a,b:longint); var now:longint; begin inc(tot); now:=tot; tre[now].a:=a; tre[now].b:=b; tre[now].cov:=0; if a+1<b then begin tre[now].li:=tot+1; maketree(a,(a+b)shr 1); tre[now].ri:=tot+1; maketree((a+b)shr 1,b); end; end; procedure insert(num:longint); begin if (c<=tre[num].a)and(tre[num].b<=d) then tre[num].cov:=tre[num].cov+1 else begin if c<(tre[num].a+tre[num].b) div 2 then insert(tre[num].li); if d>(tre[num].a+tre[num].b) div 2 then insert(tre[num].ri); end; end; procedure delete(num:longint);

充满无不能的精神

坚定必成功的信念!

45

begin if (c<tre[num].a)and(tre[num].b<=d) then dec(tre[num].cov) else begin if c<(tre[num].a+tre[num].b) div 2 then delete(tre[num].li); if d>(tre[num].a+tre[num].b) div 2 then delete(tre[num].li); end; end; procedure count(num:longint); begin if tre[num].cov>0 then numb:=numb+(tre[num].b-tre[num].a) else begin if tre[num].li>0 then count(tre[num].li); if tre[num].ri>0 then count(tre[num].ri); end; end; begin readln(c,d); maketree(c,d); while not eof do begin readln(c,d); insert(1); end; count(1); writeln(numb); End. (1) 单点修改,区间查询: program xianduantree; var d,ql,qr,root,tot,ans,n,m,i:longint; key,l,r:array[0..200000] of longint; a:Array[0..100000] of longint; function max(x,y:longint):longint; begin if x>y then exit(x) else exit(y); end; procedure update(x:longint); begin key[x]:=max(key[l[x]],key[r[x]]); end; function build(s,t:longint):longint; var mid,now:longint; begin inc(tot);

充满无不能的精神

坚定必成功的信念!

46

now:=tot; if s=t then begin key[now]:=a[s]; exit(now); end; mid:=(s+t) div 2; l[now]:=build(s,mid); r[now]:=build(mid+1,t); update(now); exit(now); end; procedure query(x,s,t:longint); var mid:longint; begin if (ql<=s)and(qr>=t) then begin ans:=max(ans,key[x]); exit; end; mid:=(s+t) div 2; if ql<=mid then query(l[x],s,mid); if qr>mid then query(r[x],mid+1,t); end; procedure insert(x,s,t:longint); var mid:longint; begin if (ql=s)and(s=t) then begin key[x]:=qr; exit; end; mid:=(s+t) div 2; if ql<=mid then insert(l[x],s,mid) else insert(r[x],mid+1,t); update(x); end; begin readln(n,m); for i:=1 to n do read(a[i]); root:=build(1,n); for i:=1 to m do begin readln(d,ql,qr); 充满无不能的精神 坚定必成功的信念!
47

if d=1 then begin ans:=-maxlongint; query(root,1,n); writeln(ans); end else insert(root,1,n); end; end. (2) 区间修改,区间查询: program xianduantree_qujianxiugai; var tmp,d,ql,qr,root,tot,i,j,n,m,ans:longint; delta,key,l,r:array[0..200000] of longint; a:array[0..100000] of longint; function max(x,y:longint):longint; begin if x>y then exit(x) else exit(y); end; procedure update(x:longint); begin key[x]:=max(key[l[x]],key[r[x]]); end; procedure paint(x,y:longint); begin key[x]:=key[x]+y; delta[x]:=delta[x]+y; end; procedure pushdown(x:longint); begin paint(l[x],delta[x]); paint(r[x],delta[x]); delta[x]:=0; end; function build(s,t:longint):longint; var now,mid:longint; begin inc(tot); now:=tot; if s=t then begin key[now]:=a[s]; exit(now); end; mid:=(s+t) div 2; l[now]:=build(s,mid); r[now]:=build(mid+1,t); 充满无不能的精神 坚定必成功的信念!
48

update(now); exit(now); end; procedure query(x,s,t:longint); var mid:longint; begin if (ql<=s)and(qr>=t) then begin ans:=max(ans,key[x]); exit; end; pushdown(x); mid:=(s+t) div 2; if ql<=mid then query(l[x],s,mid); if qr>mid then query(r[x],mid+1,t); end; procedure insert(x,s,t:longint); var mid:longint; begin if (ql<=s)and(qr>=t) then begin paint(x,tmp); exit; end; pushdown(x); mid:=(s+t) div 2; if ql<=mid then insert(l[x],s,mid); if qr>mid then insert(r[x],mid+1,t); update(x); end; begin readln(n,m); for i:=1 to n do read(a[i]); root:=build(1,n); for i:=1 to m do begin read(d,ql,qr); if d=1 then begin ans:=-maxlongint; query(root,1,n); writeln(ans); end else begin readln(tmp); //区间 ql 到 qr 增加 tmp

充满无不能的精神

坚定必成功的信念!

49

insert(root,1,n); end; end; end. ⑶ 划分树 type node=record l,r,mid:longint; end; var n,m,i:longint; tree:array[0..600000]of node; a:array[0..100002]of longint; g,f:array[0..50,0..100002]of longint; procedure qsort(l,r:longint); var t,x,i,j:longint; begin i:=l; j:=r; x:=a[(l+r) shr 1]; repeat while a[i]<x do inc(i); while a[j]>x do dec(j); if not(i>j) then begin t:=a[i]; a[i]:=a[j]; a[j]:=t; inc(i); dec(j); end; until i>j; if l<j then qsort(l,j); if i<r then qsort(i,r); end; procedure build(k,l,r,deep:longint); var mid,i,t1,t2:longint; begin tree[k].l:=l; tree[k].r:=r; mid:=(l+r) shr 1; tree[k].mid:=mid; if l=r then exit; t1:=l-1; t2:=mid; for i:=l to r do if (g[deep-1,i]<=a[mid])and(t1<mid) then begin inc(t1); g[deep,t1]:=g[deep-1,i]; if i=l then f[deep,i]:=1 else f[deep,i]:=f[deep,i-1]+1; end else begin inc(t2); g[deep,t2]:=g[deep-1,i]; if i=l then f[deep,i]:=0 else f[deep,i]:=f[deep,i-1]; end; build(2*k,l,mid,deep+1); build(2*k+1,mid+1,r,deep+1); end; procedure ask(x,y,k,m,deep:longint); var t1,t2,tl,ll,rr:longint;

充满无不能的精神

坚定必成功的信念!

50

begin if (x=tree[m].l)and(y=tree[m].r) then begin writeln(a[x+k-1]); exit; t1:=f[deep,y]; if x<=tree[m].l then t2:=0 else t2:=f[deep,x-1]; tl:=t1-t2; if k<=tl then begin ll:=tree[m].l+t2; rr:=ll+tl-1; ask(ll,rr,k,2*m,deep+1); end else begin ll:=tree[m].mid+1+x-tree[m].l-t2; rr:=ll+y-x-tl; ask(ll,rr,k-tl,2*m+1,deep+1); end; end; procedure work; var x,y,k,i:longint; begin for i:=1 to m do begin readln(x,y,k); ask(x,y,k,1,1); end; end; begin readln(n,m); for i:=1 to n do begin read(a[i]); g[0,i]:=a[i]; end; qsort(1,n); build(1,1,n,1); work; end. 8.hash 表(挂链法) const mo=29; type line=^node; node=record data,poi:longint; nxt:line; end; var ha:array[0..mo]of line; i,j,n,m,k:longint; procedure putin(x,i:longint);//把 x 插入 ha[i]中,在首段插入 var p:line; begin new(p); p^.data:=x; p^.nxt:=ha[i]; ha[i]:=p; end;

end;

充满无不能的精神

坚定必成功的信念!

51

function hash(x:longint):boolean; var p:line;i,j:longint; begin i:=x mod mo; p:=ha[i]; while p<>nil do begin if p^data=x then exit(true);// p:=p^.nxt; end; putin(x,i); exit(false); end; begin readln(n); for i:=1 to n do begin read(x); putin(x,x mod mo); end; for i:=1 to n do begin read(x); writeln(hash(x)); end; End. 9.随机数获取 program sadf; uses crt; var b,c,a:integer; begin clrscr; c:=99; randomize; a:=random(c); readln(b); while b<>a do begin if b=250 then begin writeln('=',a); readln; exit; end; if b>a then writeln('da') else if b<a then writeln('xiao'); readln(b);

充满无不能的精神

坚定必成功的信念!

52

end; writeln('ok'); readln; end.

七、排序算法

1.冒泡排序

** **

for i:=1 to n do for j:=1 to i-1 do if a[j]>a[i] then swap(a[i],a[j]); 2.插入排序

procedure insert_sort; var i,j:integer; begin for i:=2 to n do begin a[0]:=a[i]; j:=i-1; while a[0]<a[j] do begin a[j+1]:=a[j]; j:=j-1; end; a[j+1]:=a[0]; end;

充满无不能的精神

坚定必成功的信念!

53

end; 3.快速排序

**

procedure qsort(l,r:integer); var i,j,mid:integer; begin i:=l; j:=r; mid:=a[(l+r)>>1]; repeat while a[i]<mid do inc(i); while a[j]>mid do dec(j); if i<=j then begin swap(a[i],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; 4.归并排序(求逆序对)

**

type love=record x,y:longint; end; var n,i:longint; ans:int64; a:array[1..300000] of longint; c:array[1..300000] of longint; procedure merge(l,r:longint); var t,mid,i,p,q:longint; begin if l>=r then exit; mid:=(l+r) div 2; merge(l,mid); merge(mid+1,r); p:=l; q:=mid+1; t:=l-1; repeat inc(t); if a[p]>a[q] then begin c[t]:=a[q]; inc(q); inc(ans,mid-p+1);//不需要求逆序对时不要此步

充满无不能的精神

坚定必成功的信念!

54

end else begin c[t]:=a[p]; inc(p); end; until (p>mid)or(q>r); if p<=mid then begin for i:=p to mid do begin inc(t); c[t]:=a[i]; end; end else begin for i:=q to r do begin inc(t); c[t]:=a[i]; end; end; for i:=l to r do a[i]:=c[i]; end; begin readln(n); for i:=1 to n do read(a[i]); merge(1,n); for i:=1 to n do write(a[i],' '); writeln; writeln(ans); //输出逆序对数。 end. 5.堆排序

*

procedure sift(i,m:integer);{调整以 i 为根的子树成为堆,m 为结点总数} var k:integer; begin a[0]:=a[i]; k:=2*i;{在完全二叉树中结点 i 的左孩子为 2*i,右孩子为 2*i+1} while k<=m do begin if (k<m) and (a[k]<a[k+1]) then inc(k);{找出 a[k]与 a[k+1]中较大值} if a[0]<a[k] then begin a[i]:=a[k]; i:=k; k:=2*i; end

充满无不能的精神

坚定必成功的信念!

55

else k:=m+1; end; a[i]:=a[0]; {将根放在合适的位置} end; procedure heapsort; var j:integer; begin for j:=n div 2 downto 1 do sift(j,n); for j:=n downto 2 do begin swap(a[1],a[j]); sift(1,j-1); end; end;

八、位运算(and/or/xor/not/shl/shr)

1.and 运算 and 运算通常用于二进制取位操作 例如一个数 and 1 的结果就是取二进制的最末位。这可以用来判断一个整数的奇偶,二进制的最 末位为 0 表示该数为偶数,最末位为 1 表示该数为奇数. 2.or 运算 or 运算通常用于二进制特定位上的无条件赋值 例如一个数 or 1 的结果就是把二进制最末位强行变成 1。如果需要把二进制最末位变成 0,对这个 数 or 1 之后再减一就可以了,其实际意义就是把这个数强行变成最接近的偶数。 3.xor 运算 xor 运算通常用于对二进制的特定一位进行取反操作,因为异或可以这样定义:0 和 1 异或 0 都不 变,异或 1 则取反。 xor 运算的逆运算是它本身,也就是说两次异或同一个数最后结果不变,即(a xor b) xor b = a。xor 运算可以用于简单的加密。 4.not 运算 not 运算的定义是把内存中的 0 和 1 全部取反。使用 not 运算时要格外小心,你需要注意整数类型 有没有符号。如果 not 的对象是无符号整数(不能表示负数) ,那么得到的值就是它与该类型上界的差, 5.shl 运算 a shl b 就表示把 a 转为二进制后左移 b 位(在后面添 b 个 0) 。 a shl b 的值实际上就是 a 乘以 2 的 b 次方 通常认为 a shl 1 比 a * 2 更快 定义一些常量可能会用到 shl 运算。你可以方便地用 1 shl 16 - 1 来表示 65535。很多算法和数据结 构要求数据规模必须是 2 的幂,此时可以用 shl 来定义 Max_N 等常量。 6.shr 运算 a shr b 表示二进制右移 b 位(去掉末 b 位) ,相当于 a 除以 2 的 b 次方(取整) 。我们也经常用 shr 1 来代替 div 2,比如二分查找、快排等等。想办法用 shr 代替除法运算可以使程序效率大大提高。最大 公约数的二进制算法用除以 2 操作来代替慢得出奇的 mod 运算,效率可以提高 60%。 7.位运算总结 功能 | 示例 | 位运算 ----------------------+---------------------------+--------------------

充满无不能的精神

坚定必成功的信念!

56

去掉最后一位 在最后加一个 0 在最后加一个 1 把最后一位变成 1 把最后一位变成 0 最后一位取反 把右数第 k 位变成 1 把右数第 k 位变成 0 右数第 k 位取反 取末三位 取末 k 位 取右数第 k 位 把末 k 位变成 1 末 k 位取反 把右边连续的 1 变成 0 把右起第一个 0 变成 1 把右边连续的 0 变成 1 取右边连续的 1 去掉右起第一个 1 的左边

| (101101->10110) | (101101->1011010) | (101101->1011011) | (101100->101101) | (101101->101100) | (101101->101100) | (101001->101101,k=3) | (101101->101001,k=3) |(101001->101101,k=3) | (1101101->101) | (1101101->1101,k=5) | (1101101->1,k=4) | (101001->101111,k=4) |(101001->100110,k=4) | (100101111->100100000) | (100101111->100111111) | (11011000->11011111) | (100101111->1111) | (100101000->1000)

| x shr 1 | x shl 1 | x shl 1+1 | x or 1 | x or 1-1 | x xor 1 | x or (1 shl (k-1)) | x and not (1 shl (k-1)) | x xor (1 shl (k-1)) | x and 7 | x and (1 shl k-1) | x shr (k-1) and 1 | x or (1 shl k-1) | x xor (1 shl k-1) | x and (x+1) | x or (x+1) | x or (x-1) | (x xor (x+1)) shr 1 | x and (x xor (x-1))

九、程序时间测试
uses sysutils; var tt:real; begin Tt:=time; 主程序体 writeln((time-tt)*3600*24:0:2,’s’); end.

充满无不能的精神

坚定必成功的信念!

57

十、注意事项

1.考试中在一定的时间如果没有想出过全点的算法就抓紧时间编写一个能过部分点的朴素或可过样 例的骗分算法。 2.考试应该想好了在编程前要想好算法编写时要思考语句是否会带来不良的影响。 3.考试时要善于发现规律,而且推出某个规律时,要多次进行验证以保证其正确性。 4.看题时一定要仔细,特别是某些没有样例的题。 5.当算法正确,程序错误时,暂时放弃,过几天再重打一遍。 6 考试时要注意数据范围,当数据范围较小时可先使用枚举等方法然后再进行动规或搜索。 7 考试时要在重要的(可能出错的)地方用笔划记,使不该犯的错误尽可能避免,每次都能发挥出自 己的水平。 8. 一个题目不一定就是只有一种算法可能是几个算法的结合。 9.注意题目中 x 与 y 所代表的意义;m 与 n 所代表的意义。 10.程序编写完成时要注意特殊情况和极端情况的考虑。 11.在所有题目编完后,要出几个极限数据判断是否会出现 201、215 等错误。 12.在遇到数学或物理问题时要先把问题分析清楚,再编程。 13.考试时想到的思路和思维的闪光要在草稿纸上记录下来,再验证其可行性(包括:编程复杂度、 实现时间、时间复杂度、空间复杂度),可行性较低的要及时舍弃。 14.如果实在想不到好的算法就赶快打一个搜索。 15.数组最好比题目中的数据范围大一些,避免边境情况未考虑完全时出现 201。 16.能开 int64 的尽量开,数组最好从 0 开始 17.做题时不要一开始就想骗分算法,最好先想正确算法。 18.出现了矩阵的题目时要注意搜索或动规的顺序,是先行在列,还是先列再行。 19.在循环次数较多和递归深度较深的时候尽量减少使用 fillchar,以防超时和 202。 20.并查集在合并完所有的集合后记住再进行一次状态压缩,指向最终代表元。 21.审题时注意对关键条件和特殊范围的把握,他们一般是题目解答的突破口。 22.如果题意要求输出某个数,但这个数难求易于验证,一般可以用二分解决。

充满无不能的精神

坚定必成功的信念!

58


推荐相关:

冲刺NOIP之整理

投诉违规内容,请到百度文库投诉中心;如提出功能问题或意见建议,请点击此处进行反馈。 冲刺NOIP之整理 冲刺NOIP2012知识点整理、冲刺NOIP2012知识点整理、隐藏>>...


NOIP冲刺模拟题

NOIP冲刺模拟题_学科竞赛_高中教育_教育专区。高 2016...【思路点拨】 一般多询问的问题要么是具有比较短的...树上的倍增法求 LCA,掌握 #include<cstdlib> #...


冲刺NOIP2010模拟试题与解析(一)

冲刺NOIP2010模拟试题与解析(一)_学科竞赛_初中教育_教育专区。题目名称题目程序...下面 h 行描述居民的需 要:b e t(0...


冲刺NOIP2010 报数题解

冲刺NOIP2010 报数题解_学科竞赛_高中教育_教育专区。报数【题目描述】 CG 同学...的左侧或者右侧不存在非零数 字(这里只考虑整数部分)则这一段“零”不应 该...


冲刺NOIP2012模拟试题(十)

冲刺NOIP2012模拟试题(十) - 习题 1. 2. 3. 编号 ...


NOIP2013冲刺训练(第十五组)

投诉违规内容,请到百度文库投诉中心;如提出功能问题或意见建议,请点击此处进行反馈。 NOIP2013冲刺训练(第十五组) NOIP2013冲刺训练(第十五组)NOIP2013冲刺...


冲刺noip2011模拟试题

冲刺NOIP 2011 模拟试题题目 失落的神庙 失落的猴子 被遗忘的时光 反素数 程序...(一开始颜色为 0) ,每次我会把其中的一个矩形染成一 种颜色,最后你要告诉...


★冲刺NOIP 2010模拟试题六

冲刺NOIP 2010模拟试题六_调查/报告_表格/模板_实用文档。模拟题冲刺...这个 Black Box 要处理一串命令 命令只有两种: ADD(x) : 把 x 元素放进 ...


冲刺Noip2010模拟试题

投诉违规内容,请到百度文库投诉中心;如提出功能问题或意见建议,请点击此处进行反馈。 冲刺Noip2010模拟试题 冲刺Noip2010模拟试题冲刺Noip2010模拟试题隐藏>> ...


冲刺NOIP2010模拟试题

冲刺NOIP2010模拟试题_公务员考试_资格考试/认证_教育专区 暂无评价|0人阅读|0次下载|举报文档 冲刺NOIP2010模拟试题_公务员考试_资格考试/认证_教育专区。...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com