⑴ noip中的最常用的演算法
沒有哪個更重要，要因題而異的。
DP方程：
1. 資源問題1
-----機器分配問題
F[I,j]:=max(f[i-1,k]+w[i,j-k])
2. 資源問題2
------01背包問題
F[I,j]:=max(f[i-1,j-v[i]]+w[i],f[i-1,j]);
3. 線性動態規劃1
-----樸素最長非降子序列
F[i]:=max{f[j]+1}
4. 剖分問題1
-----石子合並
F[i,j]:=min(f[i,k]+f[k+1,j]+sum[i,j]);
5. 剖分問題2
-----多邊形剖分
F[I,j]:=min(f[i,k]+f[k,j]+a[k]*a[j]*a[i]);
6. 剖分問題3
------乘積最大
f[i,j]:=max(f[k,j-1]*mult[k,i]);
7. 資源問題3
-----系統可靠性(完全背包)
F[i,j]:=max{f[i-1,j-c[i]*k]*P[I,x]}
8. 貪心的動態規劃1
-----快餐問題
F[i,j]表示前i條生產線生產j個漢堡,k個薯條所能生產的最多飲料,
則最多套餐ans:=min{j div a,k div b,f[I,j,k] div c}
F[i,j,k]:=max{f[i-1,j',k']+(T[i]-(j-j')*p1-(k-k')*p2) div p3}
時間復雜度 O(10*100^4)
9. 貪心的動態規劃2
-----過河 f[i]=min{{f(i-k)} (not stone[i])
{f(i-k)}+1} (stone[i]); +貪心壓縮狀態
10. 剖分問題4
-----多邊形-討論的動態規劃
F[i,j]:=max{正正 f[I,k]*f[k+1,j];
負負 g[I,k]*f[k+1,j];
正負 g[I,k]*f[k+1,j];
負正 f[I,k]*g[k+1,j];} g為min
11. 樹型動態規劃1
-----加分二叉樹 (從兩側到根結點模型)
F[I,j]:=max{f[I,k-1]*f[k+1,j]+c[k]}
12. 樹型動態規劃2
-----選課 (多叉樹轉二叉樹,自頂向下模型)
F[I,j]表示以i為根節點選j門功課得到的最大學分
f[i,j]:=max{f[t[i].l,k]+f[t[i].r,j-k-1]+c[i]}
13. 計數問題1
-----砝碼稱重
const w:array[1..n] of shortint=(1，2，3，5，10，20)；
//不同砝碼的重量
var a:array [1..n] of integer;
//不同砝碼的個數
f[0]:=1; 總重量個數(Ans)
f[1]:=0; 第一種重量0;
f[f[0]+1]=f[j]+k*w[j];
(1<=i<=n; 1<=j<=f[0]; 1<=k<=a[i];)
14. 遞推天地1
------核電站問題
f[-1]:=1; f[0]:=1;
f[i]:=2*f[i-1]-f[i-1-m]
15. 遞推天地2
------數的劃分
f[i,j]:=f[i-j,j]+f[i-1,j-1];
16. 最大子矩陣1
-----一最大01子矩陣
f[i,j]:=min(f[i-1,j],v[i,j-1],v[i-1,j-1])+1;
ans:=maxvalue(f);
17. 判定性問題1
-----能否被4整除
g[1,0]:=true; g[1,1]:=false; g[1,2]:=false; g[1,3]:=false;
g[i,j]:=g[i-1,k] and ((k+a[i,p]) mod 4 = j)
18. 判定性問題2
-----能否被k整除
f[I,j±n[i] mod k]:=f[i-1,j]; -k<=j<=k; 1<=i<=n
20. 線型動態規劃2
-----方塊消除游戲
f[i,i-1,0]:=0
f[i,j,k]:=max{f[i,j-1,0]+sqr(len(j)+k),
f[i,p,k+len[j]]+f[p+1,j-1,0]}
ans:=f[1,m,0]
21. 線型動態規劃3
-----最長公共子串，LCS問題
f[i,j]={0 (i=0)&(j=0);
f[i-1,j-1]+1 (i>0,j>0,x[i]=y[j]);
max{f[i,j-1]+f[i-1,j]}} (i>0,j>0,x[i]<>y[j]);
let(n>m); (n=length(a); m:=length(b));
for i:= 1 to n do
begin
x:=-1; p:=1;
for j:= 1 to m do
if a[i]=b[j] then
begin
x:=p;
while flag[j,x] and (f[j,x]<a[i]) do inc(x);
p:=x;
f[j,x]:=a[i];
flag[j,x]:=true;
end
else
if (x<>-1) and flag[j-1,x] and ((not flag[j,x]) or (f[j-1,x]<f[j,x])) then
begin
f[j,x]:=f[j-1,x];
flag[j,x]:=true;
end else x:=-1;
end;
ok:=false;
for i:= m downto 1 do
if flag[m,i] then begin writeln(i); ok:=true; break; end;
if not ok then writeln(0);
22. 最大子矩陣2
-----最大帶權01子矩陣O(n^2*m)
枚舉行的起始，壓縮進數列，求最大欄位和，遇0則清零
f[i]:=max(f[i-1]+a[i],a[i])
readln(n,m);
for i:= 1 to n do for j:= 1 to m do read(a[i,j]);
ans:=-maxlongint;
for i:= 1 to n do
begin
fillchar(b,sizeof(b),0);
fillchar(u,sizeof(u),0);
for j:= i to n do
begin
max:=0;
for k:= 1 to m do
begin
if (a[j,k]<>0) and (not u[k]) then
begin
inc(b[k],a[j,k]);
inc(max,b[k])
end
else
begin
max:=0;
u[k]:=true;
end;
if max>ans then ans:=max;
end;
end;
end;
23. 資源問題4
-----裝箱問題(判定性01背包)
f[j]:=(f[j] or f[j-v[i]]);
注: 這里將數字三角形的意義擴大
凡狀態轉移為圖形,跟其上面階段和前面狀態有關都叫數字三角形:)
24. 數字三角形1
-----樸素の數字三角形
f[i,j]:=max(f[i+1,j]+a[I,j],f[i+1,j+1]+a[i,j]);
25. 數字三角形2
-----晴天小豬歷險記之Hill
同一階段上暴力動態規劃
if[i,j]:=min(f[i,j-1],f[I,j+1],f[i-1,j],f[i-1,j-1])+a[i,j]
26. 雙向動態規劃1
數字三角形3
-----小胖辦證
f[i,j]:=max(f[i-1,j]+a[i,j],f[i,j-1]+a[i,j],f[i,j+1]+a[i,j])
27. 數字三角形4
-----過河卒
//邊界初始化
f[i,j]:=f[i-1,j]+f[i,j-1];
28. 數字三角形5
-----樸素的打磚塊
f[i,j,k]:=max(f[i-1,j-k,p]+sum[i,k],f[i,j,k]);
29. 數字三角形6
-----優化的打磚塊
f[I,j,k]:=max{g[i-1,j-k,k-1]+sum[I,k]}
30. 線性動態規劃3
-----打鼴鼠』
f[i]:=f[j]+1;(abs(x[i]-x[j])+abs(y[i]-y[j])<=t[i]-t[j])
31. 樹形動態規劃3
-----貪吃的九頭龍
32. 狀態壓縮動態規劃1
-----炮兵陣地
Max(f[Q*(r+1)+k],g[j]+num[k])
If (map[i] and plan[k]=0) and
((plan[P] or plan[q]) and plan[k]=0)
33. 遞推天地3
-----情書抄寫員
f[i]:=f[i-1]+k*f[i-2]
34. 遞推天地4
-----錯位排列
f[i]:=(i-1)(f[i-2]+f[i-1]);
f[n]:=n*f[n-1]+(-1)^(n-2);
35. 遞推天地5
-----直線分平面最大區域數
f[n]:=f[n-1]+n
:=n*(n+1) div 2 + 1;
36. 遞推天地6
-----折線分平面最大區域數
f[n]:=(n-1)(2*n-1)+2*n;
37. 遞推天地7
-----封閉曲線分平面最大區域數
f[n]:=f[n-1]+2*(n-1)
:=sqr(n)-n+2;
38 遞推天地8
-----凸多邊形分三角形方法數
f[n]:=C(2*n-2,n-1) div n;
對於k邊形
f[k]:=C(2*k-4,k-2) div (k-1); //(k>=3)
39 遞推天地9
-----Catalan數列一般形式
1,1,2,5,14,42,132
f[n]:=C(2k,k) div (k+1);
40 遞推天地10
-----彩燈布置
排列組合中的環形染色問題
f[n]:=f[n-1]*(m-2)+f[n-2]*(m-1); (f[1]:=m; f[2]:=m(m-1);
41 線性動態規劃4
-----找數
線性掃描
sum:=f[i]+g[j];
(if sum=Aim then getout; if sum<Aim then inc(i) else inc(j);)
42 線性動態規劃5
-----隱形的翅膀
min:=min{abs(w[i]/w[j]-gold)};
if w[i]/w[j]<gold then inc(i) else inc(j);
43 剖分問題5
-----最大獎勵
f[i]:=max(f[i],f[j]+(sum[j]-sum[i])*i-t
44 最短路1
-----Floyd
f[i,j]:=max(f[i,j],f[i,k]+f[k,j]);
ans[q[i,j,k]]:=ans[q[i,j,k]]+s[i,q[i,j,k]]*s[q[i,j,k],j]/s[i,j];
45 剖分問題6
-----小H的小屋
F[l,m,n]:=f[l-x,m-1,n-k]+S(x,k);
function GetS(l,n:longint):extended;
begin
if (n=0) or (n>l) then exit(WQ)
else getS:=(l mod n)*k2*sqr(l div n+1)+
(n-l mod n)*k2*sqr(l div n)+
k1*sqr(l);
end;
if x+S(x,k)>=f[i,q,p] then break else f[i,q,p]:=x+S(x,k);inc(k);
46 計數問題2
-----隕石的秘密（排列組合中的計數問題）
Ans[l1,l2,l3,D]:=f[l1+1,l2,l3,D+1]-f[l1+1,l2,l3,D];
F[l1,l2,l3,D]:=Sigma(f[o,p,q,d-1]*f[l1-o,l2-p,l3-q,d]);
47 線性動態規劃
------合唱隊形
兩次F[i]:=max{f[j]+1}＋枚舉中央結點
48 資源問題
------明明的預算方案：加花的動態規劃
f[i,j]:=max(f[i,j],f[l,j-v[i]-v[fb[i]]-v[fa[i]]]+v[i]*p[i]+v[fb[i]]*p[fb[i]]+v[fa[i]]*p[fa[i]]);
49 資源問題
-----化工場裝箱員
50 樹形動態規劃
-----聚會的快樂
f[i,2]:=max(f[i,0],f[i,1]);
f[i,1]:=sigma(f[t[i]^.son,0]);
f[i,0]:=sigma(f[t[i]^.son,3]);
51 樹形動態規劃
-----皇宮看守
f[i,2]:=max(f[i,0],f[i,1]);
f[i,1]:=sigma(f[t[i]^.son,0]);
f[i,0]:=sigma(f[t[i]^.son,3]);
52 遞推天地
-----盒子與球
f[i,1]:=1;
f[i,j]:=j*(f[i-1,j-1]+f[i-1,j]);
53 雙重動態規劃
-----有限的基因序列
f[i]:=min{f[j]+1}
g[c,i,j]:=(g[a,i,j] and g[b,i,j]) or (g[c,i,j])
54 最大子矩陣問題
-----居住空間
f[i,j,k]:=min(min(min(f[i-1,j,k],f[i,j-1,k]),
min(f[i,j,k-1],f[i-1,j-1,k])),
min(min(f[i-1,j,k-1],f[i,j-1,k-1]),
f[i-1,j-1,k-1]))+1;
55 線性動態規劃
------日程安排
f[i]:=max{f[j]}+P[I]; (e[j]<s[i])
56 遞推天地
------組合數
C[I,j]:=C[i-1,j]+C[I-1,j-1]
C[I,0]:=1
57 樹形動態規劃
-----有向樹k中值問題
F[I,r,k]:=max{max{f[l[i],I,j]+f[r[i],I,k-j-1]},f[f[l[i],r,j]+f[r[i],r,k-j]+w[I,r]]}
58 樹形動態規劃
-----CTSC 2001選課
F[I,j]:=w[i](if i∈P)+f[l[i],k]+f[r[i],m-k](0≤k≤m)(if l[i]<>0)
59 線性動態規劃
-----多重歷史
f[i,j]:=sigma{f[i-k,j-1]}(if checked)
60 背包問題(+-1背包問題+回溯)
-----CEOI1998 Substract
f[i,j]:=f[i-1,j-a[i]] or f[i-1,j+a[i]]
61 線性動態規劃(字元串)
-----NOI 2000 古城之謎
f[i,1,1]:=min{f[i+length(s),2,1], f[i+length(s),1,1]+1} f[i,1,2]:=min{f[i+length(s),1,2]+words[s],f[i+length(s),1,2]+words[s]}
62 線性動態規劃
-----最少單詞個數
f[i,j]:=max{f[I,j],f[u-1,j-1]+l}
63 線型動態規劃
-----APIO2007 數據備份
狀態壓縮＋剪掉每個階段j前j*2個狀態和j*2+200後的狀態貪心動態規劃
f[i]:=min(g[i-2]+s[i],f[i-1]);
64 樹形動態規劃
-----APIO2007 風鈴
f[i]:=f[l]+f[r]+{1 (if c[l]<c[r])}
g[i]:=1(d[l]<>d[r]) 0(d[l]=d[r])
g[l]=g[r]=1 then Halt;
65 地圖動態規劃
-----NOI 2005 adv19910
F[t,i,j]:=max{f[t-1,i-dx[d[[t]],j-dy[d[k]]]+1],f[t-1,i,j];
66 地圖動態規劃
-----優化的NOI 2005 adv19910
F[k,i,j]:=max{f[k-1,i,p]+1} j-b[k]<=p<=j;
67 目標動態規劃
-----CEOI98 subtra
F[I,j]:=f[I-1,j+a[i]] or f[i-1,j-a[i]]
68 目標動態規劃
----- Vijos 1037搭建雙塔問題
F[value,delta]:=g[value+a[i],delta+a[i]] or g[value,delta-a[i]]
69 樹形動態規劃
-----有線電視網
f[i,p]:=max(f[i,p],f[i,p-q]+f[j,q]-map[i,j])
leaves[i]>=p>=l, 1<=q<=p;
70 地圖動態規劃
-----vijos某題
F[I,j]:=min(f[i-1,j-1],f[I,j-1],f[i-1,j]);
71 最大子矩陣問題
-----最大欄位和問題
f[i]:=max(f[i-1]+b[i],b[i]); f[1]:=b[1]
72 最大子矩陣問題
-----最大子立方體問題
枚舉一組邊i的起始，壓縮進矩陣 B[I,j]+=a[x,I,j]
枚舉另外一組邊的其實，做最大子矩陣
73 括弧序列
-----線型動態規劃
f[I,j]:=min(f[I,j],f[i+1,j-1](s[i]s[j]=」()」or(」[]」)),
f[I+1,j+1]+1 (s[j]=」(」or」[」 ] , f[I,j-1]+1(s[j]=」)」or」]」 )
74 棋盤切割
-----線型動態規劃
f[k,x1,y1,x2,y2]=min{min{f[k-1,x1,y1,a,y2]+s[a+1,y1,x2,y2],
f[k-1,a+1,y1,x2,y2]+s[x1,y1,a,y2]
min{}}
75 概率動態規劃
-----聰聰和可可(NOI2005)
x:=p[p[i,j],j]
f[I,j]:=(f[x,b[j,k]]+f[x,j])/(l[j]+1)+1
f[I,i]=0
f[x,j]=1
76 概率動態規劃
-----血緣關系
我們正在研究妖怪家族的血緣關系。每個妖怪都有相同數量的基因，但是不同的妖怪的基因可能是不同的。我們希望知道任意給定的兩個妖怪之間究竟有多少相同的基因。由於基因數量相當龐大，直接檢測是行不通的。但是，我們知道妖怪家族的家譜，所以我們可以根據家譜來估算兩個妖怪之間相同基因的數量。
妖怪之間的基因繼承關系相當簡單：如果妖怪C是妖怪A和B的孩子，則C的任意一個基因只能是繼承A或B的基因，繼承A或B的概率各佔50％。所有基因可認為是相互獨立的，每個基因的繼承關系不受別的基因影響。
現在，我們來定義兩個妖怪X和Y的基因相似程度。例如，有一個家族，這個家族中有兩個毫無關系(沒有相同基因)的妖怪A和B，及它們的孩子C和D。那麼C和D相似程度是多少呢？因為C和D的基因都來自A和B，從概率來說，各佔50％。所以，依概率計算C和D平均有50％的相同基因，C和D的基因相似程度為50％。需要注意的是，如果A和B之間存在相同基因的話，C和D的基因相似程度就不再是50％了。
你的任務是寫一個程序，對於給定的家譜以及成對出現的妖怪，計算它們之間的基因相似程度。
F[A, B]=(f[A0, B]+P[A1, B])/2
f[I,i]=1
f[I,j]=0(I,j無相同基因)
77 線性動態規劃
-----決斗
F[I,j]=(f[I,j] and f[k,j]) and (e[I,k] or e[j,k]),i<k<j
78 線性動態規劃
-----舞蹈家
F[x,y,k]=min(f[a[k],y,k+1]+w[x,a[k]],f[x,a[k],k+1]+w[y,a[k]])
79 線性動態規劃
-----積木游戲
F[I,a,b,k]=max(f[I,a+1,b,k],f[i+1,a+1,a+1,k』],f[I,a+1,a+1,k』])
80 樹形動態規劃（雙次記錄）
-----NOI2003 逃學的小孩
樸素的話枚舉節點i和離其最遠的兩個節點 j,k O(n^2)
每個節點記錄最大的兩個值，並記錄這最大值分別是從哪個相鄰節點傳過來的。當遍歷到某個孩子節點的時候，只需檢查最大值是否是從該孩子節點傳遞來的。如果是，就取次大，否則取最大值
81 樹形動態規劃(完全二叉樹)
-----NOI2006 網路收費
F[I,j,k]表示在點i所管轄的所有用戶中，有j個用戶為A，在I的每個祖先u上，如果N[a]>N[b]則標0否則標1，用二進制狀態壓縮進k中，在這種情況下的最小花費
F[I,j,k]:=min{ f[l,u,k and (s[i]<<(i-1))]
+w1,f[r,j-u,k and(s[i]<<(i-1))]}
82 樹形動態規劃
-----IOI2005 河流
F[i]:=max
83 記憶化搜索
-----Vijos某題,忘了
F[pre,h,m]:=sigma{SDP(I,h+1,M+i)} (pre<=i<=M＋1)
84 狀態壓縮動態規劃
-----APIO 2007 動物園
f[I,k]:=f[i-1,k and not (1<<4)] + NewAddVal
85 樹形動態規劃
-----訪問術館
f[i,j-c[i]×2]:= max ( f[l[i],k], f[r[i],j-c[i]×2-k] )
86 字元串動態規劃
-----Ural 1002 Phone
if exist((s,j,i-j)) then f[i]:=min(f[i],f[j]+1);
87 多進程動態規劃
-----CEOI 2005 service
Min( f[i,j,k], f[i-1,j,k] + c[t[i-1],t[i]] )
Min( f[i,t[i-1],k], f[i-1,j,k] + c[j,t[i]] )
Min( f[i,j,t[i-1]], f[i-1,j,k] + c[k,t[i]] )
88 多進程動態規劃
-----Vijos1143 三取方格數
max(f[i,j,k,l],f[i-1,j-R[m,1],k-R[m,2],l-R[m,3]]);
if (j=k) and (k=l) then inc(f[i,j,k,l],a[j,i-j]) else
if (j=k) then inc(f[i,j,k,l],a[j,i-j]+a[l,i-l]) else
if (k=l) then inc(f[i,j,k,l],a[j,i-j]+a[k,i-k]) else
if (j=l) then inc(f[i,j,k,l],a[j,i-j]+a[k,i-k]) else
inc(f[i,j,k,l],a[j,i-j]+a[k,i-k]+a[l,i-l]);
89 線型動態規劃
-----IOI 2000 郵局問題
f[i,j]:=min(f[I,j],f[k,j-1]+d[k+1,i]);
90 線型動態規劃
-----Vijos 1198 最佳課題選擇
if j-k>=0 then Min(f[i,j],f[i-1,j-k]+time(i,k));
91 背包問題
----- USACO Raucous Rockers
多個背包，不可以重復放物品，但放物品的順序有限制。
F[I,j,k]表示決策到第i個物品、第j個背包，此背包花費了k的空間。
f[I,j,k]:=max(f[I-1,j,k],f[I-1,j,k-t[i]]+p[i],f[i-1,j-1,maxtime-t[i]])
92 多進程動態規劃
-----巡遊加拿大（IOI95、USACO）
d[i,j]=max{d[k,j]+1(a[k,i] & j<k<i),d[j,k]+1(a[I,j] & (k<j))}。
f[i,j]表示從起點出發，一個人到達i，另一個人到達j時經過的城市數。d[i,j]=d[j,i]，所以我們限制i>j
分析狀態(i,j)，它可能是(k,j)(j<k<i)中k到達i得到（方式1），也可能是(j,k)(k<j)中k超過j到達i得到（方式2）。但它不能是(i,k)(k<j)中k到達j得到，因為這樣可能會出現重復路徑。即使不會出現重復路徑，那麼它由(j,k)通過方式2同樣可以得到，所以不會遺漏解 時間復雜度O(n3)
93 動態規劃
-----ZOJ cheese
f[i,j]:=f[i-kk*zl[u,1],j-kk*zl[u,2]]+a[i-kk*zl[u,1],j-kk*zl[u,2]]
94 動態規劃
-----NOI 2004 berry 線性
F[I,1]:=s[i]
F[I,j]:=max{min{s[i]-s[l-1]},f[l-1,j-1]} (2≤j≤k, j≤l≤i)
95 動態規劃
-----NOI 2004 berry 完全無向圖
F[I,j]:=f[i-1,j] or (j≥w[i]) and (f[i-1,j-w[i]])
96 動態規劃
-----石子合並 四邊形不等式優化
m[i,j]=max{m[i+1,j], m[i,j-1]}+t[i,j]
97 動態規劃
-----CEOI 2005 service
（k≥long[i]，i≥1）g[i, j, k]=max{g[i-1,j,k-long[i]]+1，g[i-1,j,k]}
（k<long[i]，i≥1） g[i, j, k]=max{g[i-1,j-1,t-long[i]]+1，g[i-1,j,k]}
(0≤j≤m， 0≤k<t) g[0,j,k]=0;
ans:=g[n,m,0]。
狀態優化：g[i, j]=min{g[i-1,j]，g[i-1,j-1]+long[i]}
其中(a, b)+long[i]=(a』, b』)的計算方法為：
當b+long[i] ≤t時： a』=a; b』=b+long[i];
當b+long[i] ＞t時： a』=a+1; b』=long[i];
規劃的邊界條件：
當0≤i≤n時，g[i,0]=(0,0)
98 動態規劃
-----AHOI 2006寶庫通道
f[k]:=max{f[k-1]+x[k,j]-x[k,i-1], x[k,j]-x[k,i-1]}
for i:= 1 to n do
begin
for j:= 1 to m do
begin
read(a[i,j]);
if a[i,j]='1' then x[i,j]:=x[i,j-1]+1
else x[i,j]:=x[i,j-1]-1;
end;
readln;
end;
for i:= 1 to m do
for j:= i to m do
begin
y:=0;
for k:= 1 to n do
begin
z:=x[k,j]-x[k,i-1];
if y>0 then inc(y,z) else y:=z;
if y>ans then ans:=y;
end;
end;
99 動態規劃
-----Travel
A) 費用最少的旅行計劃。
設f[i]表示從起點到第i個旅店住宿一天的最小費用；g[i]表示從起點到第i個旅店住宿一天，在滿足最小費用的前提下所需要的最少天數。那麼：
f[i]=f[x]+v[i], g[i]=g[x]+1
x滿足：
1、 x<i，且d[i] – d[x] <= 800（一天的最大行程）。
2、 對於所有的t < i, d[i] – d[t] <= 800，都必須滿足：
A. g[x] < g[t](f[x] = f[t]時) B. f[x] < f[t] (其他情況)
f[0] = 0，g[0] = 0。 Ans:=f[n + 1]，g[n+1]。
B). 天數最少的旅行計劃。
方法其實和第一問十分類似。
設g』[i]表示從起點到第i個旅店住宿一天的最少天數；f』[i]表示從起點到第i個旅店住宿一天，在滿足最小天數前提下所需要的最少費用。那麼：
g』[i] = g』[x] + 1, f』[i] = f』[x] + v[i]
x滿足：
1、 x<i，且d[i] – d[x] <= 800（一天的最大行程）。
2、 對於所有的t < i, d[i] – d[t] <= 800，都必須滿足：
f』[x] < f』[t] g』[x] = g』[t]時
g』[x] < g』[t] 其他情況
f』[0] = 0，g』[0] = 0。 Ans:=f』[n + 1]，g』[n+1]。
100 動態規劃
-----NOI 2007 cash
y:=f[j]/(a[j]*c[j]+b[j]);
g:=c[j]*y*a[i]+y*b[i];
f[i]:=max(f[i],g)
⑵ 極高分求 noip 常用演算法 c++源碼
什麼？是C++……無奈，我手頭的程序都是PASCAL的……
1、初等演算法
2、高精度的四則運算
3、查找演算法（順序查找、二分法、哈希查找等等）
這三個較簡單，在網路上搜索即可
4、排序演算法
其實只需要背快排、堆排即可，其他的速度比較慢不推薦
5、分枝限界法
網路搜索
6、圖的演算法
floodfill：
#include <graphics.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
int main(void)
{
/* request auto detection */
int gdriver = DETECT, gmode, errorcode;
int maxx, maxy;
/* initialize graphics, local variables */
initgraph(&gdriver, &gmode, "");
/* read result of initialization */
errorcode = graphresult();
if (errorcode != grOk)
/* an error occurred */
{
printf("Graphics error: %s\n",
grapherrormsg(errorcode));
printf("Press any key to halt:");
getch();
exit(1);
/* terminate with an error code */
}
maxx = getmaxx();
maxy = getmaxy();
/* select drawing color */
setcolor(getmaxcolor());
/* select fill color */
setfillstyle(SOLID_FILL, getmaxcolor());
/* draw a border around the screen */
rectangle(0, 0, maxx, maxy);
/* draw some circles */
circle(maxx / 3, maxy /2, 50);
circle(maxx / 2, 20, 100);
circle(maxx-20, maxy-50, 75);
circle(20, maxy-20, 25);
/* wait for a key */
getch();
/* fill in bounded region */
floodfill(2, 2, getmaxcolor());
/* clean up */
getch();
closegraph();
return 0;
}
7、其他：
KMP:
#include<iostream>
#include<time.h>
#include<string>
using namespace std;
void init(string ,string);
void show(char [],int);
int kmp(string ,string,int pos);
void get_next(char*,int *);
string s1,t1;
int m,n;
char *s;
char *t;
int *next;
/*************************MAIN**************************************/
int main(int argc[],char*args[])
{
double t=clock();
cout<<"找到位置為："<<kmp("acbsabcaacabaabaabcacaabc","abaabca",1)<<endl;
delete[] s;
delete[] next;
cout<<"耗時："<<(clock()-t)/1000<<"毫秒！"<<endl;
return 0;
}
/**********************++++NEXT++++********************************/
void get_next(char s[],int ne[])
{
ne =new int[n+1];
next=new int[n+1];
ne[0]=9999;
int i(1),j(0);
ne[1]=0;
while(i<=(int)(t[0]))//數組是字元型的，要轉化為整數
{
if(j==0||t[i]==t[j]){++i;++j;ne[i]=j;}
else j=ne[j];
}
for( i=1;i<=n;i++)
{
cout<<"next["<<i<<"]="<<ne[i]<<endl;
next[i]=ne[i];
}
}
/********************++++KMP+++**********************************/
int kmp(string s0,string t0,int pos)
{
init(s0,t0);
int i=pos,j=1;
while(i<=((int)(s[0]))&&(j<=((int)(t[0]))))
{
if((j==0)||(s[i]==t[j])){++i;++j;}
else j=next[j];
}
if(j>(int)(t[0])) return i-((int)(t[0]));
else return 0;
}
/**********************************************************/
void init(string ss,string tt)
{ s1=ss;
t1=tt;
m=s1.length();
n=t1.length();
//if((s=(char*)malloc((m+1)*sizeof(char)))<0){cout<<"failed\n";return;}
s=new char[m+1];
s[0]=m;
//if((t=(char*) malloc((n+1)*sizeof(char)))<0) {cout<<"failed\n";return;}
t=new char[n+1];
t[0]=n;
for(int i=1;i<=m;i++)
s[i]=s1.at(i-1);
for( i=1;i<=n;i++)
t[i]=t1.at(i-1);
cout<<"原字元串"; show(s,m);
cout<<"模式字元串： "; show(t,n);
get_next(t,next);
}
/*******************++++SHOW+++**************************************/
void show(char s[],int n )
{
for(int i=1;i<=n;i++)
cout<<s[i]<<" ";
cout<<endl;
cout<<"length： "<<int(s[0])<<"\n";
}
prim:
#include <stdio.h>
#define INFINITY 32767
#define MAX 4
typedef struct{
int vexnum;
int arcs[MAX][MAX];
}Graph;//圖的結構體
//*****************創建圖的鄰接矩陣 *****************
void Creat_Graph(Graph *g)
{
int i,j,v1,v2,w,num;
printf("please input vertex number:\n");
scanf("%d",&num);
g->vexnum=num;
for(i=0;i<num;i++)
for(j=0;j<num;j++)
if(i==j)
g->arcs[i][j]=0; //無環，對角線為0
else
g->arcs[i][j]=INFINITY;
printf("please input vertex ,vertex ,weight :(end with -1,-1)\n");
do
{ printf("<vertex1,vertex2,weight>:");
scanf("%d,%d,%d",&v1,&v2,&w);
if(v1>=0&&v1<num&&v2>=0&&v2<num)
{
g->arcs[v1][v2]=w;
g->arcs[v2][v1]=w;
}
}while(!(v1==-1&&v2==-1));//循環的條件
}
Kruskal:
#include<iostream>
#include<vector>
#include<algorithm>
#define max 100
using namespace std;
struct Edge{
int vi,vj,w;
};
bool lequal(Edge const* t1, Edge const* t2){
return (t1->w<t2->w);
}
int V,E;
vector <Edge*>edges;
vector <Edge*>mst;
int cicles[max];
int main(){
int i,W,number,c;
Edge *e;
c=1;
while(true){
edges.clear();
mst.clear();
cin>>V>>E;
if(!V && !E) break;
for(i=0;i<E;i++){
e = new Edge;
cin>>e->vi>>e->vj>>e->w;
edges.push_back(e);
}
sort(edges.begin(),edges.end(),lequal);
for(i=0;i<V;i++) cicles[i] = i;
while(mst.size()<(V-1) && edges.size()){
if(cicles[edges[0]->vi]!=cicles[edges[0]->vj]){
number = cicles[edges[0]->vj];
for(i=0;i<V;i++) {
if(cicles[i]==number)
cicles[i] = cicles[edges[0]->vi];
}
mst.push_back(edges[0]);
}
edges.erase(edges.begin(),edges.begin()+1);
}
W = 0;
for(i=0;i<mst.size();i++) {
W+=mst[i]->w;
}
cout<<"Case "<<c++<<":"<<endl;
cout<<"The Minimun Spanning Tree has cost: "<<W<<endl;
}
return 0;
}
floyd:
program floyd;
var st,en,f:integer;
n,i,j,x:integer;
a:array[1..10,1..10]of integer;
path,map1,map2:array[1..10,1..10]of integer;
begin
readln(n);
for i:=1 to n do
begin
for j:=1 to n do
begin
read(a[i,j]);
path[i,j]:=j;
end;
readln;
end;
for x:=1 to n do
for i:=1 to n do
for j:=1 to n do
if a[i,j]>a[i,x]+a[x,j] then
begin
a[i,j]:=a[i,x]+a[x,j];
path[i,j]:=path[i,x];
end;
readln(st,en);
writeln(a[st,en]);
writeln;
f:=st;
while f<> en do
begin
write(f);
write('=>');
f:=path[f,en];
end;
write(en);
end.
完畢
⑶ NOIP普及拿一等需掌握的演算法
第一題
啊，這位同學，想我兩年前也是如此，結果去年，那個悲傷的故事，我明悟了，演算法有毛用，woc，第一第二題題目都看錯，縱使，二等獎，所以看清題目很重要很重要
回到正題
第一題，多半很水，排序模擬的結合
第二題，1：回溯，2：遞歸遞推，應該算簡單，大概是數論
這些，你要做到的是別看錯題目，否則又一隻悲劇
第三題，1：模擬，貪心結合，考慮范圍很廣2:很高深的動規，也就是DP，種類很多，也有可能留在第四題
第四題圖論樹，各種困難，我也沒掌握
至於題目，www.wikioi.com，現在好像是www.codves.cn，反正一樣，你可以按照題型結構，自己做
至於資料，它，我發不上來，以前可以的，所以你如果要的話，加我qq702294175
⑷ NOIP2015提高組Day1第二題，求解題報告及分布說明
NOIP2015提高組復賽Day1第二題解題報告
By 某蒟蒻zrw
1. 題目大概描述（因為寫的時候題目還沒放出來）
幾個小盆友們在傳遞自己的信息（生日），並且每個小盆友只會把自己知道的信息傳給唯一的一個人【但是自己可以收到很多信息，並會在收到信息的下一輪把這些信息傳給那個唯一的人】（單相思233333），問多少輪後自己會收到自己一開始傳遞出去的自己的信息。
輸入：第一行一個整數n，表示有n個人
接下來n行，每行一個數j，設這是除第一行外的第i行，那麼j表示第i個人只會把信息傳給第j個人。
輸出：一個整數，表示最少幾輪後自己的信息會回到自己手中。
樣例輸入：
5
2 4 2 3 1
樣例輸出：
3
數據規模：100% n<=200000 60% n<=2500 30% 記不住了……
2. 大概需要什麼樣的演算法
根據數據規模，我們可以大概判斷需要多少效率的演算法，甚至有的時候可以猜出這題用的是什麼演算法。對於本題來說，60%大概就是O(n^2)的演算法了，一般是裸的暴力回溯或者是暴力廣搜，也有用floyd的（我是從NOIP吧上看到的）。
如果要AC的話，演算法效率至少要在O(nlogn)以下（log在這里是以2為底不是以10為底）。
然而，本題是有O(n)演算法的，下面會講。
3. 我們還是畫個圖吧（圖可能比較難看，但能看就行）
畫畫圖，就會知道這是在做一件什麼事情了。
以樣例數據為例：
我們很容易發現，2,3,4，形成了一個環，而1和5，並沒有什麼卵用……
所以在環234中，由於每一輪可以把在上一輪知道的信息傳給唯一的下一個人，在234環中，就需要3輪，信息才能傳到
多畫幾個圖（由於本人很懶，就只畫一張特殊情況比較多的小圖）：
（有木有一種貴圈真亂的感覺）
我們可以看出來，1,5,6，成了一個環，而2,3,4,8，也成了一個環，7,9，是來打醬油的。
那麼對於這兩個環來說，因為每一輪可以傳遞上一輪信息給下一個人，所以顯然是1,5,6這個環比較早傳完，3輪。
說白了，就是在圖里找最小環。
4. ABCD，你選擇哪一個？
於是乎就有各種最短路演算法來解決這個問題了，但是我覺得時間復雜度還是有待討究。說實話我也不知道這些演算法能不能AC。比如SPFA演算法，原本是O(kE)【k為常數，約等於2，E為邊數】，到這里估計就是O(nkE)，也就是O(nE)，因為每個點只會指向唯一一條邊，所以邊就是n條，也就是O(n^2)，不作優化很有可能會炸（請注意我的措辭）。
貼吧上也有人說是用並查集，據說是可以AC，但我並不知道他是准備怎麼個並查法，我想應該是不好理解的。
5. 說白了，你還是得走這條必經之路
很明白的一件事情就是，因為一個人只會把信息傳給唯一的另一個人，我們就可以用一個一維數組來存儲這個關系。設數組為father[]，那麼father[i]表示就是第i個人可以把信息傳給第father[i]個人，這樣很省空間，訪問的時間也很省。
6. 那麼問題來了……
挖掘機……哦不，優化技術哪家強？
可能很多人到這里就卡住了。
所以我們再把樣例數據挖出來看一看：
（是不是覺得越看這個圖越不爽了？）
如果說對每一個點進行什麼SPFA啊，floyd什麼鬼的最短路演算法，那1,5這兩個路人就根本沒用了！而且對於2,3,4來說，如果每一個都把環走過去，是十分費時間的。
你要想想，官方可是有一百種方法來卡數據讓你AC不了的！
但顯然，如果用一個數組記錄這個點是否被訪問過的話，萬一從路人搜到環里，不就悲劇了？
7. 醬油，垃圾，摔掉！
如何處理掉醬油是一大問題，但在處理之前你需要了解什麼是醬油，才能處理。
沒有辦法形成環的點，就是醬油！
那怎麼樣才無法形成環呢？
煞筆，沒有人給他信息他肯定就只有自己一個人的信息嘛，也就沒辦法形成環，例如樣例中的5：
那既然沒用，那還留著幹嘛？摔掉！
然後你會發現，1也是個醬油，接著摔：
碰到了2。2的入度不為0，不進行操作。
於是乎，這就成了一個完美的環了。
說白了，就是把初始時入度為0的點刪掉，並且把指向的點的入度減一，如果減完後指向點的入度也為0了，那麼就按照剛剛那個操作繼續下去，直到找到減完後入度不為0的點。
對於某些比我還弱的人的科普：
入度：在圖中，對於某一個點，通向這個點的邊個數就是入度。同樣，相對的出度，就是從這個點出發向另一個點的邊的個數。比如樣例中5的入度為0，出度為1；1的入度為1，出度為1；2的入度為2，出度為1。
當然，設一個visit[]數組表示這個點是否被訪問過是個不錯的選擇，因為之後有用。將入度為0的點的visit設為已經訪問過。
對於剛剛第二種圖，我也進行這樣處理，得到的圖是這個樣的：
（是不是覺得舒坦很多了呢？）
如果還是沒有理解，看看下面這一小段文字：
「
我的想法就是看2 4 2 3 1
發現第五個人沒收到消息
所以把他T了
這時候1也收不到消息了
所以把1也T了
就剩下2 3 4三個人
所以輸出3
」——引用貼吧ID 詩仙Eric 的比較通俗的話
對於刪除點和邊的話，dfs（深度優先搜索，簡稱深搜）和bfs（廣度優先搜索，簡稱廣搜）都可以使用，效率應該也不會相差太多。我是喜歡拿queue裝逼的人，於是乎用了廣搜。
最壞情況，n=200000,1指向2,2指向3……一直到199998指向199999,199999指向200000,200000指向199999，O(n)，不會超時。
好了，關於「打醬油」的問題就解決了，那麼剩下的就是專心解決最小環問題了。
8. visit數組出奇跡
要知道，總是會有一個不經意的細節，影響到了結果。這就是FLAG的力量。
所以說，屎可以亂吔，FLAG不能亂立。
↑以上均為扯淡。
首先我先說一下，因為是貼吧某個盆友（好吧就是上面引用話的那個人）知道之前的演算法，但由於沒學過太多圖論的演算法，不會玩最小環，於是我拿出來講了。
說實話，我也沒學過多少圖論的演算法→_→
剛剛已經講過了，這個圖用father一維數組存是很省空間的，調用也很省時間。
於是乎就是查找入度不為0的點（其實到這個時候應該已經只剩下入度為1的了，因為每個點只有可能在一個環內，可以去稍稍畫幾個圖證明一下），然後利用father數組調用環（這個和並查集有異曲同工之處）。
但如果查找到每個點都調用一次環，那最壞的查找情況可是O(n^2)。
說好的O(nlogn)呢？
不要打架，不要打架，visit好處都有啥，誰說對了就給他！
對於樣例來說，訪問完2這個點和2,3,4這個環，3,4兩點也就都訪問過了，因為同一個環長度肯定是都一樣的，所以沒有必要再去搜3,4兩點。
那麼就用visit數組來記錄這個點是否有訪問過，當訪問一個環的時候，每次訪問到一個點，就將其標記為已經訪問過，下次for循環到這個點時就可以跳過，省時間。
這也就是剛剛為什麼入度為0的點需要設成該點已訪問過的原因——醬油哪有你出場的份嘛。
最壞情況：n=200000，1指向2,2指向3……199999指向200000,200000指向1。
for循環：n次
while查找：n次
還是O(n)
9. 總結
我是做過一些往年的提高組day1第二題的題目，但我想這次應該是最容易的了（然而這次的第3題寫個暴力都瞬間爆炸【然而我並不會寫，只會看特殊數據騙30分】），也就意味著大家都要靠明天的題目來拉分了（FJ的某方立了個FLAG說FJ有人把第3題AC了他就直播吔屎23333）（集體230的節奏）。
這題我覺得，真的，畫圖是關鍵（我記得我以前的競賽老師王老師經常說的一件事情就是數形結合），多畫圖，多模擬，就很容易找到需要解決問題的方法。我這么弱一二兩題也總共花了大概1個小時沒到半就做完了。個人認為這樣的演算法在這題里應該算是最高效的演算法之一了，因為除了最後的查找以外，已經沒有什麼重復計算的地方了。而且應該也算是最容易理解的演算法了，要AC應該沒什麼問題。至於其他的演算法，我太弱，理解不了。
順便附帶被貼吧大神舉反例後的打臉截圖（代碼也隨後放）：
⑸ 關於NOIP
NOIP級別中，普及組和提高組的要求不同。
但是這幾類動規的題目掌握了，基本也就可以了：
1、背包問題：01背包、完全背包、需要構造的多維01背包
詳見背包九講
2、最大降序：例如打導彈
3、矩陣相乘：例如能量珠子
4、買股票
5、方格取數：單向的、雙向的
6、三角取數
這些都是簡單的動規的應用，必須掌握，背也要背出來，還要會套用。
至於排序，本人認為基本的選擇排序大家都會，快速排序是一定要會的，當數據規模<500時用選擇排序，當數據規模在500和100000之間是用快速排序，但是NOIP中經常考到基數排序，例如劃分數線等，數據規模會達到1000000，用其他的排序法可能會超時一兩個測試點。
至於搜索，那是必須掌握的深搜、廣搜都要會，主要是深搜，當提高組碰到一下子想不出動規的狀態轉移方程式，深搜窮舉也是可行的，一般都能拿到不少的分數。個人之間廣搜的用處不大，程序復雜而且爆機率很高。當然n個for的窮舉法在不得已的時候也能得不少分，只要if剪枝的好，對付八後問題等問題時，時間效率比很高。
另外就是圖的遍歷，有關圖的最小生成樹、圖的單源最短路徑，也是需要很好地掌握，一直會考。當然，深搜的本事高的人可以用深搜搞定。
總結如下：要得一等，必須對模擬法和窮舉法有深刻的體會，並知道很多變通的手段；對快排要背的滾瓜爛熟；對深搜要做到不管是貪心還是動規的題，都能用深搜實現，只不過少量點超時而已；動規要記住六大模型，然後背包要理解透徹；數學很重要，數學分析的題要做對，例如排組合、凸包、計算幾何近幾年常考。有了這些，一等可以穩拿。
⑹ Noip主要是考什麼普及組的C++，主要考什麼
一、試題形式
每次NOIP的試題分四組：普及組初賽題A1、普及組復賽題A2、提高組初賽題B1和提高組復賽題B2。其中，A1和B1類型基本相同，A2和B2類型基本相同，但題目不完全相同，提高組難度高於普及組。
（一）初賽
初賽全部為筆試，2小時，滿分100分。試題由四部分組成：1、選擇題：共20題，每題1.5分，共計30分。每題有5個備選答案，前10個題為單選題（即每題有且只有一個正確答案，選對得分），後10題為不定項選擇題（即每題有1至5個正確答案，只有全部選對才得分）。普及組20個都是單選題。
2、問題求解題：共2題，每題5分，共計10分。試題給出一個敘述較為簡單的問題，要求學生對問題進行分析，找到一個合適的演算法，並推算出問題的解。考生給出的答案與標准答案相同，則得分；否則不得分。
3、程序閱讀理解題：共4題，每題8分，共計32分。題目給出一段程序（不一定有關於程序功能的說明），考生通過閱讀理解該段程序給出程序的輸出。輸出與標准答案一致，則得分；否則不得分。
4、程序完善題：共2題，每題14分，共計28分。題目給出一段關於程序功能的文字說明，然後給出一段程序代碼，在代碼中略去了若干個語句或語句的一部分並在這些位置給出空格，要求考生根據程序的功能說明和代碼的上下文，填出被略去的語句。填對則得分；否則不得分。
（二）復賽
復賽的題型和考試形式與NOI類似，全部為上機編程題，但難度比NOI低。每天3.5小時。普及組考一天，共4題，每題100分，共計400分；提高組考兩天，每天3題，共6題，每題100分，共計600分。每一試題包括：題目、問題描述、輸入輸出要求、樣例描述及相關說明。測試時，測試程序為每道題提供了5-10組測試數據，考生程序每答對一組得10－20分，累計分即為該道題的得分。
五、試題的知識范圍
（一）初賽內容與要求：
計 基 算 本 機 常 的 識
1．計算機和信息社會（信息社會的主要特徵、計算機的主要特徵、數字通信網路的主要特徵、數字化）
2．信息輸入輸出基本原理（信息交換環境、文字圖形多媒體信息的輸入輸出方式）
3．信息的表示與處理（信息編碼、微處理部件MPU、內存儲結構、指令，程序，和存儲程序原理、程序的三種基本控制結構）
4．信息的存儲、組織與管理（存儲介質、存儲器結構、文件管理、資料庫管理）
5．信息系統組成及互連網的基本知識（計算機構成原理、槽和埠的部件間可擴展互連方式、層次式的互連結構、互聯網路、TCP/IP協議、HTTP協議、WEB應用的主要方式和特點）
6．人機交互界面的基本概念（窗口系統、人和計算機交流信息的途徑（文本及交互操作））
7．信息技術的新發展、新特點、新應用等。
計 基 算 本 機 操 的 作
1. Windows和LINUX的基本操作知識
2. 互聯網的基本使用常識 （網上瀏覽、搜索和查詢等）
3. 常用的工具軟體使用（文字編輯、電子郵件收發等）
程序設計的基本知識數據結構
1．程序語言中基本數據類型(字元、整數、長整、浮點)
2. 浮點運算中的精度和數值比較
3．一維數組（串）與線性表
4．記錄類型（PASCAL）/ 結構類型（C）
程序設計
1．結構化程序設計的基本概念
2．閱讀理解程序的基本能力
3．具有將簡單問題抽象成適合計算機解決的模型的基本能力
4．具有針對模型設計簡單演算法的基本能力
5．程序流程描述（自然語言/偽碼/NS圖/其他）
6．程序設計語言（PASCAL/C/C++）
基本 演算法 處理
1．初等演算法（計數、統計、數學運算等）
2．排序演算法（冒泡法、插入排序、合並排序、快速排序）
3．查找（順序查找、二分法）
4．回溯演算法
（二）復賽內容與要求：
在初賽內容的基礎上增加以下內容：
數據結構
1．指針類型
2．多維數組
3．單鏈表及循環鏈表
4．二叉樹
5．文件操作（從文本文件中讀入數據，並輸出到文本文件中）
程序設計
1．演算法的實現能力
2．程序調試基本能力
3．設計測試數據的基本能力
4．程序的時間復雜度和空間復雜度的估計
演算法處理
1．離散數學知識的應用（如排列組合、簡單圖論、數理邏輯）
2．分治思想
3．模擬法
4．貪心法
5．簡單搜索演算法（深度優先 廣度優先）搜索中的剪枝
6．動態規劃的思想及基本演算法
⑺ noip需要准備哪些方面的基礎知識。復賽需要做哪些類型的題目（提高組）
Noip演算法（小超）
以下用n表示圖的點數，m表示邊數，k表示一個常數，log均以2為底數，存儲邊都採用邊表。
【模擬】
高精度加、減、乘，除應該不需要
表達式求值（中綴轉後綴，棧的操作）
【圖論】
圖的表示：鄰接矩陣，鄰接表，邊表
單源最短路：dijkstra（O(n2)），bellman（spfa優化，O(km)）
傳遞閉包和floyd
最小生成樹演算法：prim（O(n2)），kruskal（O(m log m)）
拓撲排序（O(m)）
歐拉路（邊一次）
漢密爾頓迴路（點一次）
強連通分量
匹配演算法（最大匹配，最小點覆蓋，最小路徑覆蓋，最大獨立集）
網路流演算法（最大流dinic，最小費用流spfa）
差分約束系統
【樹】
樹的先序、中序、後序遍歷
樹中的最長路（兩遍bfs）
特殊的樹：二叉樹
樹形動態規劃
並查集
字母樹
【搜索】
深搜，一般需要剪枝，有可行性剪枝和最優性剪枝兩種經常考。還有迭代深搜。
寬搜，雙向廣搜，估價函數。
【動態規劃】
背包問題：01背包，無限背包，多重背包，有依賴的背包，二維費用背包。（參照背包九講）
樹形動態規劃
狀態壓縮的動態規劃
最長不下降子序列
最長公共子序列和最長公共子串
動態規劃的優化（快速冪，改變狀態，優化轉移，單調性，四邊形不等式）
【貪心】
也有一些經典的模型，如取線段的問題，一般從小規模數據找規律，再適當的有一些證明。
【排序】
選擇排序、冒泡排序
快速排序（快排）、堆排序
插入排序
希爾排序
歸並排序
【分治】
二分查找
二分答案（這個好像不是分治）
【串】
串的基本操作
Kmp（字串匹配）
Kmp擴展
AC自動機
【數論】
歐幾里得演算法，最大公約數和最小公倍數
判斷質數（sqrt式與篩法求素數）
進制轉換
同餘定理
中國剩餘定理
概率與期望
歐拉函數
【幾何】
線段相交
凸包（水平序和極角序）
半平面交
【有序表】
順序表、鏈表、塊狀鏈表
線段樹及其基本操作
樹狀數組
平衡樹（sbt、treap、splay）
後綴數組
【其他】
Hash
隨機化演算法
矩形切割（與線段樹的比較）
Lca（最近公共祖先）與rmq（區間最值）
高斯消元
⑻ noi/noip 學習教材+內容+方法
我曾經也是一名OIer
Q&A:
1: 個人認為你手裡那本說比奧賽經典好。他們應該都是屬於講解題思路或演算法的吧。
2：我不認同你認識的那個人說的：語法幾乎不涉及。NOIP考察的主要是熟練度，怎麼可能和語法不涉及呢？NOIP屬於是一個推廣普及的比賽，也可以是說是NOI的鋪墊。演算法考得也是些比較基礎的。學PASCAL用什麼教材？我也忘了當初我的那本書名了，記得是藍色的似乎是南京什麼出版社。其實個人覺得語法這些東西，寫的都差不多。演算法的學習也沒什麼順便，你到NOI官網上去看NOIP的考試大綱。
如果你想通過OI來保送的話，你要注意你的年級。因為我記得13屆的將取消報送。對於NOIP來說，都是些基礎。首先你還是把語言弄熟，多練習題。做模擬題，練熟練程度。然後學習演算法，對於演算法這些也是多做題。在NOIP中演算法用的最多必學的應該算是動態規劃吧。在OJ上去做題，去討論討論，認識認識些OIer對你有幫助的。建議做USACO，網上也有翻譯的題目。那個題很不錯的。從第一節開始做。