⑴ 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，网上也有翻译的题目。那个题很不错的。从第一节开始做。