rmq:
var a,p,q:array [0..300000] of longint; { p 递增队列， q 递减队列 }
n,m,x,i,j,k,h,t,max,min:longint;
begin
assign(input,'Rmq.in'); reset(input); assign(output,'Rmq.out'); rewrite(output);
readln(n,m);
for k:=1 to n do read(a[k]);
fillchar(p,sizeof(p),0); p[1]:=1; h:=1; t:=1; max:=0; { 初始化递减队列与指针，h 队首，t 队尾 }
fillchar(q,sizeof(q),0); q[1]:=1; i:=1; j:=1; min:=0; { 初始化递增队列与指针，i 队首，t 队尾 }
for k:=2 to m do
begin
while (h<=t) and (a[k]>a[p[t]]) do dec(t);
inc(t);
p[t]:=k;
while (i<=j) and (a[k]<a[q[j]]) do dec(j);
inc(j);
q[j]:=k;
end;
for k:=1 to n-m do
begin
inc(max,a[p[h]]);
x:=a[k+m];
while (h<=t) and (x>a[p[t]]) do dec(t);
inc(t);
p[t]:=k+m;
if k=p[h] then inc(h);
inc(min,a[q[i]]);
x:=a[k+m];
while (i<=j) and (x<a[q[j]]) do dec(j);
inc(j);
q[j]:=k+m;
if k=q[i] then inc(i);
end;
for k:=n-m+1 to n do
begin
inc(max,a[p[h]]);
if k=p[h] then inc(h);
inc(min,a[q[i]]);
if k=q[i] then inc(i);
end;
writeln(max);
writeln(min);
close(input); close(output);
end.

kmp:
var
t,s:ansistring;
l,i,j,k:longint;
index:longint;
next:array[1..10000] of longint;
begin
assign(input,'kmp.in');
assign(output,'kmp.out');
reset(input);rewrite(output);
readln(t);
readln(s);
fillchar(next,sizeof(next),0);
k:=0;
j:=1;
while j<length(s)do
if (k=0) or (s[j]=s[k]) then
begin
inc(j);inc(k);next[j]:=k;
end
else k:=next[k];
for i:=1 to length(s) do write(i:3);writeln;
for i:=1 to length(s) do write(s[i]:3);writeln;
for i:=1 to length(s) do write(next[i]:3);writeln;
index:=0;i:=1;j:=1;
while (i<=length(t)) and (j<=length(s)) do
begin
if (j=0) or (t[i]=s[j]) then
begin inc(i);inc(j) end
else
j:=next[j];
if j>length(s) then index:=i-length(s);
end;
writeln(index);
//readln;
close(input);close(output);
end.

表达式express
var s:string;
c:array [' '..'~'] of longint; { 存储各符号的优先级，数组定义的较大，实际用到其中的 7 个 }
i,n,fp,dp:longint; { 即：+ - * / ^ ( ) 七个符号，它们的 ASCII 码不连续 }
f:array [0..100] of char; { 符号栈，栈顶指针 fp }
d:array [0..100] of longint; { 数据栈，栈顶指针 dp }
function cal(a,b:longint; c:char):longint; { 返回 a b 按运算符 c 进行运算的结果 }
begin
case c of
'+':cal:=a+b;
'-':cal:=a-b;
'*':cal:=a*b;
'/':cal:=a div b;
'^':cal:=a**b;
end
end;
begin
assign(input,'Express.in'); reset(input); assign(output,'Express.out'); rewrite(output);
c['(']:=1; c[')']:=2; c['+']:=3; c['-']:=3; c['*']:=4; c['/']:=4; c['^']:=5; { 定义运算符的优先级 }
readln(s); { 读取表达式 }
n:=length(s); i:=1; fp:=0; dp:=0; { i 指示扫描表达式位置；fp 符号栈指针；dp 数据栈指针 }
while i<=n do { 扫描表达 }
if s[i] in ['0'..'9'] then { 遇到数字，则从表达式在提取一个数，存入数据栈中 }
begin
inc(dp); d[dp]:=0; { 数据进栈，存入栈顶单元 d[dp] 中 }
while (i<=n) and (s[i] in ['0'..'9']) do
begin d[dp]:=d[dp]*10+ord(s[i])-48; inc(i); end;
end
else
if (s[i]='(') or (fp=0) then { 如果遇到左括号，或是当前符号栈为空 }
begin inc(fp); f[fp]:=s[i]; inc(i); end { 则符号进栈，并移动表达式指针 }
else
if s[i]=')' then { 如果是右括号 }
begin
while f[fp]<>'(' do { 先将 ( ) 内的运算做完 }
begin dec(dp); d[dp]:=cal(d[dp],d[dp+1],f[fp]); dec(fp); end;
{ 从数据栈中取出前后二个数，根据符号栈内的符号进行运算，结果存回数据栈 }
dec(fp); inc(i); { 去掉一对括号 ( ) }
end
else
if c[s[i]]>c[f[fp]] then { 如果当前符号优先级高于栈顶符号优先级，则符号进符号栈 }
begin inc(fp); f[fp]:=s[i]; inc(i); end
else
begin { 当符号栈项的符号优先级大于或等于当前扫描到的符号时 }
while (fp>0) and (c[s[i]]<=c[f[fp]]) do
begin dec(dp); d[dp]:=cal(d[dp],d[dp+1],f[fp]); dec(fp); end;
inc(fp); f[fp]:=s[i]; inc(i); { 优先级高的运算完成后，该符号进栈 }
end;
while fp>0 do { 表达式已扫描完，但符号栈不为空，让所有的符号全部参与运算 }
begin dec(dp); d[dp]:=cal(d[dp],d[dp+1],f[fp]); dec(fp); end;
writeln(d[1]); { 数据栈栈底数据即为最终结果 }
close(input); close(output);
end.


二分图
var
link:array[1..3000] of longint;
visited:array[1..3000] of boolean;
g:array [1..3000,1..3000] of boolean;
n,m,k,i,a,b,ans:longint;
function find(x:longint):boolean;
var j:longint;
begin
for j:=1 to k do
if not(visited[j]) and g[x,j] then
begin
visited[j]:=true;
if (link[j]=0) or find(link[j]) then
begin
link[j]:=x;
exit(true);
end;
end;
exit(false);
end;
begin
fillchar(g,sizeof(g),false);
fillchar(link,sizeof(link),0);
readln(n,m,k);
for i:=1 to k do
begin
readln(a,b);
g[a,b]:=true;
end;
ans:=0;
for i:=1 to m do
begin
fillchar(visited,sizeof(visited),0);
if find(i) then inc(ans);
end;
writeln(ans);
readln;
end.

ZMS 子母树
var
a:array[1..100] of longint;
f,sum:array[1..100,1..100] of longint;
n,i,j,k:integer;
begin
assign(input,'zms.in'); reset(input); assign(output,'zms.out'); rewrite(output);
fillchar(sum,sizeof(sum),0);
readln(n);
for i:=1 to n do read(a[i]); { 每堆沙的数量 }
readln;
for i:=1 to n do
for j:=i to n do
if j=i then sum[i,j]:=a[j]
else sum[i,j]:=sum[i,j-1]+a[j]; { 第 i 至第 j 堆沙的数量和 }
fillchar(f,sizeof(f),0); { 包含了 f[i,1]=0 ，一个数不需合并，故其合并代价为 0 }
for j:=2 to n do
for i:=1 to n-j+1 do { 计算 f[i,j] ，即从 i 起的连续 j 个数合并 }
begin
f[i,j]:=maxlongint;
for k:=1 to j-1 do
if f[i,k]+f[i+k,j-k]+sum[i,i+j-1]<f[i,j] then
f[i,j]:=f[i,k]+f[i+k,j-k]+sum[i,i+j-1];
end;
writeln(f[1,n]);
close(input); close(output);
end.


MAXSUBTREE
type
link=^tr;
tr=record
v:longint;
next:link;
end;
var
p:link;
ans,i,x,y,n:longint;
w,f:array[1..20000] of longint;
son:array [1..20000] of link;
visited:array [1..20000] of boolean;
procedure search(i:longint);
var t:link;
tmp:longint;
begin
visited[i]:=false;
t:=son[i];
tmp:=0;
while t<>nil do
begin
if visited[t^.v] then begin search(t^.v);
if f[t^.v]>0 then tmp:=tmp+f[t^.v];end;
t:=t^.next;
end;
f[i]:=w[i]+tmp;
if f[i]>ans then ans:=f[i];
end;
begin
assign(input,'maxsubtree.in');
assign(output,'maxsubtree.out');
reset(input);
rewrite(output);
readln(n);
for i:=1 to n do
read(w[i]);
for i:=1 to n-1 do
begin
readln(x,y);
new(p); p^.v:=x; p^.next:=son[y]; son[y]:=p;
new(p); p^.v:=y; p^.next:=son[x]; son[x]:=p;
end;
fillchar(visited,sizeof(visited),true);
ans:=0;
search(1);
writeln(ans);
close(input);
close(output);
end.

spfa
type
link=^node;
node=record
next:link;
v,w:longint;
end;
var
f:array[1..1000] of boolean;
q:array[1..1000] of integer;
d:array[1..1000] of longint;
son:array[1..1000] of link;
a,b,w,n,v0,vt,v,t,h:integer;
p:link;
begin
assign(input,'spfa.in');
assign(output,'spfa.out');
reset(input);rewrite(output);
readln(n,v0,vt);
while not eof do
begin
readln(a,b,w);
new(p);
p^.v:=b;
p^.w:=w;
p^.next:=son[a];
son[a]:=p;
end;
fillchar(f,sizeof(f),0);
fillchar(q,sizeof(q),0);
fillchar(d,sizeof(d),$7f);
d[v0]:=0;
h:=0;t:=1;
f[v0]:=true;
q[h]:=v0;
while h<>t do
begin
v:=q[h];
p:=son[v];
while p<>nil do
begin
if p^.w+d[v]<d[p^.v] then
begin
d[p^.v]:=p^.w+d[v];
if not f[p^.v] then
begin
q[t]:=p^.v;
f[p^.v]:=true;
t:=(t+1) mod n;
end;
end;
p:=p^.next;
end;
f[v]:=false;
h:=(h+1) mod n;
end;
writeln(d[vt]);
close(input);close(output);
end.


并查集。。。注意初值＝ ＝
function find(x:longint):longint;
begin
if x=f[x] then exit(x) else f[x]:=find(f[x]);
exit(f[x]);
end;

书籍维护。。。二分的应用。。
var
sum,aver,i,m,n,l,r,tmp,mid:longint;
p:array[1..10000] of longint;
procedure init;
begin
assign(input,'maintain.in');
assign(output,'maintain.out');
reset(input);
rewrite(output);
end;
procedure endl;
begin
close(input);
close(output);
end;
begin
init;
readln(n,m);
for i:=1 to n do
begin
readln(p[i]);
inc(sum,p[i]);
end;
aver:=trunc(sum/m+0.5);
l:=aver;r:=sum;
while l<r do
begin
mid:=(l+r) div 2;
sum:=0;
tmp:=0;
for i:=1 to n do
if (tmp+p[i]<=mid) then inc(tmp,p[i])
else
begin
inc(sum);
tmp:=0;
end;
if tmp<>0 then inc(sum);
if sum<=m then r:=mid else l:=mid;
end;
writeln(mid);
endl;
end.

最大子序列和 Sub3 有 n 个数排成一排，求一个和最大的连续子序列，而且子序列的长度在 L1 和 L2 之间。
输入文件：第一行三个数 n L1 L2 （ n ≤ 200000 ，1 ≤ L1 ≤ L2 ≤ n ）
　　　　　第二行有 n 个数
输出文件：一个数，表示长度在 L1 到 L2 间的连续子序列的最大和
输入样例：10 3 6
　　　　　-5 4 3 -6 -8 5 -4 2 -5 6
输出样例：4
样例说明：因为规定长度为 3 到 6 ，所以最大和“ 3 4 ”不能取，可取长度为 5 的“ 5 -4 2 -5 6 ”连续子序列之和
{ 单调队列实现 }
var sum,q:array [0..300000] of longint;
n,L1,L2,h,t,i,ans,x:longint;
begin
assign(input,'Sub3.in'); reset(input); assign(output,'Sub3.out'); rewrite(output);
readln(n,L1,L2);
fillchar(sum,sizeof(sum),0);
for i:=1 to n do begin read(x); sum[i]:=sum[i-1]+x; end;
fillchar(q,sizeof(q),0);
q[1]:=L1; h:=1; t:=1;
for i:=L1+1 to L2 do
begin
while (h<=t) and (sum[i]>=sum[q[t]]) do dec(t);
inc(t);
q[t]:=i;
end;
ans:=-maxlongint;
for i:=1 to n-L2 do
begin
if sum[q[h]]-sum[i-1]>ans then ans:=sum[q[h]]-sum[i-1];
while (h<=t) and (sum[i+L2]>=sum[q[t]]) do dec(t);
inc(t);
q[t]:=i+L2;
if q[h]-i<L1 then inc(h);
end;
for i:=n-L2+1 to n-L1+1 do
begin
if sum[q[h]]-sum[i-1]>ans then ans:=sum[q[h]]-sum[i-1];
if q[h]-i<L1 then inc(h);
end;
writeln(ans);
close(input); close(output);
end.
{ 堆维护实现，有部分错误 ======================================================= }
type rec=record sum,w:longint; end;
var f:array [1..200000] of rec;
sum,where:array [1..200000] of longint;
n,l1,l2,len,i,x,base,max,now:longint;
procedure add(sum,w:longint); { 向堆中添加一个元素，sum 表示从第 1 个数累加到第 w 个数时的总和 }
var i,j:longint; t:rec; { 堆为大根堆 }
begin
inc(len); f[len].sum:=sum; f[len].w:=w; { len 为堆的总元素个数，总是添加在最后位置上 }
j:=len; i:=j div 2;
while (i>0) and (f[i].sum<f[j].sum) do begin { 然后从最后位置向上上升 }
where[f[i].w]:=j; where[f[j].w]:=i;
t:=f[i]; f[i]:=f[j]; f[j]:=t; j:=i; i:=j div 2;
end;
end;
procedure del(k:longint); { 将堆的第 k 个元素删除 }
var i,j:longint; t:rec;
begin { 将尾部元素置于 k 位置，堆元素数减 1 }
f[k]:=f[len]; where[f[k].w]:=k; dec(len); i:=k; j:=i*2;
while j<=len do begin { 沿 k 位置线路向下调整 }
if (j<len) and (f[j].sum<f[j+1].sum) then inc(j);
if f[i].sum<f[j].sum then begin
t:=f[i]; f[i]:=f[j]; f[j]:=t;
where[f[i].w]:=j; where[f[j].w]:=i; i:=j; j:=i*2;
end else break;
end;
end;
begin
assign(input,'Sub3.in'); reset(input); assign(output,'Sub3.out'); rewrite(output);
readln(n,l1,l2); now:=0; len:=0;
for i:=1 to l2 do begin
read(x); inc(now,x); sum[i]:=now; { now 为第 1 个数开始至第 i 个数的累加值，并存入 sum[i] }
if i>=l1 then add(sum[i],i); { 长度在 l1 --- l2 间的和构成一个堆 }
end;
max:=f[1].sum; { max 存储最大值 }
for i:=l2+1 to n do begin
read(x); inc(now,x); sum[i]:=now; base:=sum[i-l2];
del(where[i-l2+l1-1]); { 先从堆中删除最前的元素 }
add(sum[i],i); { 再在堆中加入刚生成的元素 }
if f[1].sum-base>max then max:=f[1].sum-base; { 完成之后是否有最大值 }
end;
for i:=n-l2+l1 to n-1 do begin { 尾部的若干元素处理 }
base:=sum[i-l1+1];
del(where[i]);
if f[1].sum-base>max then max:=f[1].sum-base;
end;
writeln(max);
close(input); close(output);
end.


组合数。。O（N）算法
var
t:longint;
n,k:longint;
i:longint;
boo:boolean;
procedure init;
begin
assign(input,'parity.in');
assign(output,'parity.out');
reset(input);
rewrite(output);
end;
procedure terminate;
begin
close(input);
close(output);
halt;
end;
function work(n,k:longint):boolean;
begin
while k<>0 do
begin
if n mod 2<k mod 2 then exit(false);
n:=n div 2;
k:=k div 2;
end;
exit(true);
end;
begin
init;
readln(t);
for i:=1 to t do
begin
readln(n,k);
if k>n-k then k:=n-k;
boo:=work(n,k);
if boo then writeln(1) else writeln(0);
end;
terminate;
end.

type link=^rec; rec=record v:longint; next:link; end;
var n,m,i,v,h,t,ans,x,y,z:longint;
c,d:array [1..100000] of longint;
head,head2:array [1..100000] of link;
f:array [1..100000] of boolean;
a,q:array [0..100000] of longint;
p:link;
function max(a,b:longint):longint;
begin if a>b then exit(a) else exit(b); end;
function min(a,b:longint):longint;
begin if a<b then exit(a) else exit(b); end;
begin
assign(input,'trade.in'); reset(input); assign(output,'trade.out'); rewrite(output);
readln(n,m);
fillchar(head,sizeof(head),0); fillchar(head2,sizeof(head2),0);
for i:=1 to n do read(a[i]); readln;
for i:=1 to m do
begin
readln(x,y,z);
new(p); p^.v:=y; p^.next:=head[x]; head[x]:=p; { head[x] 链表记录 x 的邻点 }
new(p); p^.v:=x; p^.next:=head2[y]; head2[y]:=p; { head2[y] 链表记录汇至 y 的邻点 }
if z=2 then
begin { 如果是一条双向路 }
new(p); p^.v:=x; p^.next:=head[y]; head[y]:=p;
new(p); p^.v:=y; p^.next:=head2[x]; head2[x]:=p;
end;
end;
for i:=1 to n do d[i]:=maxlongint; d[1]:=a[1];
fillchar(f,sizeof(f),0);
q[0]:=1; h:=0; t:=1; f[1]:=true; { SPFA 算法，从源点 1 出发，可达点所能获得的最小价格 }
while h<>t do
begin
v:=q[h];
p:=head[v];
while p<>nil do
begin
if min(d[v],a[p^.v])<d[p^.v] then
begin
d[p^.v]:=min(d[v],a[p^.v]);
if not f[p^.v] then
begin
f[p^.v]:=true;
q[t]:=p^.v;
t:=(t+1) mod n;
end;
end;
p:=p^.next;
end;
f[v]:=false;
h:=(h+1) mod n;
end;
for i:=1 to n do c[i]:=0; c[n]:=a[n];
fillchar(f,sizeof(f),0);
q[0]:=n; h:=0; t:=1; f[n]:=true; { SPFA 算法，能汇至 n 点时可获最高价格 }
while h<>t do
begin
v:=q[h];
p:=head2[v];
while p<>nil do
begin
if max(c[v],a[p^.v])>c[p^.v] then
begin
c[p^.v]:=max(c[v],a[p^.v]);
if not f[p^.v] then
begin
f[p^.v]:=true;
q[t]:=p^.v;
t:=(t+1) mod n;
end;
end;
p:=p^.next;
end;
f[v]:=false;
h:=(h+1) mod n;
end;
ans:=0;
for i:=1 to n do if c[i]-d[i]>ans then ans:=c[i]-d[i];
writeln(ans);
close(input); close(output);
end.


负权环 一个节点超过n次进队 spfa 记录。。。
var g:array [1..1000,1..1000] of longint; { 邻接矩阵，结点间距离，0 表示不连通 }
d:array [1..1000] of longint; { d[i] 表示源点到顶点 i 的距离 }
f:array [1..1000] of boolean; { f[i] 表示结点 i 是否在队列中 }
q:array [0..1000] of longint; { 循环队列，为方便运算，从 0 下标开始 }
c:array [1..1000] of longint; { c[i] 用于统计结点 i 进队次数 }
n,v0,a,b,w,h,t,k,v:longint;
ans:string;
begin
assign(input,'Negative.in'); reset(input); assign(output,'Negative.out'); rewrite(output);
readln(n,v0);
fillchar(g,sizeof(g),0);
while not eof do begin
readln(a,b,w);
g[a,b]:=w; { 读入并存储所有的有向边 }
end;
ans:='No';
for v:=1 to n do d[v]:=maxlongint; { 预置源点 v0 至各顶点 v 的距离为无穷大 }
d[v0]:=0;
fillchar(f,sizeof(f),0);
fillchar(c,sizeof(c),0);
q[0]:=v0; h:=0; t:=1; { v0 进队列，并设置队列指针，尾针指向一空位 }
f[v0]:=true; c[v0]:=1;
while h<>t do begin { 循环队列，h 指向队列首结点，t 指向尾后空位，h=t 时就结束 }
v:=q[h]; { 从队首中取出顶点 v }
for k:=1 to n do
if (g[v,k]<>0) and (d[v]+g[v,k]<d[k]) then
begin
d[k]:=d[v]+g[v,k]; { 更新到 k 的最短距离 }
if not f[k] then { 若 k 不在队列中，则 k 进队列 }
begin
f[k]:=true; q[t]:=k; t:=(t+1) mod n;
inc(c[k]);
if c[k]>n then begin ans:='Yes'; t:=(h+1) mod n; break; end;
end; { 进队次数超过 n ，修改队尾以便让宽搜结束 }
end;
f[v]:=false; { 出队 }
h:=(h+1) mod n; { 移动队首指针 }
end;
writeln(ans);
close(input); close(output); { 此为 spfa 算法，求源点到其它各点的最短距离 }
end.

ST
program RMQ;
var
a:array[1..200000] of longint;
f:array[1..200000,0..19] of longint;
d:array[0..19] of longint;
n,i,m,k,x,y:longint;
function max(x,y:longint):longint;
begin
if y>x
then max:=y
else max:=x;
end;
procedure ready;
var
i,j,t:integer;
begin
for i:=1 to n do
f[i,0]:=a[i];
t:=trunc(ln(n)/ln(2));
for j:=1 to t do
for i:=1 to n do
if i+d[j]-1<=n
then f[i,j]:=max(f[i,j-1],f[i+d[j-1],j-1])
else break;
end;
begin
readln(n);
for i:=1 to n do//读入n个数据
read(a[i]);
readln(m);
d[0]:=1;
for i:=1 to 19 do//计算2^n
d[i]:=d[i-1]*2;
ready;//预处理
for i:=1 to m do
begin
readln(x,y);
if x<>y
then begin
k:=trunc(ln(y-x+1)/ln(2));
writeln(max(f[x,k],f[y-d[k]+1,k]));//回答每个提问
end
else writeln(a[x]);
end;
end.