Ø    复赛的命题
1．    准循大纲：考察常用的数据结构和基本算法；
2．    考察能力：包括阅读理解能力、构建数学模型的能力、程序编码与调试能力、程序的时空性能分析和测试数据的生成能力、各种知识的综合应用能力等；
3．    有区分度：一般3-4题，复赛题目的特点是：1-2题算法和数据结构比较明显、或者和数学关系比较大的题目，得率比较高；1题好上手，但程序量要大一点或数据规模大的题目，考虑全面、得满分也不容易；还有1题一般是搜索、或者算法不明显、或者用到复杂高深一点的数据结构的题目，难度较大。但顺序不一定！！！

Ø    如何备战复赛
1.    做做以往历年的竞赛题和网上的模拟题，熟悉比赛的题型和要求，找出自己的不
足，加强训练；
2.    增强自己编写代码和调试的熟练程度，提高做题的时间和节奏感；
3.    熟练掌握文件的输入/输出操作，新大纲中对复赛的要求；
4.    提高自己设计测试数据的能力；
5.    提高自己做题的正确率（分数/时间）；
6.    算法方面：递推、递归、动态规划、贪心、搜索（初中到回溯就差不多了）基本
上是必考！！！对一些经典问题和算法，一定要熟练的不能再熟练；
7.    数据结构方面：字符串经常考，树（尤其二叉树）、图的基本算法（最短路径、最
小生成树等）；

Ø    复赛注意事项
1.    1.认真审题，尤其要注意问题的规模（数据范围），从某种意义上说，问题规模也暗示了你可能的算法。数据小，也许是搜索派上用场的时候；数据大了，可能只能考虑动态规划，数学方法等高算法了。
2.    2.正确的估计题目的难度和自己的水平。拿到试题后先从总体上分析一下题目，做到心中有数！注意：题目的难易对所有人是公平的，只要最大限度地发挥自己的水平，不要有包袱，考出自己的最佳成绩。
3.    3.正确地选择题目去做（最擅长、最简单的先完成），合理地安排时间和解题顺序。
4.    4.复赛中：一定提高正确率！！！解题速度是其次。
5.    5.复赛考查的算法并不困难，选手在实现上的问题往往要多一些。建议大家：
1）    1)充分利用草稿纸，不要对自己的“心算能力”太自信！编程熟练的同学喜欢“一气呵成”，拿到题目就开始编码。我认为这样不好，做信息学竞赛题的思维过程是丰富而曲折多变的，考虑问题必须全面，仅凭一时的“感觉”来编程往往是漏洞百出。比如初学者常常忘记做一些初始化工作（远不止变量赋初值这种最简单的），即使有经验的同学也难免因一时疏忽写出几个错误的语句。最要命的是“第一感觉”的算法是错误的或者效率太低（命题者的陷阱），而程序编了大半才发现，时间浪费了不说，还影响了信心和发挥。
2）    2)做一些复杂的题目，编码采取自顶向下，逐步求精的方法，调试时采用输出中间结果的办法及时找出错误的地方。可以这么说，思路越清晰，对自己程序的算法和编码越了解，调试也会越顺利（一定不要忽视这一点）。
3）    3)多测试：样例数据、极限（小大）数据、特殊数据，分析能否在规定的时空范围内出解，精度是否够，格式是否对，输入输出文件名、格式是否正确等。
4）    4)不一定要拿满分，有些题目如果你很拿手，也肯定能做对，那么一定要保证拿满分；但有些题目，在有限的竞赛时间里，你很难拿满分，或者自己觉得没有足够的时间和信心，没有好的方法，那么在很少的时间内用投机取巧的方法（如贪心等）能得到不错的分数，也是一种很大的成功。

lways evilson历年复赛题目分布如下（1997年以来）
题目    名称    算法    参考难度
1997-c1    数矩形    数学（乘法原理）    *
1997-c2    数字三角形    穷举    *
1997-c3    数路径    递推（迭代）+加法原理+高精度    ***
1997-g1    素数方阵    递归回溯+构造    **
1997-g2    表达式判错    字符串+栈    **
1997-g3    骑士游历    宽搜+递推    **
1998-c1    1:2:3    穷举    *
1998-c2    S!    高精度    *
1998-c3    2的幂次方    递归+二进制    ***
1998-g1    上下车问题    递推或者枚举    *
1998-g2    连接多位数    贪心+字符串    **
1998-g3    加法表    递归+直接判断    ***
1999-c1    Cantor表    数学    *
1999-c2/g2    回文数    字符串    **
1999-c3/g3    旅行家的预算    贪心    ***
1999-g1    导弹拦截    动态规划、贪心    **
1999-g4    邮票面值设计    搜索+优化    ***
2000-c1    计算器的改良    字符串    *
2000-c2    税收与补贴问题    数学或穷举    **
2000-c3/g2    乘积最大    动态规划+高精度    ***
2000-c4/g3    单词接龙    回溯    **
2000-g1    进制转换    类比+穷举    **
2000-g4    方格取数    动态规划    ***
2001-c1    数的计数    递归或递推或动态规划    *
2001-c2    最大公约数与最小公倍数    穷举+优化+乘法原理    **
2001-c3    二叉树的先序序列    递归或穷举，构造    **
2001-c4    装箱问题    宽搜+hash表，或动态规划    ***
2001-g1    一元三次方程求解    穷举或随机化+迭代    **
2001-g2    数的划分    递推或动态规划    **
2001-g3    统计单词个数    贪心或随机化或动态规划    ***
2001-g4    Car的旅行路线    图论（Dijkstra算法）    ***
2002-c1    级数求和    高精度    *
2002-c2    选数    搜索（递归）    ***
2002-c3    产生数    乘法原理+图论    ***
2002-c4    过河卒    递推+加法原理+高精度    **
2002-g1    均分纸牌    数学    **
2002-g2    字串变换    广搜（双向）+剪枝    ***
2002-g3    自由落体    物理题    **
2002-g4    矩形覆盖    搜索（全国没有1人对）    *****
归纳：递推、动态规划、贪心、搜索、数学（物理）、图论、高精度、回溯、穷举、字符串

Ø    复赛试题分析

1.递推（2002年初中组4：过河卒）
[问题描述]
棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点，如图中的C点和P1，……，P8，卒不能通过对方马的控制点。棋盘用坐标表示，A点(0,0)、B点(n, m) (n,m为不超过20的整数),同样马的位置坐标是需要给出的，C≠A且C≠B。现在要求你计算出卒从A点能够到达B点的路径的条数。

[问题分析]
跳马是一道老得不能再老的题目，我想每位编程初学者都学过，可能是在学回溯或搜索等算法的时候，很多书上也有类似的题目，一些比赛中也出现过这一问题的变形（如NOIP1997初中组的第三题）。有些同学一看到这条题目就去搜索，即使你编程调试全通过了，运行时你也会发现：当n,m=15就会超时。
其实，本题稍加分析就能发现，要到达棋盘上的一个点，只能从左边过来（我们称之为左点）或是从上面过来（我们称之为上点），所以根据加法原理，到达某一点的路径数目，就等于到达其相邻的上点和左点的路径数目之和，因此我们可以使用逐列（或逐行）递推的方法来求出从起点到终点的路径数目。障碍点（马的控制点）也完全适用，只要将到达该点的路径数目设置为0即可。
用F[i,j]表示到达点(i,j)的路径数目，g[i,j]表示点(i, j)有无障碍，g[i,j]=0表示无障碍，g[i,j]=1表示有障碍。
则，递推关系式如下：
F[i,j] = F[i-1,j] + F[i,j-1]   {i>0且j>0且g[x, y] = 0}
递推边界有4个：
F[i,j] = 0                     { g[x,y] = 1 }
F[i,0] = F[i-1,0]              {i > 0且g[x,y] = 0}
F[0,j] = F[0,j-1]              {j > 0且g[x,y] = 0}
F[0,0] = 1
考虑到最大情况下：n=20,m=20，路径条数可能会超过MaxLongInt,所以要用高精度（使用Comp类型计数即可）。
程序：见文件夹。

例1、递推举例：储油点
[问题描述]
一辆重型卡车欲穿过1000公里的沙漠，卡车耗油为1升/公里，卡车总载油能力为500公升。显然卡车装一次油是过不了沙漠的。因此司机必须设法在沿途建立几个贮油点，使卡车能顺利穿越沙漠，试问司机如何建立这些贮油点？每一贮油点应存多少汽油，才能使卡车以消耗最少汽油的代价通过沙漠？
    编程计算及打印建立的贮油点序号，各贮油点距沙漠边沿出发的距离以及存油量。
          No．       distance(k．m．)           oil(litre)
          1              ××                    ××
          2              ××                    ××
          3              ××                    ××
[问题分析]
设dis[i]─第i个贮油点至终点(i=0)的距离；oil[i]─第i个贮油点的存贮油量。
    我们可以用倒推法来解决这个问题。从终点向始点倒推，逐一求出每个贮油点的位置及存油量。下图表示倒推时的返回点。
       终点                                                         始点
       └───────────┬──┬──────────────┬┘
i=0                    i=1    i=2 …                       …i=n
    从贮油点i向贮油点i+1倒推的策略是，卡车在点i和点i+1间往返若干次。卡车每次返回i+1处时正好耗尽500公升汽油，而每次从i+1处出发时又必须装足500公升汽油。两点之间的距离必须满足在耗油最少的条件下使i点贮足i*500公升汽油的要求(0≤i≤n-1)。具体地讲，第一个贮油点i=1应距终点i=0处500km且在该处贮藏500公升汽油，这样才能保证卡车能由i=1处到达终点i=0处，这就是说：dis[1]=500；oil[1]=500。为了在i=1处贮藏500公升汽油，卡车至少从i=2处开两趟满载油的车至i=1处。所以i=2处至少存贮2*500公升汽油，即oil[2]=500*2=1000。另外，再加上从i=1返回至i=2处的一趟空载，合计往返3次。三次往返路程的耗油量按最省要求只能为500公升，即d1,2 = km。
dis[2]=dis[1]+d1,2 =dis[1]+   

为了在i=2处贮存1000公升汽油，卡车至少从i=3处开三趟满载油的车至i=2处。 所以i=3处至少存贮3*500公升汽油，即oil[3]=500*3=1500。加上i=2至i=3处的二趟返程空车，合计5次。路途耗油量亦应500公升，即d2,3 = km。
    dis[3]=dis[2]+d2,3 =dis[2]+  

依次类推，为了在i=k处贮藏k*500公升汽油，卡车至少从i=k+1处开k趟满载车至i=k处， 即oil[k+1]=(k+1)*500=oil[k]+500，加上从i=k返回i=k+1的k-1趟返程空车，合计2*k-1次。这2*k-1次总耗油量按最省要求为500公升，即dk, k+1= km。
          dis[k+1]=dis[k]+dk,k+1
                  =dis[k]+   

最后， i=n至始点的距离为1000-dis[n]，oil[n]=500*n。为了在i=n处取得n*500公升汽油， 卡车至少从始点开n+1次满载车至i=n，加上从i=n返回始点的n趟返程空车，合计2*n+1次，2*n+1 趟的总耗油量应正好为(1000-dis[n])*(2*n+1)，即始点藏油为oil[n]+(1000-dis[n])*(2*n+1)。
由此得出如下的程序框架（程序略）：
begin
  k：=1；d：=500；                  { 从i=1处开始向始点倒推}
  dis[1]：=500；oil[1]：=500；
  repeat
    k：=k+1；d：=d+500/(2*k-1)；
    dis[k]：=d；
    oil[k]：=oil[k-1]+500；
  until d>=1000；
  dis[k]：=1000；                   {置始点至终点的距离值}
  d1：=1000-dis[k-1]；              {求贮油点k处至始点的距离}
  oil[k]：=d1*(2*k+1)+oil[k-1]；    {求始点藏油量}
for i：=0 to k do  输出第i个贮油点的距离为1000-dis[k-i]，藏油量为oil[k-i]；
end.
程序：见文件夹。

2. 动态规划（2000年初中组3/高中组2: 乘积最大）
[问题描述]  
今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：
设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。
同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：
有一个数字串：312， 当N=3，K=1时会有以下两种分法：
3*12=36
31*2=62
    这时，符合题目要求的结果是：31*2=62
    现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。
[输入]
   程序的输入共有两行：
   第一行共有2个自然数N，K（6≤N≤40，1≤K≤6）
   第二行是一个长度为N的数字串。
[输出]
   结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。
[样例输入]
4  2
1231
[样例输出]
62
[问题分析]
首先，由于问题的规模为6<=N<=40，1<=K<=6，要在长为N的数字串中插入K个乘号使得乘积最大，显然将会超出长整数的范围，所以运算要用高精度乘法。
其次，让我们考虑穷举的方法行不行，由组合数学知识知道：在长为N的数字串中插入K个乘号的方案有C（N-1,K）种，极限数据等于6500000种插入方案，而高精度本身也很费时间，所以穷举算法肯定会超时。看来只有找动态规划这样的高效算法了！！！
那么如何使用动态规划呢？分析发现：问题中只有乘号插入的位置是变化的，取数字串中的任意一段（P1到P2）来考虑，若能求出在其中插入K-1个乘号的最大乘积，则只需穷举第K个乘号的插入位置P（P从初始的P1+K-1开始插入，最多插入到P2-1后）。该乘号把数字串分成了两段，前半段包含K-1个乘号（其最大值已经算出），将它的值与后半段的值相乘得到第K个乘号在位置P时的最大乘积。打擂台选出P在各个位置时得到的最大乘积即为问题的解。
依此类推，把K-1的问题归结为K-2的情况，……，直到求在任意一段中插入1个乘号的最大乘积时，需预先算出在任意一段中插入0个乘号时的最大乘积。而此时的值是已知的（即为该段的数值）。假设C[p1,p2,K]表示在长为N的数字串中，从第p1个数字到第p2个数字之间插入K个乘号的最大乘积，动态转移方程如下：
                      p2-1
C[p1,p2,k] =   MAX  （C[p1,p,k-1] * C[p+1,p2,0]）
                         P=p1+k-1
假设输入的数字已保存在d[1..n]中（n<=maxn=40），定义三维数组max存放结果，即：
var max:array[1..maxn,1..maxn,0..maxn-1] of byte;其中max[i,j,0]到max[i,j,maxn-1]存放任意一段的最大乘积。则，动态规划的初始化工作如下：
for i:=1 to n-1 do
  for j:=i to n do
    begin
      for m:=0 to maxn-1  do  max[I,j,m]:=0;    {清0}
      w:=0;                                     {记录高精度数的有效位数}
      for m:=j downto I do begin                {高精度数的初始化}
                             max[I,j,w]:=d[m];
                             w:=w+1;
                           end;
end;

例2.动态规划举例（2001年高中3： 统计单词个数）
[问题描述]
给出一个长度不超过200的由小写英文字母组成的字母串（约定：该字串以每行20个字母的方式输入，且保证每行一定为20个）。要求将此字母串分成k份（1<k≤40）， 且每份中包含的单词个数加起来总数最大（每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可以包含this和is ，选用this 之后就不能包含th）。
单词在给出的一个不超过6个单词的字典中。要求输出最大的个数。
[输入格式]
输入数据放在文本文件input3.dat中,  其格式如下：
第一行有二个正整数：（p,k）
    p表示字串的行数；
    k表示分为k个部分。
接下来的 p行，每行均有20个字符。
再接下来有一个正整数s，表示字典中单词个数。（1≤s≤6）
接下来的s行，每行均有一个单词。
[输出格式]
结果输出至屏幕，每行一个整数，分别对应每组测试数据的相应结果。
[输入输出样例]  
输入：1   3
   t h i s i s a b o o k y o u a r e a o h
   4
   is
   a
   ok
   sab
输出：7
[问题分析]
首先,通过分析可以得出下面的结论:当给定的字符串中以同一个字母开头的单词有多个时,只须选用最短的一个,因为该单词受分段的影响最小,所以可以设数组shortest存储给定的字符串中所有位置上的最短单词的长度,shortest[i]=0表示给定的字符串中从第i个字符开始的一段不包含任何单词,否则表示从该位置起包含的最短的单词的长度。
另外，为了方便处理,可以将所有单词按从短到长的次序重新排序,并引入二维数组pos记录单词在给定的字符串中的分布情况,pos[i,j]=true表示在给定的字符串中从第i个字符开始包含第j个单词。
算法上可以从以下几个方面考虑：

不错,谢楼主.........

谢谢楼主
明天就要比赛了

我是菜鸟,这是哪儿来的?能告诉我吗?