tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> 电脑基础知识 >>

NOIP算法总结


NOIP 算法总结
BY.W.X 吃了、还得睡 (一)数论 1.最大公约数,最小公倍数 2.筛法求素数 3. mod 规律公式 4.排列组合数,错排 5.Catalan 数 6.康拓展开 7 负进制 8.中位数的应用 9.位运算 (二)高精度算法 1. 朴素加法减法 2. 亿进制加法减法 3. 乘法 4. 除法 5. 亿进制读入处理 6. 综合应用 (三)排序算法 1. 冒泡 2 快排 3 堆排 4 归并 (四)DP 1. 概念 2. 解题步骤 3. 背包类 DP 4. 线性 DP 5. .区间动态规划 6. 坐标型动态规划(规则类 DP) 7. 资源分配型动态规划 8. 树型动态规划 9. 状态压缩的动态规划 10. 动态规划的一般优化方法 (五)图论 1. Floyd-Warshall 2. Bellman-ford 3. SPFA 4. dijkstra


5. prim 6. kruskal 7. 欧拉回路 8. 哈密顿环 9. flood fill(求图的强连通分量) 10. 最小环问题(基于 floyd) 11. Topological sort 12. 次短路 13. 次小生成树 (六)树 1.堆 2. 二叉排序树 3. 最优二叉树(哈夫曼树) 4.求树的后序遍历 5.并查集及应用 (七)分治 1.二分查找 2.二分逼近(注意精度问题) 3.二分答案 4.快排(见排序算法) 5.归并排序(见排序算法) 6.快速幂 (八)贪心 (九)搜索 (十)其它 1. 离散化 2. KMP 3. 字符串哈希 4. 常用字符串函数过程

(一)数论
1. 最大公约数,最小公倍数


function gcd(a,b:longint):longint; begin if b=0 then gcd:=a else gcd:=gcd(b,a mod b); end; function jslcm(a,b:longint):longint; begin jslcm:=a div gcd(a,b)*b;(先 div 防 215) end;

2.筛法求素数
var f:array[1..10000000] of boolean; su:array[1..100000] of longint; sj,n,i,j:longint; begin readln(sj); fillchar(f,sizeof(f),true); f[2]:=true; for i:=2 to sj do if f[i] then begin j:=i+i; while j<sj do begin f[j]:=false; j:=j+i; end; end; for i:=2 to sj do if f[i] then begin inc(n); su[n]:=i; end; end.

3. mod 规律公式 结合律 ((a+b) mod p + c)mod p = (a + (b+c) mod p) mod p ((a*b) mod p * c)mod p = (a * (b*c) mod p) mod p 分配律 ((a +b)mod p × c) mod p = ((a × c) mod p + (b × c) mod p) mod p 4.排列组合数,错排 A(n,m)=n!/(n-m)! C(n,m):=n!/m!(n-m)! 错排 通项 f[n]:=n![1-1/1!+1/2!-1/3!……+(-1)^n*1/n!] (利用容斥原理证明)


递推式 f[n]:=(n-1)*(f[n-1]+f[n-2]) (加法原理) 5.Catalan 数 (1)公式 h(n)=C(2n,n)/(n+1) (n=1,2,3,...) 【计算过程中可用质因子表优化】 (2)应用 01 串,出栈序列
对于一个二进制的 01 串,共 n+m 位,满足 n 个 1,m 个 0,且 0<=n-m<=1,该串 还满足从左向右 1 的个数永远大于 0 的个数。问:共有多少种排列方式? 此题可理解为进出栈问题,n 个元素组成的队列,共有多少种进出栈的方式? 答案是满足卡特兰数的,即 n 个元素的进出站顺序为 h(n)=c(2n,n)/(n+1) ; 为什么呢? 在 2n 位二进制数中填入 n 个 1 的方案数为 c(2n,n),不填 1 的其余 n 位自动填 0。从中减去 不符合要求(由左而右扫描,0 的累计数大于 1 的累计数)的方案数即为所求。 h(n)=c(2n,n)-c(2n,n-1)=c(2n,n)/(n+1) ; 推广:当 n<>m 时,即 1 的个数为 n,0 的个数为 m 排列方式的总数为:c(n+m,m)-c(n+m,m-1) =c(n+m,n-1)*(n-m+1)/m;

6.康拓展开
function ktzk(s:string):longint; const jc:array[1..8] of longint=(1,2,6,24,120,720,5040,40320); var i,j,num,tem,l:longint; begin l:=length(s); num:=0; for i:=1 to l-1 do begin tem:=0; for j:=i+1 to l do if s[i]>s[j] then inc(tem); num:=num+tem*jc[8-i]; end; ktzk:=num; end;

7.负进制
const ch:array[0..19]ofchar=('0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','I','J'); var n,r,x,y,z,nn,i:longint; ans:array[1..2000]of longint; begin readln(n,r); x:=0; nn:=n; repeat;



inc(x); ans[x]:=n mod r; n:=n div r; if ans[x]<0 then begin; ans[x]:=ans[x]-r; n:=n+1; end; until n=0; write(nn,'='); for i:=x downto 1 do write(ch[ans[i]]); writeln('(base',r,')'); end.

8.中位数的应用(应用:士兵站队)
var min,i,j,n,h,mid:longint; x,y:array[1..10000] of longint; procedure qs1(s,t:longint); procedure qs2(s,t:longint); begin readln(n); for i:=1 to n do read(x[i],y[i]); qs1(1,n);(对 y 排序) min:=0; mid:=y[n div 2+1]; for i:=1 to n do min:=min+abs(y[i]-mid); qs2(1,n); (对 x 排序) for i:=1 to n do x[i]:=x[i]-i+1; qs2(1,n); (对 x 排序) mid:=x[n div 2+1]; for i:=1 to n do min:=min+abs(x[i]-mid); writeln(min); end.

9.位运算 (1) 基本操作
and or 运算通常用于二进制特定位上的无条件赋值,例如一个数 or 1 的结果就是把二进制最 末位强行变成 1。如果需要把二进制最末位变成 0,对这个数 or 1 之后再减一就可以了,其 实际意义就是把这个数强行变成最接近的偶数。 xor 0 和 1 异或 0 都不变,异或 1 则取反。



例:对 01 串 0101010 之类,改变某一位上的值,只需 xor 某一位,如:对有数第三位取 反,只需 xor 4; 对有数第三位和第二位同时取反,只需 xor 6; not;not 运算的定义是把内存中的 0 和 1 全部取反。 .Shl 通常认为 a shl 1 比 a * 2 更快,因为前者是更底层一些的操作。因此程序中乘以 2 的操作请尽量用左移一位来代替。 shr; 我们也经常用 shr 1 来代替 div 2 (2) 应用 计算二进制中的 1 的个数 同样假设 x 是一个 32 位整数。经过下面五次赋值后,x 的值就是原数的二进制表示中数字 1 的个数。比如,初始时 x 为 1314520 那么最后 x 就变成了 9,它表示 1314520 的二进制中有 9 个 1。 x := (x and $55555555) + ((x shr 1) and $55555555); x := (x and $33333333) + ((x shr 2) and $33333333); x := (x and $0F0F0F0F) + ((x shr 4) and $0F0F0F0F); x := (x and $00FF00FF) + ((x shr 8) and $00FF00FF); x := (x and $0000FFFF) + ((x shr 16) and $0000FFFF); 为了便于解说, 我们下面仅说明这个程序是如何对一个 8 位整数进行处理的。 我们拿数字 211 来开刀。211 的二进制为 11010011。 +---+---+---+---+---+---+---+---+ | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | <---原数 +---+---+---+---+---+---+---+---+ | 1 0 | 0 1 | 0 0 | 1 0 | <---第一次运算后 +-------+-------+-------+-------+ | 0 0 1 1 | 0 0 1 0 | <---第二次运算后 +---------------+---------------+ | 00000101 | <---第三次运算后,得数为 5 +-------------------------------+ 整个程序是一个分治的思想。第一次我们把每相邻的两位加起来,得到每两位里 1 的个数, 比如前两位 10 就表示原数的前两位有 2 个 1。 第二次我们继续两两相加, 10+01=11, 00+10=10, 得到的结果是 00110010,它表示原数前 4 位有 3 个 1,末 4 位有 2 个 1。最后一次我们把 0011 和 0010 加起来,得到的就是整个二进制中 1 的个数。程序中巧妙地使用取位和右移,比如第二 行中$33333333 的二进制为 00110011001100....,用它和 x 做 and 运算就相当于以 2 为单位间 隔取数。shr 的作用就是让加法运算的相同数位对齐。 例题:玩欺诈的小杉 描述 Description 是这样的, 在小杉的面前有一个 N 行 M 列的棋盘, 棋盘上有 N*M 个有黑白棋的棋子 (一 面为黑,一面为白) ,一开始都是白面朝上。 小杉可以对任意一个格子进行至多一次的操作(最多进行 N*M 个操作) ,该操作使得与该格 同列的上下各 2 个格子以及与该格同列的左右各 1 个格子以及该格子本身翻面。 例如,对于一个 5*5 的棋盘,仅对第三行第三列的格子进行该操作,得到如下棋盘(0 表示 白面向上,1 表示黑面向上) 。



00100 00100 01110 00100 00100 对一个棋盘进行适当的操作,使得初始棋盘(都是白面朝上)变成已给出的目标棋盘的操作 集合称作一个解法。 小杉的任务是对给出的目标棋盘求出所有解法的总数。 输入格式 Input Format 每组测试数据的 第一行有 3 个正整数,分别是 N 和 M 和 T(1<=N,M<=20,1<=T<=5) 接下来 T 个目标棋盘,每个目标棋盘 N 行,每行 M 个整数之前没有空格且非 0 即 1,表示 目标棋盘(0 表示白面朝上,1 表示黑面朝上) 两个目标棋盘之间有一个空行。 特别地,对于 30%的数据,有 1<=N,M<=15 输出格式 Output Format 对每组数据输出 T 行,每行一个整数,表示能使初始棋盘达到目标棋盘的解法总数 var z,m,n,t,ans,i,j,l,k:longint; en:array[1..21] of longint; s:string; procedure find(x:longint); var las,mak,i,ls:longint; begin las:=0; mak:=x; for i:=1 to m do begin ls:=mak; mak:=(mak xor en[i] xor (mak shl 1)xor(mak shl 2) xor(mak shr 1)xor(mak shr 2) xor las)and k; las:=ls; end; if mak=0 then inc(ans); end; begin readln(n,m,t); for z:=1 to t do begin fillchar(en,sizeof(en),0); for i:=1 to n do begin readln(s); for j:=1 to m do



en[j]:=en[j]*2+ord(s[j])-48; end; ans:=0; k:=1 shl n -1; for i:=1 to k do find(i); writeln(ans); readln; end; end.

(二)高精度算法
1.朴素加法减法
var a,b,c:array[1..10000] of longint; jin,x,la,lb,lc,i:longint; s1,s2:string; procedure jiafa; begin if la>lb then lc:=la else lc:=lb; jin:=0; for i:=1 to lc do begin x:=a[i]+b[i]+jin; c[i]:=x mod 10; jin:=x div 10; end; if jin<>0 then begin inc(lc);c[lc]:=jin;end; for i:=lc downto 1 do write(c[i]); writeln; end; procedure jianfa; begin fillchar(c,sizeof(c),0); if la>lb then lc:=la else lc:=lb; for i:=1 to lc do begin c[i]:=c[i]+a[i]-b[i]; if c[i]<0 then begin inc(c[i],10);dec(c[i+1]); end; end; while (c[lc]=0)and(lc>0) do dec(lc); for i:=lc downto 1 do


write(c[i]); writeln; end; begin readln(s1); readln(s2); la:=length(s1); lb:=length(s2); for i:=1 to la do a[i]:=ord(s1[la-i+1])-48; for i:=1 to lb do b[i]:=ord(s2[lb-i+1])-48; jiafa; if (lb>la)or((la=lb)and(s1<s2)) then begin write('-');x:=la;la:=lb;lb:=x;c:=a;a:=b;b:=c;end; jianfa; end.

2.亿进制加法减法
背景: 笨笨骨牌(domino.pas/c/cpp) 笨笨对多米诺骨牌有很大的兴趣,然而他的骨牌比较特别,只有黑色的和白色的两种。他觉得如果存在 连续三个骨牌是同一科颜色,那么这个骨牌排列便是不美观的。现在他有 n 个骨牌要来排列,他想知道不美 观的排列的个数。由于数字较大,数学不好的他不会统计,所以他请你来帮忙。希望你在一秒内求出不美观 的排列的个数。 【输入格式】 只有一个正整数,即要排列的骨牌个数。 【输出格式】 一个数,即不美观的排列个数。 【样例输入】 4 【样例输出】 6 【样例解释】 有四种不美观的排列。 黑黑黑黑,白白白白,黑黑黑白,白白白黑,黑白白白,白黑黑黑 【数据范围】 20%的数据,n≤60; 50%的数据,n≤600; 100%的数据,n≤10000

type arr=array[1..1000] of longint; var lf,lg:array[0..10000] of longint; f,g:array[0..10000] of arr; er:arr;



i,j,m,n,ler:longint; function gj1(a,b:arr;la,lb:longint;var lc:longint):arr; var c:arr;i,j,jin,x:longint; begin jin:=0; fillchar(c,sizeof(c),0); if la>lb then lc:=la else lc:=lb; for i:=1 to lc do begin x:=a[i]+b[i]+jin; c[i]:=x mod 100000000; jin:=x div 100000000; end; if jin<>0 then begin inc(lc);c[lc]:=jin; end; gj1:=c; end; function gj2(a,b:arr;la:longint;var lc:longint):arr; var i,j,x:longint; begin for i:=1 to la do begin x:=a[i]-b[i]; if x<0 then begin x:=x+100000000;dec(a[i+1]); end; a[i]:=x; end; while (a[la]=0)and(la>0) do dec(la); lc:=la; gj2:=a; end; begin readln(n); f[0][1]:=0;g[0][1]:=2; f[1][1]:=0;g[1][1]:=2; f[2][1]:=0;g[2][1]:=4; er[1]:=4; ler:=1; for i:=0 to 2 do begin lf[i]:=1;lg[i]:=1;end; for i:=3 to n do begin er:=gj1(er,er,ler,ler,ler); f[i]:=gj1(f[i-1],f[i-1],lf[i-1],lf[i-1],lf[i]); f[i]:=gj1(f[i],g[i-3],lf[i],lg[i-3],lf[i]); g[i]:=gj2(er,f[i],ler,lg[i]);

10

end; write(f[n][lf[n]]); for i:=lf[n]-1 downto 1 do if f[n][i]>=10000000 then write(f[n][i]) else if f[n][i]>=1000000 then write('0',f[n][i]) else if f[n][i]>=100000 then write('00',f[n][i]) else if f[n][i]>=10000 then write('000',f[n][i]) else if f[n][i]>=1000 then write('0000',f[n][i]) else if f[n][i]>=100 then write('00000',f[n][i]) else if f[n][i]>=10 then write('000000',f[n][i]) else write('0000000',f[n][i]); writeln; end.

3.乘法
procedure chengfa; var c:array[1..200] of integer; i,j,lc,x:integer; cod:char; begin fillchar(c,sizeof(c),0); cod:='+'; if ca<>cb then cod:='-'; for i:=1 to la do for j:=1 to lb do begin c[i+j-1]:=c[i+j-1]+a[i]*b[j]; c[i+j]:=c[i+j]+c[i+j-1] div 10; c[i+j-1]:=c[i+j-1] mod 10; end; lc:=la+lb; while (lc>1)and(c[lc]=0) do dec(lc); if cod='-' then write(cod); for i:=lc downto 1 do write(c[i]); end;

4.除法
(1) 计算 A/B 的精确值,设 A,B 是一般整数,计算机可接受的数,精确小数后 20 位。不考虑四舍五入。 输入:两个数,n m 输出:n/m 的结果。 Sample Input 32 Sample Output 3/2=1.50000000000000000000

11

var a,b,i,j,l:integer; c:array[0..21] of integer; procedure prepare; begin l:=0; c[0]:=a div b; end; procedure gchu; begin while l<20 do begin a:=(a-c[l]*b)*10; c[l+1]:=a div b; inc(l); end; end; begin readln(a,b); write(a,'/',b,'='); prepare; gchu; write(c[0],'.'); for i:=1 to 20 do write(c[i]); end.
(2)计算 A/B 的精确值,设 A 是高精度数(不超过 100 位) ,B 是一般整数,计算机可接受的数,精 确小数后 100 位。不考虑四舍五入。 输入:第一行被除数 n,第二行除数 m 输出:n/m 的结果。 Sample Input 3 2 Sample Output 1.5

var c:array[1..1000] of longint; aa:string; a:array[1..100] of longint; b,i,j,la,l,beg,en:longint; cho:boolean; begin cho:=false; readln(aa);

12

readln(b); la:=length(aa); for i:=1 to la do a[i]:=ord(aa[i])-48; i:=1; while i<=la do begin c[i]:=a[i] div b; a[i+1]:=a[i+1]+(a[i]-c[i]*b)*10; inc(i); end; dec(i); if a[i+1]=0 then cho:=true; l:=i+1; while (l-i<=100) do begin c[l]:=a[i+1] div b; a[i+1]:=(a[i+1]-c[l]*b)*10; inc(l) end; beg:=1; while c[beg]=0 do inc(beg); en:=l-1; while (c[en]=0)and(a[i+1]=0) do dec(en); for j:=beg to i do write(c[j]); if cho then exit; write('.'); for j:=i+1 to en do write(c[j]); end.

7. 亿进制读入
readln(s); la:=length(s); p:=0; while la>0 do begin inc(p); ls:=copy(s,la-7,8); s:=copy(s,1,la-8); la:=length(s); val(ls,a[p]); end;

6.应用
13

红豆玲珑骰(mark.pas/c/cpp) 【题目描述】 红豆玲珑骰一共六面,每一面上有+、-、*其中之一的符号。每当骰子落下后,hh4742 的 两条卷轴就会自动打开,上面分别显示有一个整数。 你所要做的工作,就是将这两个整数用骰子朝上的一面上显示的符号运算得出结果。 【输入格式】 第一行,骰子上显示的符号。 第二行,一个整数 a。 第三行,一个整数 b。 (-10^69<=a,b<=10^69) 【输出格式】 输出文件共一行,即计算得来的结果。 【输入样例】 * -50 6 【输出样例】 -300 var a,b,h:array[1..71] of integer; ch,fu,sign:char; ca,cb:boolean; i,j,m,n,la,lb,lh:longint; s1,s2,hs:string; procedure int; begin readln(fu); readln(s1); la:=length(s1); ca:=true; if s1[1]='-' then begin ca:=false; dec(la);delete(s1,1,1);end; while (s1[1]='0')and(la>1) do begin dec(la); delete(s1,1,1); end; for i:=la downto 1 do a[la-i+1]:=ord(s1[i])-48; readln(s2); lb:=length(s2); cb:=true; if s2[1]='-' then begin cb:=false; dec(lb);delete(s2,1,1);end; while (s2[1]='0')and(lb>1) do begin dec(lb);

14

delete(s2,1,1); end; for i:=lb downto 1 do b[lb-i+1]:=ord(s2[i])-48; end; procedure jiafa; var x,w,jin,i:integer; begin if la>lb then w:=la else w:=lb; jin:=0; for i:=1 to w do begin x:=a[i]+b[i]+jin; a[i]:=x mod 10; jin:=x div 10; end; if jin<>0 then begin inc(w);a[w]:=jin; end; la:=w; if sign='-' then write(sign); for i:=la downto 1 do write(a[i]); writeln; end; procedure jianfa; var jie,i,x,w:integer; cod:char; begin cod:='+'; if (la<lb)or((la=lb)and(s1<s2)) then cod:='-'; if cod='-' then begin h:=a;a:=b;b:=h;lh:=la;la:=lb;lb:=lh;end; jie:=0; for i:=1 to la do begin x:=jie+a[i]-b[i]; if x<0 then begin jie:=-1;x:=x+10;end; a[i]:=x mod 10; end; if (la<>1)and(a[la]=0) then dec(la); if cod='-' then write(cod); for i:=la downto 1 do write(a[i]); end; procedure chengfa; var c:array[1..142] of integer; i,j,lc,x:integer; cod:char;

15

begin fillchar(c,sizeof(c),0); cod:='+'; if ca<>cb then cod:='-'; for i:=1 to la do for j:=1 to lb do begin c[i+j-1]:=c[i+j-1]+a[i]*b[j]; c[i+j]:=c[i+j]+c[i+j-1] div 10; c[i+j-1]:=c[i+j-1] mod 10; end; lc:=la+lb; while (lc>1)and(c[lc]=0) do dec(lc); if cod='-' then write(cod); for i:=lc downto 1 do write(c[i]); end; begin int; sign:='+'; if (fu='+')and(ca)and(cb) then jiafa; if (fu='+')and(not ca)and(not cb) then begin sign:='-';jiafa;end; if (fu='+')and(ca)and(not cb) then jianfa; if (fu='+')and(not ca)and(cb) then begin h:=a;a:=b;b:=h;lh:=la;la:=lb;lb:=lh;hs:=s1;s1:=s2;s2:=hs;jianfa; end; if (fu='-')and(ca)and(cb) then jianfa; if (fu='-')and(ca)and(not cb) then jiafa; if (fu='-')and(not ca)and(not cb) then begin h:=a;a:=b;b:=h;lh:=la;la:=lb;lb:=lh;jianfa;end; if (fu='-')and(not ca)and(cb) then begin sign:='-';jiafa;end; if fu='*' then chengfa; end.

(三)排序算法
1. 冒泡
var temp,i,j,k,n:integer; a:array[1..1000]of longint; begin ; readln(n); for i:=1 to n do read(a[i]); for i:=1 to n-1 do for j:=1 to n-i do if a[j]<a[j+1] then
16

begin; temp:=a[j]; a[j]:=a[j+1];a[j+1]:=temp; end; for i:=1 to n do write(a[i],' '); writeln; end.

2. 快排 (1) 不稳定
procedure qs(s,t:longint); var x,i,j,h:longint; begin i:=s;j:=t; x:=a[(i+j)div 2]; repeat while a[i]<x do inc(i); while a[j]>x do dec(j); if i<=j then begin h:=a[i];a[i]:=a[j];a[j]:=h; h:=b[i];b[i]:=b[j];b[j]:=h;inc(i);dec(j);end; until i>j; if i<t then qs(i,t); if s<j then qs(s,j); end;

(2) 稳定
procedure qs(s,t:longint); var i,j,sub:longint; x:int64; begin i:=s;j:=t; x:=a[(i+j)div 2]; sub:=b[(i+j)div 2]; repeat while (a[i]<x)or((x=a[i])and(b[i]<sub)) do inc(i); while (a[j]>x)or((a[j]=x)and(b[j]>sub)) do dec(j); if i<=j then begin h:=a[i];a[i]:=a[j];a[j]:=h; hb:=b[i];b[i]:=b[j];b[j]:=hb; inc(i);dec(j);end; until i>j; if i<t then qs(i,t); if s<j then qs(s,j); end;

3 堆排 背景:NOIP2004 合并果子
var

17

a:array[1..10000] of longint; t,i,j,k,n,len,g1,g2:longint; procedure ins(k:longint); var s,h:longint; begin inc(len); a[len]:=k; s:=len; while (s<>1)and(a[s div 2]>a[s])do begin h:=a[s]; a[s]:=a[s div 2]; a[s div 2]:=h; s:=s div 2 end; end; function heap:longint; var h,fa,s:longint; sto:boolean; begin heap:=a[1]; a[1]:=a[len]; dec(len); fa:=1;sto:=false; while ((fa*2<=len) or (fa*2+1<=len))and (not sto) do begin if (fa*2+1>len)or(a[fa*2]<a[fa*2+1]) then s:=fa*2 else s:=fa*2+1; if a[fa]>a[s] then begin h:=a[fa];a[fa]:=a[s];a[s]:=h; fa:=s end else sto:=true; end; end; begin readln(n); len:=0; t:=0; for i:=1 to n do begin read(k); ins(k); end; for i:=1 to n-1 do begin g1:=heap;

18

g2:=heap; t:=t+g1+g2; ins(g1+g2); end; writeln(t); end.

4 归并 背景:求逆序对
procedure msort(s,t:longint); var i,j,k,m:longint; begin if s=t then exit; m:=(s+t)div 2; msort(s,m); msort(m+1,t); i:=s;j:=m+1; k:=s; while (i<=m)and(j<=t) do if a[i]<=a[j] then begin r[k]:=a[i];inc(i);inc(k);end else begin inc(total,m-i+1); r[k]:=a[j];inc(j);inc(k);end; while i<=m do begin r[k]:=a[i];inc(k);inc(i);end; while j<=t do begin r[k]:=a[j];inc(k);inc(j);end; for i:=s to t do a[i]:=r[i]; end;

(四)DP
1.概念
在多阶段决策的问题中,各个阶段采取的决策,一般来说是与时间或空间有关的。决策 依赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来,故 有“动态”的含义,我们称这种解决多阶段决策最优化的过程为动态规划方法。 阶段:把所求问题的过程按照时间或空间恰当地分成若干个相互联系的阶段。 状态:表示每个阶段的客观状态,它既是某阶段的出发位置,又是前一阶段的终点。 无后效性: 如果给定某一阶段的状态, 则在这一阶段以后过程的发展不受这阶段以前各 段状态的影响,所以各阶段确定时,整个过程也就确定了。 决策:一个阶段的状态给定以后,从该状态演变到下一阶段状态的一种选择(行动)。 策略:由每个阶段的决策组成的序列。 最优性原理:把一个大问题划分成多个子问题,对于整个问题必须最优的情况时,问 题也必须最优,即问题具备最优子结构的性质。

2. 解题步骤
(1)判断问题是否具有最优子结构性质,若不具备,则不能用动态规划。 (2)把问题分成若干个子问题(分阶段)。 、 (3)建立状态转移方程(递推公式)。 (4)找出边界条件。
19

(5)设定初始值。 (6)递推求解。

3. 背包类 DP (1) 0/1 背包
var n,m,i,j:longint; w,c:array[1..30] of longint; f:array[0..100000] of longint; function max(a,b:longint):longint; begin if a>=b then exit(a) else exit(b); end; begin readln(n,m); for i:=1 to n do readln(w[i],c[i]); fillchar(f,sizeof(f),0); for i:=1 to n do for j:=m downto w[i] do f[j]:=max(f[j-w[i]]+c[i],f[j]); writeln(f[m]); end.

(2) 完全背包
var n,m,i,j:longint; w,c:array[1..30] of longint; f:array[0..100000] of longint; function max(a,b:longint):longint; begin if a>=b then exit(a) else exit(b); end; begin readln(n,m); for i:=1 to n do readln(w[i],c[i]); fillchar(f,sizeof(f),0); for i:=1 to n do for j:=w[i] to m do f[j]:=max(f[j-w[i]]+c[i],f[j]); writeln(f[m]); end.

(3)二维费用背包
背景:潜水员为了潜水要使用特殊的装备。他有一个带 2 种气体的气缸:一个为氧气,一个为氮气。让

20

潜水员下潜的深度需要各种的数量的氧和氮。潜水员有一定数量的气缸。每个气缸都有重量和气体容量。 潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总重的最低限度的是多少? 例如:潜水员有 5 个气缸。每行三个数字为:氧,氮的(升)量和气缸的重量: 3 36 120 10 25 129 5 50 250 1 45 130 4 20 119 如果潜水员需要 5 升的氧和 60 升的氮则总重最小为 249 (1,2 或者 4,5 号气缸) 。 你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。 【输入格式】 第一行有 2 整数 t,a(1<=t<=21,1<=a<=79) 。它们表示氧,氮各自需要的量。 第二行为整数 n (1<=n<=1000)表示气缸的个数。 此后的 n 行,每行包括 ti,ai,wi(1<=ti<=21,1<=ai<=79,1<=wi<=800)3 整数。这些各自是:第 i 个气缸里的氧和氮的容量及汽缸重量。 【输出格式】 仅一行包含一个整数,为潜水员完成工作所需的气缸的重量总和的最低值

var f:array[0..21,0..79] of longint; i,j,k,n,t,a,j1,k1:longint; ti,ai,w:array[1..1000] of longint; function min(a,b:longint):longint; begin if a<=b then exit(a) else exit(b); end; begin readln(t,a); readln(n); fillchar(f,sizeof(f),$7f); for i:=1 to n do readln(ti[i],ai[i],w[i]); f[0,0]:=0; for i:=1 to n do for j:=t downto 0 do for k:=a downto 0 do begin if j+ti[i]>t then j1:=t else j1:=j+ti[i]; if k+ai[i]>a then k1:=a else k1:=k+ai[i]; f[j1,k1]:=min(f[j,k]+w[i],f[j1,k1]); end; writeln(f[t,a]); end.

(4)多重背包及优化(二进制,单调队列)
若有 n 种物品,背包容量为 m,物品体积、价值、最大使用次数为 v,w,c,则朴素的动

21

规方程为: f[i]=max{f[i-v*k]+w*k} (1<=k<=c)。 我们把所有可能达到的体积按照除以当前物品 体积 v 的余数划分为 0~v-1,则当余数为 k(k∈[0,v-1])时又可以划分为 k,k+v,k+2*v…k+j*v… (1<=j<=(m-k)div v)这几种具体的体积,由于对于余数为 k 时的转移只会发生在以上列举 出的几个体积上, 所以可以建立关于以上几个体积的单调队列, 以便于快速地找到最优决策。 但是这里要注意一点,由于这几个决策的体积和价值都不相同,直接没有可比性,所以我们 把这些决策的体积统一到为 k 时比较,统一方法只需要利用体积为 k+j*v 这一特点,把需要 插入队中的 f[k+j*v]的价值减去 j*w,就是当体积为 k 时的一个可以用于比较的“参考”价值。 可以很容易想到: 由于转移时, 使用当前物品贡献的那一部分是二者之差, 所以这与减掉 j*w 之前是等效的。 这样,每次求 f[k+j*v]时,只需要在队列中找到一个最优的决策 f[k+j’*v],使得 j-j’<=c 即可, 剩下的工作就只有维护单调队列了。 procedure insert(x,y:longint); //插入到一个价值单调递减,使用次数单调递增的队列中 begin while (l<=r)and(b[r]<=y) do dec(r); inc(r);a[r]:=x;b[r]:=y; end; begin readln(n,m); //n 为物品个数、m 为背包容量 for i:=1 to n do begin read(v,w,c); //读入当前物品:v 为物品体积、w 为物品价值、c 为物品可用次数 if m div v<c then c:=m div v; //最多可使用次数 for k:=0 to v-1 do //把所有的体积按除以 v 的余数划分为 0~v-1 begin l:=1;r:=0; //清空队列 for j:=0 to (m-k) div v do //余数为 k 的又分为 k,v+k,2*v+k…j*v+k… begin insert(j,f[j*v+k]-j*w); //等效于把体积统一到 k,价值减去 j*w,这样比较优劣才有意义 while a[l]<j-c do inc(l); //删除次数超过 c 的 f[j*v+k]:=b[l]+j*w; //用队列头的值更新 f[j*v+k] end; end; end; writeln(f[m]); end.

4. 线性 DP

22

?线型动态规划问题,最典型的特征就是状态都在一条线上,并且位置固定,问 题一般都规定只能从前往后取状态,解决的办法是根据前面的状态特征,选取最 优状态作为决策进行转移。 ?设前 i 个点的最优值,研究前 i-1 个点与前 i 个点的最优值, ?利用第 i 个点决策转移 状态转移方程一般可写成: fi(k) = min{ fi-1 or j( k’) + u(i,j) or u(i,i-1) } (1) LIS 最长不降子序列 {n^2}
begin; readln(n); for x:=1 to n do read(a[x]); for x:=1 to n do f[x]:=1; for x:=2 to n do for y:=1 to x-1 do if a[x]>a[y] then f[x]:=max(f[x],f[y]+1); for x:=1 to n do if f[x]>ans then ans:=f[x]; writeln(ans); end.

{nlogn}(二分法)
var i,j,m,n,a,t:longint; f:array[1..100000] of longint; function find(l,r:longint):longint; begin while (r-l>1) do begin m:=(l+r) div 2; if f[m]=a then exit(m); if f[m]<a then r:=m else l:=m; end; exit(r); end; begin readln(n); t:=0;f[t]:=maxlongint; for i:=1 to n do begin read(a); if a=0 then continue; if a<f[t] then begin inc(t);f[t]:=a;end else f[find(0,t)]:=a;

23

end; writeln(t); end.

(2)LCS 最长公共序列
var s1,s2:ansistring; i,j,l1,l2:integer; f0,f1:array[0..5000] of longint; function max(a,b:longint):longint; begin if a>=b then exit(a) else exit(b); end; begin readln(s1); readln(s2); l1:=length(s1); l2:=length(s2); dec(l1);dec(l2); fillchar(f0,sizeof(f0),0); fillchar(f1,sizeof(f1),0); for i:=1 to l1 do begin f0:=f1; for j:=1 to l2 do if s1[i]=s2[j] then f1[j]:=f0[j-1]+1 else f1[j]:=max(f0[j],f1[j-1]); end; writeln(f1[l2]); end.

(3)例题:移动服务
(service.pas/c/cpp) 【问题描述】 一个公司有三个移动服务员。如果某个地方有一个请求,某个员工必须赶到那个地方去(那个地方没 有其他员工) ,某一时刻只有一个员工能移动。被请求后,他才能移动,不允许在同样的位置出现两 个员工。从 p 到 q 移动一个员工,需要花费 c(p,q)。这个函数没有必要对称,但是 c(p,p)=0。公司必 须满足所有的请求。目标是最小化公司花费。 【输入格式】: 第一行有两个整数 L,N(3<=L<=200, 1<=N<=1000)。L 是位置数 ;N 是请求数。每个位置从 1 到 L 编 号。下 L 行每行包含 L 个非负整数。第 i+1 行的第 j 个数表示 c(i,j) ,并且它小于 2000。最后一行包 含 N 个数,是请求列表。一开始三个服务员分别在位置 1,2,3。 【输出格式】: 一个数 M,表示最小服务花费

24

var f,f1:array[0..200,0..200] of longint; a:array[1..200,1..200] of longint; q:array[1..1000] of integer; i,j,m,n,k,min:longint; function fmin(a,b:longint):longint; begin if a<=b then exit(a) else exit(b); end; begin readln(n,m); for i:=1 to n do for j:=1 to n do read(a[i,j]); for i:=1 to m do read(q[i]); fillchar(f,sizeof(f),$7f); fillchar(f1,sizeof(f1),$7f); f1[1,2]:=a[3,q[1]]; f1[2,3]:=a[1,q[1]]; f1[1,3]:=a[2,q[1]]; for k:=1 to m-1 do begin fillchar(f,sizeof(f),$7f); for i:=1 to n do for j:=1 to n do if (i<>j)and(i<>q[k])and(j<>q[k]) then if f1[i,j]<>2139062143 then begin f[i,j]:=fmin(f[i,j],f1[i,j]+a[q[k],q[k+1]]); f[i,q[k]]:=fmin(f[i,q[k]],f1[i,j]+a[j,q[k+1]]); f[j,q[k]]:=fmin(f[j,q[k]],f1[i,j]+a[i,q[k+1]]); end; f1:=f; end; min:=maxlongint; for i:=1 to n do for j:=1 to n do if f[i,j]<min then min:=f[i,j]; writeln(min); end.

(4)例题:多米诺骨牌
【输入】 输入文件的第一行是一个正整数 n(1≤n≤1000),表示多米诺骨牌数。接下来的 n 行表示 n 个多米诺骨牌的 点数。每行有两个用空格隔开的正整数,表示多米诺骨牌上下方块中的点数 a 和 b,且 1≤a,b≤6。

25

【输出】 输出文件仅一行,包含一个整数。表示求得的最小旋转次数

var x,y,i,j,m,n,sj,xj,l1,l2:longint; f,g:array[-5001..5001] of longint; a:array[1..1000] of longint; function min(a,b:longint):longint; begin if a<=b then exit(a) else exit(b);end; begin readln(n); for i:=1 to n do begin read(x,y); a[i]:=x-y; end; for i:=-5001 to 5001 do f[i]:=10000000; if a[1]>0 then begin sj:=a[1];xj:=-a[1];end else begin sj:=-a[1];xj:=a[1] end; f[a[1]]:=0; f[-a[1]]:=1; for i:=2 to n do begin if a[i]>0 then begin sj:=a[i]+sj;xj:=xj-a[i];end else begin sj:=sj-a[i];xj:=xj+a[i] end; for j:=-5001 to 5001 do g[j]:=10000000; for j:=xj to sj do g[j]:=min(f[j+a[i]]+1,f[j-a[i]]); f:=g; end; if f[0]<10000000 then writeln(f[0]) else for i:=0 to 5000 do begin if (f[i]<10000000)or(f[-i]<10000000) then begin writeln(min(f[i],f[-i]));break;end; end; end.

(5)例题:万神牛的筷子
(chopsticks.pas/c/cpp) 【问题描述】 中国人吃饭喜欢用筷子。万神牛与常人不同,他的一双筷子有 3 只,一双短筷子加上一根比较长的(一 般用来穿香肠之类的食物) 。两只较短的筷子的长度应该尽可能的接近,但是最长的那根长度是无所谓 的。如果一双筷子的长度分别是 A,B,C(A<=B<=C) ,则用 sqr(A-B)的值表示这双筷子的质量,这个

26

值越小,这双筷子的质量越高。 万神牛请 MM 吃饭,并准备为每人准备一双这种特殊的筷子。万神牛有 N(N<=5000)只筷子, 他希望找到一种办法搭配好 M 双筷子,使得这些筷子的质量值和最小。 【输入格式】 第一行两个正整数 M,N,表示有 N 只筷子,需要搭配 M 双。第二行到第 N+1 行每行一个整数,表示 每只筷子的长度,按长度从小到大给出。 【输出格式】 一行,一个整数,表示最小的质量值和

var f:array[0..1000,0..200] of longint; w:array[1..1000] of longint; k,i,j,m,n:longint; function min(a,b:longint):longint; begin if a>=b then exit(b) else exit(a); end; begin readln(m,n); for i:=1 to n do read(w[n-i+1]); fillchar(f,sizeof(f),$3f); for i:=0 to k do f[0,k]:=0; for i:=0 to n do f[i,0]:=0; for i:=3 to n do for j:=1 to i div 3 do begin f[i,j]:=min(f[i,j],f[i-2,j-1]+sqr(w[i]-w[i-1])); f[i,j]:=min(f[i,j],f[i-1,j]); end; writeln(f[n,m]); end.

(6)最大子矩阵
for i:=1 to n do for j:=i to n do for k:=1 to n do begin if f[k-1]<0 then ji:=0 else ji:=f[k-1]; f[k]:=ji+a[k,j]-a[k,i-1]; if f[k]>max then max:=f[k]; end; if max<0 then max:=0; writeln(max);

(7)任务安排:把当前状态对以后的影响加入
read(n); read(s);

27

c[0]:=0;t[i]:=0; for i:=1 to n do begin read(tt,cc); t[i]:=t[i-1]+tt; c[i]:=c[i-1]+cc; end; fillchar(f,sizeof(f),$3f); f[0]:=0; for i:=1 to n do for j:=1 to i do f[i]:=min(f[i],f[j-1]+(t[i])*(c[i]-c[j-1])+(c[n]-c[j-1])*s);

5. 区间动态规划 (1)合并:意思就是将两个或多个部分进行整合,当然也可以反过来,也就是是将一个问
题进行分解成两个或多个部分。 特征:能将问题分解成为两两合并的形式 求解:对整个问题设最优值,枚举合并点,将问题分解成为左右两个部分,最后将左右两个 部分的最优值进行合并得到原问题的最优值。有点类似分治算法的解题思想。 典型试题:整数划分,凸多边形划分、石子合并、多边形合并、能量项链等、数字游戏。

(2) 例题:能量项链 //把环展开成 2*n 的链
var a,a1,b:array[0..200] of longint; f:array[0..200,0..200] of longint; maxt,i,j,k,k1,m,n,z:longint; function max(a,b:longint):longint; begin if a>=b then max:=a else max:=b; end; begin readln(n); for i:=1 to n do read(a[i]); for i:=1 to n do a[i+n]:=a[i]; fillchar(f,sizeof(f),0); for i:=1 to 2*n-2 do f[i,i+1]:=a[i]*a[i+1]*a[i+2]; for k:=3 to n do for i:=1 to 2*n-k do for j:=i+1 to i+k-1 do f[i,i+k-1]:=max(f[i,i+k-1],f[i,j-1]+f[j,i+k-1]+a[i]*a[j]*a[i+k]); maxt:=0; for i:=1 to n do if f[i,i+n-1]>maxt then maxt:=f[i,i+n-1]; writeln(maxt); end.

28

(3)例题:数字游戏:注意正负值时 fmin,fmax 的处理 5.坐标型动态规划(规则类 DP)
规则类动态规划有一个共性,那就是在一个矩阵中(一般是二维矩阵,当然可能有更加复杂 的图形)给出一些规则,然后按规则去做某些决策,我们思考这类问题的基本方法是:以坐 标为状态,坐标之间的转换关系,一般利用问题给出的规则进行决策转移。 状态转移方程一般可描述如下:

F(i,j)=Max{f(i-1,k)}+决策;这里 k 为规则数 (1) 传纸条
var i,j,m,n,k,h:longint; a:array[0..50,0..50] of byte; f:array[0..50,0..50,0..50,0..50] of longint; function max(a,b,c,d:longint):longint; var i:longint; begin i:=0; if a>i then i:=a; if b>i then i:=b; if c>i then i:=c; if d>i then i:=d; max:=i; end; begin readln(m,n); for i:=1 to m do for j:=1 to n do read(a[i,j]); fillchar(f,sizeof(f),0); for i:=1 to m do for j:=1 to n do for k:=1 to m do for h:=1 to n do if (i=k)and(j=h) then f[i,j,k,h]:=max(f[i-1,j,k-1,h],f[i-1,j,k,h-1],f[i,j-1,k,h-1],f[i,j-1,k-1,h])+a[i,j] else f[i,j,k,h]:=max(f[i-1,j,k-1,h],f[i-1,j,k,h-1],f[i,j-1,k,h-1],f[i,j-1,k-1,h])+a[i,j]+a[k,h]; writeln(f[m,n,m,n]); end. (2) 小胖办证(坐标双向动归) 小胖办证 问题描述 小胖要办个签证。办证处是一座 M 层的大楼,1<=M<=100。每层楼都有 N 个办公室, 编号为 1..N(1<=N<=500)。每个办公室有一个签证员。签证需要让第 M 层的某个签证 员盖章才有效。每个签证员都要满足下面三个条件之一才会给小胖盖章: 1. 这个签证员在 1 楼 2. 小胖的签证已经给这个签证员的正楼下(房间号相同)的签证员盖过章了。

29

3. 小胖的签证已经给这个签证员的相邻房间(房间号相差 1,楼层相同)的签证员盖 过章了。 每个签证员盖章都要收取一定费用,这个费用不超过 1000000000。找出费用最小的盖 章路线,使签证生效 输入格式 第 1 行两个整数 M 和 N。 接下来 M 行每行 N 个整数,第 i 行第 j 个数表示第 i 层的第 j 个签证员收取的费用。 输出格式 按顺序打出你经过的房间的编号,每行一个数。 如果有多条费用最小的路线,输出任意一条 var f,a:array[0..500,0..1000] of longint; pre:array[0..500,0..1000]of integer; oup:array[1..500000] of integer; i,j,j1,m,n,k,minf,mp:longint; function min(a,b,c:longint):longint; var t:longint; begin if a<=b then begin t:=a;mp:=j end else begin t:=b;mp:=j-1 end; if c<t then begin t:=c;mp:=j+1 end; min:=t; end; begin readln(n,m); for i:=1 to n do for j:=1 to m do read(a[i,j]); fillchar(f,sizeof(f),$7f); for i:=1 to m do begin pre[1,i]:=0; f[1,i]:=a[1,i];end; for i:=2 to n do for k:=1 to m do for j:=1 to m do begin minf:=min(f[i-1,j],f[i,j-1],f[i,j+1]); if minf<f[i,j] then begin f[i,j]:=minf+a[i,j]; pre[i,j]:=mp; end; end; minf:=maxlongint; for i:=1 to m do if f[n,i]<minf then begin minf:=f[n,i];mp:=i end; i:=1;oup[i]:=mp;j:=n; while pre[j,oup[i]]<>0 do

30

begin if oup[i]=pre[j,oup[i]] then j1:=j-1 else j1:=j; inc(i); oup[i]:=pre[j,oup[i-1]]; j:=j1; end; for j:=i downto 1 do writeln(oup[j]); end.

(3)免费馅饼 转化对象(相对移动) ,使其成为传统的移动问题 (4)瑰丽的华尔兹(NOI2005) 6. 资源分配型动态规划 资源分配模型的动态规划,也是在信息学竞赛中经常使用的。 这类型的题目一 般是:给定 m 个资源,分配给 n 个部门,第 i 个部门获得 j 个资源有个盈利值,问如何 分配这 m 个资源能使获得的盈利最大,求最大盈利。 这类型的题目一般用资源数做状态,数组 f[i,j]表示前个 i 个部门分配 j 个资源 的最大盈利,则状态转移方程为: f[i,j]:=max{f[i-1,k]+value[i,j-k]} (0≤k≤j) 程序框架:
Procedure dynamic; Var i,j,k:longint; Begin For i:=1 to n do For j:=0 to m do For k:=0 to j do If f[i-1l,k]+value[i,j-k]>f[i,j] then f [i,j]:=f[i-1,k]+value[I,j-k]; Wrneln(f[n,m]); End;

7. 树型动态规划 (1)概述:它的基本模型都是一棵树或者森林,为了考虑方便,一般情况下都将这 个树或森林转化为二叉树,如下图,然后整个问题的最优只会涉及到左右孩子的 最优,然后考虑根结点的情况,这样化简了问题,最终很容易写出状态转移方程, 从而问题得到解决。另外,并不是所有的问题一定要转化为二叉树来解决,要仔 细思考的就是每个结点有些什么状态,这些结点的状态与父、子结点的状态有什 么联系,也就是如何由子结点的最优值推出父节点的最优值(即状态转移方程) (2)例题:加分二叉树 设 f(i,j)中序遍历为 i,i+1,…,j 的二叉树的最大加分,则有: f(i,j)=max{f[i,k-1]*f[k+1,j] +d[k]} f(i,i)=d[i] 答案为 f(1,n) 1<=i<=k=<=j<=n 注意加入记忆化 if f[l,r]>0 then exit; 时间复杂度 O(n^3) (3)例题:观光旅游 {lxy 牛的程序}
31

【问题描述】在一棵树中找一个权值和最大的联通块(子树) 【参考程序】
// tree DP photo program lxy(input,output); type node=record s,t,next:longint; end; var st:array[0..400000] of node; f,w,next,fa:array[0..200000] of longint; visit:array[0..200000] of boolean; i,j,m,n,x,y,sum,ans:longint; s:string; procedure insert(s,t:longint); begin inc(sum); st[sum].s:=s; st[sum].t:=t; st[sum].next:=next[s]; next[s]:=sum; end; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; procedure tree_dp(x:longint); var i,j,k,he:longint; begin k:=next[x]; while k<>0 do begin if fa[st[k].t]=x then tree_dp(st[k].t); k:=st[k].next; end; k:=next[x]; he:=0; while k<>0 do begin if fa[st[k].t]=x then he:=he+f[st[k].t]; k:=st[k].next; end; k:=next[x]; f[x]:=he+w[x]; while k<>0 do begin if fa[st[k].t]=x then f[x]:=max(f[x],f[x]-f[st[k].t]); k:=st[k].next; end; f[x]:=max(f[x],w[x]);

//f[x]表示以 x 为根的最大子树

//有儿子,先对儿子 DP

//对所有的儿子求和

//枚举每个儿子取或者不取

32

ans:=max(ans,f[x]); end; procedure make_tree(x:longint); var k:longint; begin k:=next[x]; visit[x]:=true; while k<>0 do begin if not visit[st[k].t] then begin make_tree(st[k].t); fa[st[k].t]:=x; end; k:=st[k].next; end; end; begin readln(n); for i:=1 to n do begin read(w[i]); f[i]:=(-maxlongint) div 2; end; for i:=1 to n-1 do begin readln(x,y); insert(x,y); insert(y,x); end; ans:=-maxlongint; make_tree(1); tree_dp(1); writeln(ans); end.

// 每个点都可以为根节点

9.状态压缩的动态规划
(1) 青蛙过河 F[0]=0 f[i]=min{f[i-k]} //第 i 点没有石子 f[i]=min{f[i-k]+1} //第 i 点有石子 ans=min{f[L],f[L+1],...,f[L+T-1]} 状态转移方程的时间复杂度为 O(n),n 最大为 L*(S -T)。题目中给出的数据过于变态,L 达 到了 10^9,必然会出现超时的情况。 S=T 的情况直接 mod 就可以了。 S<>T 1 题目中给出的 L 巨大,但是最多存在 100 颗石子,这说明在这条路径上肯定有好多段距 离之间并不存在石子,但是我们的动归方程把大段不存在石子的距离也进行了计算,造成

33

了时间上不必要的浪费。现在我们想应该如何处理大段不存在石子的距离以减少不必要的 状态,减少时间开销。 2 我们是不是可以去掉中间大段不存在石子的距离进行空间压缩呢? 如果可以我们最小 能压缩到多少呢? 为什么不能继续压缩呢?假如 1 ~ 100 的距离之间只有 100 的位置上 存在一颗石子,S=4 T=5。此时青蛙所有可能到达的位置为 4 5 8 9 10 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 从 12 这个位置开始以后所有的位置都有可能到达形成连续区间, 表明 12 ~ 99 所有的位置 都有可能到达, 这些位置对于确定 100 这个点能否到达做出的贡献都是一样的。 所以 dp[13] ~ dp[99]计不计算都无所谓,可以用 dp[12]来代替,我们此时回答了第一个问题即可以去 掉中间大段不存在石子的距离。此时我们考虑 100 这个石子到不到的问题,就跟考虑能不 能到到达 12 这个问题一样了。 第二个问题我们最小可以压缩到连续空间开始时的数值 12。 第三个问题如果我们在 12 的基础上进行继续压缩,我们就不可能找出一个点完全代替后 面的点,因为后边出现了不可能到达的点了。三个问题完全解决。 此时还有个疑问我们该如何确定最小压缩距离呢,这个题目我们是笔算出来的如果 S T 换 做其他数值呢, 首先我们可以想一下 S ~ T 这个区间由 T 与 T-1 确定的压缩区间是最大的, 因为其他的不是数值较小就是区间太大。已知一结论 Px+(P+1)y=Q ,x y P Q 均为整数, 其中 P Q 为非负整数,当 Q>=P*(P-1)时,x y 必有非负解,即 P*(P-1)以后所有的数值都可 得到。 证明: x=x0+(p+1)t y=y0-pt; 取 适 当 的 t, 使 0=<x<= P, 则 当 Q>P*(P-1)-1 时 有 (P+1)y=Q-Px>=P*(P-1)-Px>=P*(P-1)-P*P>=-P >-(P+1);则 y>-1 也为非负数,证明成立。 应用到题目中 T 最大为 10, 则可以确定的最小压缩空间为 9*(9-1)=72,从 72 开始就会出现 区间完全连续 (2) 广场铺砖 显然,对于每一行,宽度为 w,每格可放 0 和 1,因此有 2w 种状态,如下图: 设 f(i,s)表示铺到第 i 行,状态为 s 的方案数,则 初始值 f(1,0)=1 Ans=f[h+1][0] 时间复杂度为 O(h*2W) 以每一行作为 1 种状态,研究上下两行之间的关系,利用上下两行之间的约束条件进行 决策转移。一般采用一个二进制数表示状态,有时也用三进制或四进制数等。用二进制数表 示状态最大的好处就是在决策转移时可以采用位运算,这样能极大提高算法效率。 状态压缩的动态规划实际上也是按常规处理的一种动态规划的做法, 只不过由于每一个阶段 状态数可能比较多,状态通常采用压缩存储方式,以利于运算和转移。试题的特点一般是数 据整体规模较小,或者某一维规模较小。

10.动态规划的一般优化方法
(1) 改进状态表示 理想收入问题

34

理想收入是指在股票交易中,以 1 元为本金可能获得的最高收入,并且在理想收入中 允许有非整数股票买卖。已知股票在第 i 天每股价格是 V[i]元,1≤i≤M,求 M 天后的理想收 入 法 1:设 F[i]表示在第 i 天收盘时能达到的最高收入,则有 F[i]的递推关系式: f[i]:=max{f[j]/v[k]*v[i]} f[0]=1 v[0]=1 0<=j<=k<I 第 j 天收盘后的收入,全部用于买入第 k 天的股票,再在第 i 天将所持的股票全部卖 出所得的收入。O(m^3) 法 2: 设 Q[i]表示前 i 天能达到的最大收入,则可列出状态转移方程: q[i]:=max{q[I-1],q[j]/v[j]*v[i]} 0<=j<I O(m^2) 对于 0<=j<i,要求 Q[i],实际上 Q[1]…Q[i-1]都已经求出,因此我们只要搞一个变量保存 Q[j]/V[j] 的最大值即可,记为 MaxQ. q[i]:=max{q[I-1],maxq*v[i]} O(m) (2)利用决策的单调性:二分优化最长上升序列问题 (3)利用贪心思想减少状态总数 :快餐问题 计算出每天生产套数的上限值 对每条流水线, 我们没有必要将对每个时刻都进行动态规划, 可以拿出大部分时间进行 成套生产,剩下一些时间进行动态规划 (4)利用恰当的数据结构存储状态,减少状态查找时间 (5)根据最优解的性质减少决策

(五)图论
1.Floyd-Warshall
for k:=1 to n do //注意中间点在最外层循环 for i:=1 to n do for j:=1 to n do if f[i,k]+f[k,j]>f[i,j] then f[i,j]:=f[i,k]+f[k,j];

例题:清理通道
清理通道(road.pas) 源程序名 可执行文件名 输入文件名 输出文件名 时限 road.??? (PAS,C,CPP) road.exe road.in road.out 1S

给出一个由各种障碍物组成的二维矩阵,各种障碍物由不同的大写字母表示。我们要从矩阵第一行到 最后一行打出一条通道,每次清除障碍只能清除一种障碍物,并且并且它们必须要彼此相连接,那么至少 需要几次可以打通一条通道?图样如下: AABBCCD AFFBGGD IIJBKKD MNNOOPD 35

QQRRSST 比如在这张地图中,可以先打掉最右边的 D 区域,然后再打通 T 区域,这样就只用两次就可以打通道路(道 路是可以拐弯的,不一定要是一条直线)。 【输入格式】 第一行有两个整数,m 和 n(0<m,n<21) ;下面 m 行,每行 n 个字母。 【输出格式】 一个整数,程文打通道路用功力的最少的次数。

const dx:array[1..4] of integer=(1,-1,0,0); dy:array[1..4] of integer=(0,0,1,-1); var a:array[0..22,0..22] of char; f:array[1..441,1..441] of longint; n,m,i,j,k,min,h,g,z,x,y:longint; begin readln(n,m); for i:=1 to m*n do for j:=1 to m*n do f[i,j]:=10000000; for i:=1 to m*n do f[i,i]:=0; for i:=1 to n do begin for j:=1 to m do read(a[i,j]); readln; end; for i:=1 to n do for j:=1 to m do begin for z:=1 to 4 do begin x:=i+dx[z];y:=j+dy[z]; if (x>0)and(x<n+1)and(y>0)and(y<m+1) then begin if a[i,j]=a[x,y] then begin h:=(x-1)*m+y; g:=(i-1)*m+j; for k:=1 to m*n do if f[g,k]>f[h,k] then f[g,k]:=f[h,k]; end else begin h:=(x-1)*m+y;

36

g:=(i-1)*m+j; for k:=1 to m*n do if f[g,k]>(f[h,k]+1) then f[g,k]:=f[h,k]+1; end; end; end; end; min:=1000000000; for k:=1 to n*m do for i:=1 to n*m do for j:=1 to n*m do if f[i,k]+f[k,j]<f[i,j] then f[i,j]:=f[i,k]+f[k,j]; for i:=1 to m do for j:=m*(n-1)+1 to n*m do if f[i,j]<min then min:=f[i,j]; writeln(min+1); end.

2.Bellman-ford

O(ne)

{无负权回路} procedure relax(u,v,w:integer); begin if dis[u]+w<dis[v] then begin flag:=false; dis[v]:=dis[u]+w; pre[v]:=u; end end; function bellman_ford:boolean; var i,j :integer; begin for i:=1 to n-1 do begin flag:=true; for j:=1 to e do //每条边松弛 with edges[j] do relax(a,b,w); if flag then break; end; end;

判断是否有负权回路:松弛 n-1 次后,如果依然能松弛说明有负权回路

37

例题: (实现方便)
2、通向聚会的道路(jhdl.pas/c/cpp) 【问题描述】 candy 住在一个被划分为 n 个区域的神奇小镇中, 其中 candy 的家在编号为 n 的区域, candy 生日这天,大家都急急忙忙赶去 candy 家庆祝 candy 的生日。 candy 共有 t 个朋友住在不同的区域。小镇有 m 条道路,小镇的神奇之处在于其中的 p1 条 道路只会在你走过区域的的个数为奇数时候开启,p2 道路只会在你走过区域的个数为偶数的时 候开启,剩下的道路一直都会开启。并且,所有的道路只能够单向通过。飘飘乎居士希望知道在 所有的好朋友中,谁离 candy 最近。 【输入格式】 第一行:两个正整数 n m,表示共 n 个区域,m 条道路 接下来 m 行,每行三个正整数 u v s 表示 u 到 v 的单向道路,路程为 s,其中第 i 条道路的编 号为 i。 接着一个整数 p1 以及 p1 个正整数 odd[i],表示编号为 odd[i]的道路只会在走过奇数个区域 时开启。 接着一个整数 p2 以及 p2 个正整数 even[i],表示编号为 even[i]的道路只会在走过偶数个区 域时开启。 接下来一个正整数 t(0<t<=n) 紧接着 t 行,每行一个正整数 h 以及一个不超过 10 个字符长度的字符串 na(且均有小写字 母组成) ,表示在 h 区域居住着名字为 na 的人。 【输出格式】 第一行,即距离 candy 家最近的人的名字,数据保证有且只有一个人为最后的答案。 第二行,该人到 candy 家的距离。 如果存在多解,则输入名字中字典序较小的一人。

{虚拟 0 点,0 点到有人点距离为 0,d0,d1 分别存奇状态和偶状态,互相松弛更 新}
const chu=10000000; var x,y,l:array[1..100000] of longint; n,m,god,gev,k,i,j,g,w,ll:longint; peo:array[1..10000] of boolean; stop:boolean; nam:array[1..10000] of string[10]; s,s1:string; od{ji},ev{ou}:array[1..100000] of boolean; d0,d1:array[0..10010] of longint; fa0,fa1:array[0..10010] of integer; begin assign(input,'jhdl.in');reset(input); readln(n,m); fillchar(od,sizeof(od),true); fillchar(ev,sizeof(ev),true); fillchar(peo,sizeof(peo),false);

38

for i:=1 to m do read(x[i],y[i],l[i]); read(g); for i:=1 to g do begin read(k); od[k]:=false; end; read(g); for i:=1 to g do begin read(k); ev[k]:=false; end; for i:=1 to m do if (not ev[i]) and (not od[i]) then begin ev[i]:=true;od[i]:=true; end; readln(g); for i:=1 to g do begin readln(s); w:=pos(' ',s); ll:=length(s); s1:=copy(s,w+1,ll-w); delete(s,w,ll-w+1); val(s,w); peo[w]:=true; nam[w]:=s1; end; for i:=1 to n do if peo[i] then begin d1[i]:=0;fa1[i]:=i;end else begin d1[i]:=chu;fa1[i]:=0;end; for i:=1 to n do d0[i]:=chu; for i:=1 to n-1 do begin stop:=true; for j:=1 to m do begin if (od[j]) then begin if d1[x[j]]+l[j]<d0[y[j]] then begin d0[y[j]]:=d1[x[j]]+l[j];fa0[y[j]]:=fa1[x[j]];stop:=false;end; if (d1[x[j]]+l[j]=d0[y[j]])and(fa1[x[j]]<fa0[y[j]]) then begin fa0[y[j]]:=fa1[x[j]];end; end; if (ev[j]) then

39

begin if d0[x[j]]+l[j]<d1[y[j]] then begin d1[y[j]]:=d0[x[j]]+l[j];fa1[y[j]]:=fa0[x[j]];stop:=false;end else if (d0[x[j]]+l[j]=d1[y[j]])and(fa0[x[j]]<fa1[y[j]]) then begin fa1[y[j]]:=fa0[x[j]];end; end; end; if stop then break; end; if d1[n]<d0[n] then begin writeln(nam[fa1[n]]);writeln(d1[n]);end else if d0[n]<d1[n] then begin writeln(nam[fa0[n]]);writeln(d0[n]);end; if d1[n]=d0[n] then begin if fa1[n]<fa0[n] then begin writeln(nam[fa1[n]]);writeln(d1[n]); end else begin writeln(nam[fa0[n]]);writeln(d0[n]); end;end; close(input); end.

3.SPFA
{邻接矩阵实现} procedure spfa(be:integer); var f:array[0..1000] of longint; q:array[1..1000] of boolean; min,i,j,t,h,x:longint; begin fillchar(q,sizeof(q),false); fillchar(f,sizeof(f),0); h:=0;t:=1;q[be]:=true;{初始化一定不能错,注意 d 数组初始值与 dijkstra 的区别} f[t]:=be; for i:=1 to n do d[i]:=maxlongint div 2; d[be]:=0; while not(h=t) do begin h:=(h+1) mod n; x:=f[h]; q[x]:=false; for i:=1 to n do if a[x,i]+d[x]<d[i] then begin d[i]:=d[x]+a[x,i]; if not(q[i]) then begin q[i]:=true; t:=(t+1)mod n;f[t]:=i;end;
40

end; end; end;

{模拟链表实现 SPFA+SLF}
背景:{分层图}
道路翻新(revamp.pas/c/cpp) 【问题描述】 陈实的父亲陈老实每天都要检查一下鸡窝里的鸡。他需要从编号为 1 鸡窝出发,通过最近的道路走到编号 为 N 的鸡窝。现假设农场上一共有 N 个鸡窝,为方便起见,用 1 到 N 的数字来编号, 它们由 M (1 ≤ M ≤ 50000)条双向道路连接,保证 1 号鸡窝一定会与 N 号鸡窝相连。每条道路 连接的鸡窝用 P1i 和 P2i (1 ≤ P1i, P2i≤ N)表示,通行消耗的时间用 Ti (1 ≤ Ti≤ 1000000)来表示。 现在陈老实想翻新一些道路来减少每天花在路上的时间。 但他最多只能翻新 (1 ≤ K ≤ 20)条道路, 翻新后的 道路的通行时间将变成 0。请帮助陈老实选择最优的翻新方案使得从 1 号鸡窝到 N 号鸡窝的时间最短。 【输入文件】 输入文件 revamp.in 共 M+1 行; 第一行:包括三个数:N,M 和 K,彼此用空格分开。 第二行到 M+1 行:在第 i+1 行将会告诉你第 i 条道路的信息:P1i,P2i 和 Ti,彼此用空格分开。 N<=10000 【输出文件】 输出文件 revamp.out 仅一行:

不超过 K 条道路被翻新后的最短路径长度
type node=record g,next:longint; end; node1=record di,next,l:longint; end; const chu=maxlongint div 2; var a:array[1..320000] of node; d:array[1..320000] of longint; f:array[1..320000] of longint; q:array[1..320000] of boolean; mo:array[1..3200000] of node1; i,j,m,n,x,y,w,h,t,k,now,top:longint; begin readln(n,m,k); top:=0; fillchar(a,sizeof(a),0);

41

for i:=1 to m do begin readln(x,y,w); inc(top); mo[top].di:=x; mo[top].l:=w; mo[top].next:=a[y].next; inc(a[y].g); a[y].next:=top; inc(top); mo[top].di:=y; mo[top].l:=w; mo[top].next:=a[x].next; inc(a[x].g); a[x].next:=top; for j:=1 to k do begin inc(top); mo[top].di:=x+j*n; mo[top].l:=w; mo[top].next:=a[y+j*n].next; inc(a[y+j*n].g); a[y+j*n].next:=top; inc(top); mo[top].di:=y+j*n; mo[top].l:=w; mo[top].next:=a[x+j*n].next; inc(a[x+j*n].g); a[x+j*n].next:=top; inc(top); mo[top].di:=n*j+y; mo[top].l:=0; mo[top].next:=a[x+j*n-n].next; inc(a[x+j*n-n].g); a[x+j*n-n].next:=top; end; end; fillchar(q,sizeof(q),false); n:=n*k+n; for i:=1 to n do d[i]:=chu;

42

h:=0;t:=1;q[1]:=true;d[1]:=0; f[1]:=1; while (h<>t) do begin h:=(h+1) mod n; x:=f[h]; q[x]:=false; now:=a[x].next; for i:=1 to a[x].g do begin if mo[now].l+d[x]<d[mo[now].di] then begin d[mo[now].di]:=mo[now].l+d[x]; if not q[mo[now].di] then begin q[mo[now].di]:=true; if d[mo[now].di]<d[f[(h+1)mod n]] then {优化关键} begin f[h]:=mo[now].di; h:=(h-1) mod n;{SLF 注意两句的顺序} end else begin t:=(t+1)mod n; f[t]:=mo[now].di;end; //t:=(t+1)mod n; f[t]:=mo[now].di;{朴素} end; end; now:=mo[now].next; end; end; writeln(d[n]); end.

SPFA 判断负权回路:某个点进队 N 次则存在负权回路

4.dijkstra
{邻接矩阵实现}
var a:array[1..100,1..100] of longint; d:array[1..100] of longint; f:array[1..100] of boolean; n,i,j,k,kj,min,x,ans:longint; begin readln(n); for i:=1 to n do for j:=1 to n do begin

43

read(x); a[i,j]:=x;a[j,i]:=x; end; for i:=1 to n do begin d[i]:=a[1,i];f[i]:=false; end; f[1]:=true; ans:=0; for i:=1 to n-1 do begin min:=maxlongint; for j:=1 to n do if not(f[j])and(d[j]<min) then begin k:=j;min:=d[j];end; inc(ans,d[k]); f[k]:=true; for j:=1 to n do if d[j]>a[k,j] then d[j]:=a[k,j]; end; writeln(ans); end.

{dijkstra+heap

模拟链表实现}

type node=record l,next,di:longint; end; var heap:array[1..200000] of longint; d:array[0..200000]of longint; q:array[0..200000]of boolean; ans:array[1..200000] of longint; a,g:array[1..200000] of longint; mo:array[1..400000] of node; n,m,w1,w2,w3,i,j,x,y,ll,ansd,ansb,len:longint; function get:longint; var son,fa,jh:longint;stop:boolean; begin get:=heap[1]; heap[1]:=heap[len]; dec(len); fa:=1;stop:=false; while (fa*2+1<=len)and(not stop) do begin

44

if (fa*2+1>len)or(d[heap[fa*2]]<d[heap[fa*2+1]]) then son:=fa*2 else son:=fa*2+1; if d[heap[son]]<d[heap[fa]] then begin jh:=heap[son];heap[son]:=heap[fa];heap[fa]:=jh; fa:=son; end else stop:=true; end; end; procedure insertheap(x:longint); var jh,son:longint; begin inc(len); heap[len]:=x; son:=len; while (son<>1)and(d[heap[son div 2]]<d[heap[son]]) do begin jh:=heap[son]; heap[son]:=heap[son div 2]; heap[son div 2]:=jh; son:=son div 2; end; end; procedure dijs(be:longint); var min,k,now:longint; begin fillchar(q,sizeof(q),false); for i:=1 to n do d[i]:=10000000; d[be]:=0; len:=1;heap[len]:=be; for i:=1 to n-1 do begin k:=0; k:=get; {min:=10000000; k:=0; for j:=1 to n do if (d[j]<min)and( not q[j]) then begin min:=d[j];k:=j;end;} if k=0 then break; q[k]:=true; now:=a[k]; for j:=1 to g[k] do begin if (mo[now].l+d[k]<d[mo[now].di]) then begin d[mo[now].di]:=mo[now].l+d[k];insertheap(mo[now].di); end; now:=mo[now].next; end;

45

end; end; begin readln(n,w1,w2,w3); fillchar(a,sizeof(a),0); fillchar(g,sizeof(g),0); for i:=1 to n-1 do begin read(x,y,ll); mo[i*2-1].l:=ll; mo[i*2-1].di:=y; inc(g[x]); mo[i*2-1].next:=a[x]; a[x]:=i*2-1; mo[i*2].l:=ll; mo[i*2].di:=x; inc(g[y]); mo[i*2].next:=a[y]; a[y]:=i*2; end; dijs(w1); for i:=1 to n do ans[i]:=d[i]; dijs(w2); for i:=1 to n do ans[i]:=d[i]+ans[i]; dijs(w3); ansd:=1000000000; for i:=1 to n do begin ans[i]:=d[i]+ans[i]; if ans[i]<ansd then begin ansd:=ans[i];ansb:=i;end; end; writeln(ansb); writeln(ansd); end.

5.Prim
{O(n^2)} {朴素邻接矩阵实现} fillchar(a,sizeof(a),$3f); fillchar(f,sizeof(f),false);

46

for i:=1 to m do begin read(x,y,l); if l<a[x,y] then a[x,y]:=l; if l<a[y,x] then a[y,x]:=l; end; for i:=1 to n do d[i]:=a[k,i]; d[k]:=0; f[k]:=true; t:=0; for i:=1 to n-1 do begin min:=chu; j1:=0; for j:=1 to n do if not f[j] and(d[j]<min) then begin min:=d[j];j1:=j;end; if j1=0 then break; f[j1]:=true; inc(t,d[j1]); for j:=1 to n do if not(f[j]) and(d[j]>a[j1,j]) then d[j]:=a[j1,j]; end;

可用 prim+heap 时间复杂度为 O(nlog(n))

6.Kruskal
{基于并查集}

{O(elog(e))}

qsort(1,m); for x:=1 to n do f[x]:=x; e1:=0; e2:=0; repeat; inc(e1); k1:=find(x[e1]); k2:=find(y[e1]); if k1<>k2 then begin; inc(e2); f[k1]:=k2; end;
47

until e2=n-1; 例题:冗余电网 【问题描述】 北冰洋有一座孤岛,多年来一直没电。近日,令岛民们振奋的消息传来:S 国的专家要 为他们修建电网! ! ! 孤岛上共有 N 个村庄,发电站要建在第 K 个村庄中。S 国的专家要在 N 个村庄间修建 M 条输电线路, 但由于地理原因, M 条线路无法保证每个村庄都与第 K 个村庄(建有发电站) 直接相连, 同样, 也不一定能保证每个村庄都与第 K 个村庄间接相连(假设 A 与 B 直接相连, B 与 C 直接相连,那么 A 与 C 间接相连)。 然而,由于 S 国的专家智商实在太“高”了,以至于设计出了许多冗余线路。现给出第 i 条线路两个端点 Ui,Vi(分别表示线路连接的两个村庄,Ui!=Vi)和长度 Li,请你帮岛民算一下: 如果电网可以覆盖全岛,最少需要多长的电线;若不能,有多少个村庄无电可用。 注意:0<=冗余线路数目<M;部分数据有重边。电网可双向导电。 【输入】 第一行:N M K 接下来 M 行:Ui Vi Li 具体含义见题目描述 【输出】 如果电网可以覆盖全岛,输出最少需要的电线长度; 若不能,输出无电可用的村庄的个数。 var x,y,l:array[1..200000] of longint; fa:array[1..200000] of longint; n,m,k,i,j,h,fk,tj:longint; t,t1:int64; procedure qs(s,t:longint); var i,j,mi:longint; begin i:=s; j:=t;mi:=l[(i+j) div 2]; repeat while l[i]<mi do inc(i); while l[j]>mi do dec(j); if i<=j then begin h:=l[i];l[i]:=l[j];l[j]:=h; h:=x[i];x[i]:=x[j];x[j]:=h; h:=y[i];y[i]:=y[j];y[j]:=h; inc(i);dec(j); end; until i>j; if i<t then qs(i,t); if s<j then qs(s,j); end;

48

function getfa(a:longint):longint; begin if fa[a]=a then exit(a) else begin fa[a]:=getfa(fa[a]);exit(fa[a]);end; end; function panduan(a,b:longint):boolean; var f1,f2:longint; begin f1:=getfa(a); f2:=getfa(b); if f1=f2 then exit(false); fa[f1]:=f2; exit(true); end; begin assign(input,'yydw.in'); assign(output,'yydw.out'); reset(input); rewrite(output); readln(n,m,k); for i:=1 to m do read(x[i],y[i],l[i]); qs(1,m); for i:=1 to m do fa[i]:=i; for i:=1 to m do begin if panduan(x[i],y[i]) then begin fa[x[i]]:=fa[y[i]];t1:=l[i];t:=t+t1;end; end; fk:=getfa(k); tj:=0; for i:=1 to n do if getfa(i)=fk then inc(tj); if tj=n then writeln(t) else writeln(n-tj); close(input); close(output); end.

7.欧拉回路
每条边都经过且只经过一次 定理一:存在欧拉路,条件为图是连通的且只有 2 个奇点(不需回到起点) 定理二:存在欧拉回路,条件为连通且无奇点(需回到起点) 找欧拉路:取一奇点开始遍历 找欧拉回路:从任意一点开始遍历

49

{dfs 实现欧拉回路} var f:array[0..200,0..200] of longint; l:array[0..40000] of longint; v,n,m,i,j,x,y,g,ans:longint; procedure find(x:longint); var i:integer; begin for i:=1 to n do if f[x,i]>0 then begin inc(ans); dec(f[x,i]); dec(f[i,x]); find(i); end; inc(g); l[g]:=x; end; begin readln(n,m); fillchar(f,sizeof(f),0); for i:=1 to m do begin read(x,y); inc(f[x,y]); inc(f[y,x]); end; g:=0; ans:=0; find(1); for i:=g downto 1 do write(l[i],' '); writeln; end.

8.哈密顿环
指不重复地走过所有点并最后还能回到起点的路径 思路:每个点作为起点尝试,如果不在之前访问过的图中,则作为起点 DFS 尝试 procedure dfs(x:integer); var I:integer; begin visit[x]:=true; {标记本图内已访问过} v[x]:=true; {标记 x 点在已访问过的图里} inc(len);path[len]:=x;

50

if (len>1)and(path[1]=path) then print; for i:=1 to num[x] do if not visit[map[x,i]] then dfs(map[I,i]); dec(len); visit[x]:=false {不需恢复 v[x]} end;

9. flood fill(求图的强连通分量)
var f:array[1..500,1..500] of char; i,j,m,n,t:longint; procedure dfs(x,y:longint); begin f[x,y]:='*'; dec(t); if (x-1>0)and(f[x-1,y]='0') then dfs(x-1,y); if (y-1>0)and(f[x,y-1]='0') then dfs(x,y-1); if (x+1<=n)and(f[x+1,y]='0') then dfs(x+1,y); if (y+1<=m)and(f[x,y+1]='0') then dfs(x,y+1); end; begin t:=0; readln(n,m); for i:=1 to n do begin for j:=1 to m do begin read(f[i,j]);if f[i,j]='0' then inc(t);end; readln; end; for i:=1 to n do if f[i,1]<>'*' then dfs(i,1); for i:=1 to n do if f[i,m]<>'*' then dfs(i,m); for i:=1 to m do if f[1,i]<>'*' then dfs(1,i); for i:=1 to m do if f[n,i]<>'*' then dfs(n,i); writeln(t); end.

10.最小环问题(floyd)
{无向图的最小环} fillchar(f,sizeof(f),$3f div 2); fillchar(a,sizeof(a),$3f div 2);

51

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; writeln(ans);

11.Topological sort
不断去除找入度为 0 的点 即将与之相连的点入度减 1 直至将整张图去除 begin fillchar(f,sizeof(f),false); fillchar(ind,sizeof(ind),0); readln(n,m); for i:=1 to m do begin readln(x,y); f[x,y]:=true; inc(ind(y)); end; for i:=1 to n do begin t:=0; for j:=1 to n do if ind[j]=0 then begin;t:=j;break;end; if t=0 then begin;writeln('No answer');exit;end; writeln(t); ind[t]:=-1; for j:=1 to n do if p[t,j]=true then begin;p[t,j]:=false;dec(ind[j]);end; end; end.

12.次短路
(1) 删边:每次删最短路上的一条边,用 Dijkstra+堆求单源最短路径,则每 次求最短路径时间复杂度为 O(N*log(N+M) + M),所以总的时间复杂度为 O(N*M*log(N+M) + M^2)。 (2) 2 遍 SPFA(尚有争议) (3)每次更新数组 d 时保存一个 d0 次小值
52

13.次小生成树
{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 就是次小生成树

(六)树
1. 堆 {插入} procedure ins(x:longint); var son,h:longint; begin inc(len); a[len]:=x; son:=len; while (son<>1)and(a[son]<a[son div 2]) do begin h:=a[son]; a[son]:=a[son div 2]; a[son div 2]:=h; son:=son div 2; end; end; {取出} function get:longint; var son,fa,h:longint; stop:boolean; begin get:=a[1]; a[1]:=a[len]; dec(len); fa:=1; stop:=false; while (not stop)and((fa*2<=len)or(fa*2+1<=len)) do
53

begin if (a[fa*2+1]>a[fa*2])or(fa*2+1>len) then son:=fa*2 else son:=fa*2+1; if a[fa]<=a[son] then stop:=true else begin h:=a[son]; a[son]:=a[fa]; a[fa]:=h; fa:=son; end; end; end; 2. 二叉排序树 type tnode=record l,r:longint; s:string; end; var tre:array[0..10000] of tnode; n,i,j,tret,k:longint; ss:string; function ins(ss:string):integer; var p,f:longint; begin p:=1;f:=0; while tre[p].s<>'' do begin f:=p; if tre[p].s=ss then exit(1); if tre[p].s>ss then p:=tre[p].l else p:=tre[p].r; end; inc(tret); tre[tret].s:=ss; if tre[f].s>ss then tre[f].l:=tret else tre[f].r:=tret; exit(0); end; begin readln(n); fillchar(tre,sizeof(tre),0); for i:=1 to n do begin readln(ss); k:=ins(ss); writeln(k); end;

54

end. 3. 最优二叉树(哈夫曼树) n 个带权叶子结点构成的二叉树中,带权路径长度 WPL 最小的二叉树。 (1) 性质:叶子上的权值均相同时,完全二叉树一定是最优二叉树;权越大的叶子 离根越近;形态不唯一。 (2) 构造:找两个根节点权值最小的树合并,新根的权等于两根之和,从原森林中 删除所操作的两棵树,并加入新树,直至只剩一棵树。 4. 求树的先序遍历 var s1,s2:string; n,m:longint; procedure change(l1,r1,l2,r2:longint); var ls,w:longint; begin write(s2[r2]); w:=pos(s2[r2],s1); ls:=w-l1; if w-1>=l1 then change(l1,w-1,l2,l2+ls-1); ls:=r1-w; if w+1<=r1 then change(w+1,r1,r2-ls,r2-1); end; begin readln(s1); readln(s2); change(1,length(s1),1,length(s2)); end. 5. 并查集及应用 function getfa(a:longint):longint; begin if fa[a]=a then exit(a) else begin fa[a]:=getfa(fa[a]);{路径压缩} exit(fa[a]);end; end; function panduan(a,b:longint):boolean; var f1,f2:longint; begin f1:=getfa(a); f2:=getfa(b); if f1=f2 then exit(false); fa[f1]:=f2; {合并集合} exit(true); end;

55

(七)分治
1. 二分查找 var a:array[1..10000]of longint; n,i,j,k,z:longint; procedure find(l,r:longint); var m:longint; begin m:=(l+r) div 2; if a[m]=k then begin writeln('YES ',m); exit;end; if a[m]<k then find(m+1,r); if a[m]>k then find(l,m-1); end; begin readln(n); for i:=1 to n do read(a[i]); qs(1,n); readln(z); for i:=1 to z do begin readln(k); find(1,n); end; end. 2.二分逼近(注意精度问题) {一元三次方程求解} var a,b,c,d:extended; x:array[1..3] of extended; i,j,k,l,g:integer; procedure findx(l,r:extended); var m,y1,y2,ym:extended; begin while r-l>0.001 do begin y1:=a*l*l*l+b*l*l+c*l+d; y2:=a*r*r*r+b*r*r+c*r+d; if y1*y2>0 then exit; m:=(l+r)/2; ym:=a*m*m*m+b*m*m+c*m+d; if y1*ym<0 then r:=m else l:=m; end;
56

inc(g); x[g]:=l; end; begin readln(a,b,c,d); g:=0; for i:=-100 to 99 do begin findx(i,i+1); end; for i:=1 to 2 do write(x[i]:0:2,' '); writeln(x[3]:0:2); end. 5.二分答案 {FISH} var d,a,a1:array[1..100000] of int64; n,m,k,l,r,sum,las:int64; i,j:longint; begin readln(n); sum:=0; for i:=1 to n do begin read(d[i],a1[i]); inc(sum,a1[i]); end; for i:=n downto 2 do d[i]:=d[i]-d[i-1]; l:=0;r:=sum div n +1; while r-l>1 do begin a:=a1; m:=(l+r)div 2; for i:=1 to n-1 do {类似均分纸牌的验证答案} begin if a[i]-m>d[i+1] then begin a[i+1]:=a[i+1]+a[i]-m-d[i+1];continue;end; if a[i]-m<0 then a[i+1]:=a[i+1]-(m-a[i])-d[i+1]; end; if a[n]=m then begin writeln(m);halt;end; if a[n]>m then l:=m else r:=m; end; writeln(l); end.

57

6.快速幂 快速求 a^b,采用递归或二进制实现 {二进制实现} var b,i,j,w,a:longint; ans:qword; er:array[1..100] of longint; begin readln(a,b); w:=0; while b>0 do begin inc(w); er[w]:=b mod 2; b:=b div 2; end; ans:=1; for i:=w downto 1 do begin ans:=ans*ans; if er[i]=1 then ans:=ans*a; end; writeln(ans); end. {位运算取位} readln(a,b); w:=0; while b>0 do begin inc(w); er[w]:=b and 1; b:=b shr 1; end;

(八)贪心
贪心法是从问题的某一个初始解出发, 采用逐步构造最优解的方法向给定的目标前进。 在每 个局部阶段, 都做出一个看上去最优的决策 (即某种意义下的、 或某个标准下的局部最优解) , 并期望通过每次所做的局部最优选择产生出一个全局最优解。 所以, 有些问题用贪心法求解 能得到最优解,并且能够证明,而有些却不能证明(只能说暂时找不出反例),甚至并不一 定能得到最优解。要注意的是贪心策略一旦做出,就不可再更改。贪心法的优势在于编程简 单、运行效率高、空间复杂度低。贪心法的应用非常广泛,比如在图论中,“Dijkstra 算法” 求解单源最短路径问题、“Prim 算法”和“Kruskla 算法”求最小生成树问题、哈夫曼树的构造 (哈夫曼算法)等都是基于贪心法。 例题(非常灵活,不少难题都可用贪心骗到不少分) 1.删数问题:每次删去上升序列的最后一个
58

2.智力冲浪:按权值由大到小排列,每个任务选择可行的最晚时间。 3.游戏通关(智力冲浪数据加强版) :按时间先后排序,按每次加入一个任务,若能加入则 时间加 1,把加入任务的权值加入维护的小根堆;时间不满足加入,则与根比较大小,如大 则替换,维护堆。堆中的权值和为最后结果 4.连接数:比较 s[i]+s[j]和 s[j]+s[i]

(九)搜索
1. 深搜框架 procedure dfs(x); Var Begin If 达到目标状态 then 输出结果并退出过程; If 满足剪枝条件 then exit; For i:=1 to 搜索宽度 do Begin 备份现场; (注意如果现场使用了全局变量,则需要使用局部变量备份) Dfs(参数+增量); 恢复现场; End; 2. 深搜优化 (1) 最优化剪枝 求最优值时,当前的状态无论如何不可能比最优值更优,则退出 可与展望结合剪枝 (2) 可行性剪枝 提前判断该状态是否能得到可行解,如不能则退出 (3) 记忆化搜索 对于已经搜索过的状态直接退出 (4) 改变搜索顺序 对于看起来希望更大的决策先进行搜索 (5)优化搜索策略 比如新篝火晚会,如果先产生全排再搜索中间的人,比两个两个搜剪枝要方便 的多。 改变搜索顺序+最优化剪枝+卡时洋洋洒洒 130+行的程序不敌先产生全排 的 60+行。 。 (6) DP 或贪心确定搜索的大致范围 P.S.实在不行了就卡时 3. 深搜应用举例 (1) 生日蛋糕(最优化,可行性剪枝)
[问题描述] 7 月 17 日是 Mr.W 的生日,ACM-THU 为此要制作一个体积为 Nπ 的 M 层生日蛋糕,每层都是一个圆 柱体。 59

设从下往上数第 i(1<=i<=M)层蛋糕是半径为 Ri, 高度为 Hi 的圆柱。 当 i<M 时, 要求 Ri>Ri+1 且 Hi>Hi+1。

由于要在蛋糕上抹奶油,为尽可能节约经费,我们希望蛋糕外表面(最下一层的下底面除外)的面积 Q 最小。 令 Q= S*π 请编程对给出的 N 和 M,找出蛋糕的制作方案(适当的 Ri 和 Hi 的值) ,使 S 最小。 (除 Q 外,以上所有数据皆为正整数) [输入] 有两行,第一行为 N(N<=10000) ,表示待制作的蛋糕的体积为 N*π;第二行为 M(M<=20),表示蛋 糕的层数为 M。 [输出] 仅一行,是一个正整数 S(若无解则 S=0) 。

var n,m,ans,i,j,min:longint; thr:array[1..20] of longint; er:array[1..20] of longint; a,b,ansa,ansb:array[1..20] of integer; procedure find(rest,x,lasr,lash,s:longint); var i,j,xi,xj:integer; begin if s>min then exit; {最优化剪枝} if x=m+1 then if rest<>0 then exit; if (rest=0)and(x=m+1) then begin if s<min then begin min:=s;ansa:=a;ansb:=b;end; exit;end; xi:=0; for i:=1 to m-x do xi:=xi+thr[i]; if rest-xi<0 then exit; {可行性剪枝} if x<>1 then begin xj:=0; for i:=1 to m-x+1 do xj:=xj+sqr(lasr-i)*(lash-i); if rest>xj then exit; {可行性剪枝} end; for i:=lasr-1 downto m-x+1 do for j:=lash-1 downto m-x+1 do if i*i*j+xi<=rest then begin a[x]:=i;

60

b[x]:=j; if x=1 then find(rest-i*i*j,x+1,i,j,s+2*i*j+i*i) else find(rest-i*i*j,x+1,i,j,s+2*i*j); end; end; begin read(n);read(m); min:=maxlongint; for i:=m downto 1 do thr[i]:=i*i*i; for i:=m downto 1 do er[i]:=i*i; find(n,1,trunc(sqrt(n div m)),n,0); writeln(min); end. (2)数的划分
将整数 n 分成 k 份,且每份不能为空,任意两份不能相同(不考虑顺序)。 例如:n=7,k=3,下面三种分法被认为是相同的。 1,1,5; 1,5,1; 5,1,1; 问有多少种不同的分法。 输入:n,k (6<n<=200,2<=k<=6) 输出:一个整数,即不同的分法。 样例 输入: 7 3 输出:4 {四种分法为:1,1,5;1,2,4;1,3,3;2,2,3;}

var n,k,i,j,t:longint; function min(a,b:integer):integer; begin if a<=b then min:=a else min:=b; end; procedure cut(k,res,las:integer); var i:integer; begin if k=0 then begin inc(t);exit end else for i:=(res div k) to min(las,res+1-k) do begin cut(k-1,res-i,i); end; end; begin readln(n,k); t:=0;

{可行性}

61

cut(k,n,n); writeln(t); end. 4. 基本广搜框架 初始化;把初始布局存入 设首指针 head=0; 尾指针 tail:=1; Repeat Inc(head),取出队列首记录为当前被扩展结点; For i:=1 to 规则数 do {r 是规则编号} Begin If 新空格位置合法 then Begin If 新布局与队列中原有记录不重复 tail 增 1,并把新布局存入队尾; if 达到目标 then 输出并退出; End; End; Until head>=tail; {队列空} 5. 广搜优化 判重的优化:hash,二叉排序树 双向广搜 6. 广搜举例:
已知有两个字串 A$, B$ 及一组字串变换的规则(至多 6 个规则): A1$ -> B1$ A2$ -> B2$ 规则的含义为:在 A$中的子串 A1$ 可以变换为 B1$、A2$ 可以变换为 B2$ …。 例如:A$='abcd' B$='xyz' 变换规则为: ‘abc’->‘xu’ ‘ud’->‘y’ ‘y’->‘yz’ 则此时,A$ 可以经过一系列的变换变为 B$,其变换的过程为: ‘abcd’->‘xud’->‘xy’->‘xyz’ 共进行了三次变换,使得 A$ 变换为 B$。 若在 10 步(包含 10 步)以内能将 A$ 变换为 B$ ,则输出最少的变换步数; 否则输出"NO ANSWER

type node=record s:string[20]; st:byte; end; node1=record s:string[20]; lc,lr:longint; end; var i,j,head,tail,cho,m,tret,tw:longint; w:array[0..20] of byte;
62

a:array[0..50000] of node; c,c1:array[1..6] of string[20]; s1,s2,ls1:string[20]; ls:string[41]; tre:array[0..50000] of node1; function ins(ss:string[20]):integer; var p,f:longint; begin if ss=s1 then begin fillchar(tre,sizeof(tre),0);tre[1].s:=ss;tret:=1;end else begin p:=1; while tre[p].s<>'' do begin f:=p; if tre[p].s=ss then exit(1); if tre[p].s>ss then p:=tre[p].lc else p:=tre[p].lr; end; inc(tret); tre[tret].s:=ss; if tre[f].s>ss then tre[f].lc:=tret else tre[f].lr:=tret; end; exit(0); end; begin readln(ls); w[0]:=pos(' ',ls); s1:=copy(ls,1,w[0]-1);s2:=copy(ls,w[0]+1,length(ls)-w[0]); m:=0; while not(eof) do begin inc(m); readln(ls); w[0]:=pos(' ',ls); c[m]:=copy(ls,1,w[0]-1);c1[m]:=copy(ls,w[0]+1,length(ls)-w[0]); end; head:=0; tail:=1; a[1].s:=s1;a[1].st:=0; cho:=ins(a[1].s); repeat inc(head); for i:=1 to m do begin ls:=a[head].s; tw:=0;

63

w[1]:=0; w[1]:=pos(c[i],ls); while w[tw+1]<>0 do begin inc(tw); delete(ls,w[tw],length(c[i])); insert(' ',ls,w[tw]); w[tw+1]:=0; w[tw+1]:=pos(c[i],ls); end; for j:=1 to tw do begin ls1:=a[head].s; delete(ls1,w[j],length(c[i])); insert(c1[i],ls1,w[j]); if ins(ls1)<>1 then begin inc(tail);a[tail].s:=ls1;a[tail].st:=a[head].st+1; if ls1=s2 then begin writeln(a[tail].st); halt; end; end; end; end; until (head>=tail)or(tail>=49994)or(a[tail].st=10); writeln('NO ANSWER!'); end.

(十)其他
1.离散化 特点: 能用离散化处理的题目非常大的特点就是数据的重叠性, 一般用排序等方法使其 有条理。数据被映射后相邻数据之间有联系的题目可以用离散化处理求解。 一般方法: (1)对于一维上的点,映射到数轴上,然后找出有序且仅处理这些点的方法,一般为 贪心或者动态规划,个别也可以二分查找。如登山机器人,noip2005 river (2)对于一维的线段,对线段的位置进行字典序,处理的时候仅考虑线段的端点。 (3)空间中,利用其中的关键字大小进行排序,映射到一个有序的集合当中,再采用 与一维类似的方法。如完美的对称,飞翔,矩形覆盖,矩形染色 2.KMP var p,f:array[0..100000] of longint; s1,s2:ansistring; i,j,l,n,m,tim:longint;
64

begin readln(s1); readln(s2); m:=length(s1); p[1]:=0; j:=0; for i:=2 to m do begin while (j>0)and(s1[j+1]<>s1[i]) do j:=p[j]; if s1[j+1]=s1[i] then inc(j); p[i]:=j; end; n:=length(s2); j:=0; tim:=0; for i:=1 to n do begin while (s1[j+1]<>s2[i])and(j>0) do j:=p[j]; if s1[j+1]=s2[i] then inc(j); if j=m then begin inc(tim); f[tim]:=i-m+1; j:=p[j]; end; end; if tim=0 then writeln('There must be something wrong.') else begin writeln(tim); for i:=1 to tim do writeln(f[i]); end; end. 3.hash 给出几种字符串映射到整数序列的哈希函数(hash 很灵活) : {1} Function hash(s:String): integer; Var i,j: integer; Begin j := 1; For i:=1 To length(s) Do j := (j+ord(s[i])*cct) Mod t;{const cct=47 t=3353} While (a[j]<>'') And (a[j]<>s) Do j := j+1;

65

hash := j; End; {2} Function DJBHash(s1:String): int64; Var i: integer; hash: int64; Begin hash := 5381; For i:=1 To length(s1) Do hash := (hash+(hash shl 5)+ord(s1[i])) And $FFFFFFFF; DJBHash := hash And $7FFFFFFF; End; {3} Function ElfHash(s : string) : longint; Var i, num, g : longint; Begin num := 0; For i := 1 to length(s) do Begin num := (num shl 4) + ord(s[i]); g := num and $f0000000; num := (num xor (g shr 24))and (not g); End; ElfHash := num; End; 4.常用字符串函数过程 copy(s,a,b); pos(ss,s); insert(ss,s,m); delete(s,a,b); val(s,x); str(x,s); str(x:w1:w2,s); home 参考资料:各种百度各种 blog(衷心感谢加 ORZ 郭家宝大牛的 blog) 雅礼中学朱全民动归讲稿 安阳一中各种算法讲稿 基础算法总结(杨帅) matrix67 的各种题解 单调队列

66

线段树 Tarjan 树状数组

67



推荐相关:

Noip常用算法大全

Noip 常用算法大全一、数论算法 1.求两数的最大公约数 function gcd(a,b:integer):integer; begin if b=0 then gcd:=a else gcd:=gcd (b.a mod b);...


NOIP复赛必记常用算法

NOIP实用算法 33页 1财富值 NOIP复赛复习资料汇总 20页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...


信息学奥赛(NOIP)必看经典书目汇总

信息学奥赛(NOIP)必看经典书目汇总_学科竞赛_高中教育_教育专区。信息学奥赛(...7、 《算法竞赛入门经典:训练指南》 (推荐指数:5 颗星) 刘汝佳著, 《算法...


信息学奥赛(NOIP)必看经典书目汇总

信息学奥赛(NOIP)必看经典书目汇总_学科竞赛_高中教育_教育专区。NOIP经典数目 ...6、《算法竞赛入门经典》(推荐指数:5 颗星) 刘汝佳著,算法必看经典。 7、《...


信息学奥赛(NOIP)必看经典书目汇总

信息学奥赛(NOIP)必看经典书目汇总_学科竞赛_高中教育_教育专区。信息学奥赛(...6、 《算法竞赛入门经典》 (推荐指数:5 颗星) 刘汝佳著,算法必看经典。 7、...


NOIP初赛复习——算法1

NOIP初赛复习——算法1_理学_高等教育_教育专区。OK 备战 NOIP2010 提高组初赛...从本质上讲, 归纳就是通过观察一些简单而特殊的情况,最后总结出有用的结论或...


NOIP算法:约瑟夫问题(C++)

NOIP算法:约瑟夫问题(C++) - 约瑟夫问题 也称为约瑟夫斯置换,在计算机编程的算法中,类似问题又称为约瑟夫环,又称“丢手绢问题”。一、一般形式 1.N 个人围成一...


备战今年NOIP的基本算法

NOIP基础算法综合---分治与... 82页 免费 NOIP2010集训小资料 13页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈...


NOIP复习资料(算法部分)

NOIP复习资料(算法部分)_计算机软件及应用_IT/计算机_专业资料。noip用到的一些...NOIP算法总结 by Nap 69页 免费 NOIP初赛知识点 110页 免费 NOIP复习资料 173...


NOIP算法入门——递归免费学习_高中其他_教学视频大全

理解递推与递归的区别,学会递归的基本思想,能够使用递归思想解决简单的编程问题。视频教程,NOIer全套教学,在线学习高中其他课程,NOIP算法入门——递归视频下载

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