on the way
« 一月 2009
星期日星期一星期二星期三星期四星期五星期六
    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
       
今天
全部分类 | General | Status | Java | Music | Politics

20071113 Tuesday 2007年11月13日

NOIP复赛谈

 
 
Ø       复赛的命题
1．  准循大纲：考察常用的数据结构和基本算法；
2．  考察能力：包括阅读理解能力、构建数学模型的能力、程序编码与调试能力、程序的时空性能分析和测试数据的生成能力、各种知识的综合应用能力等；
3．  有区分度：一般3-4题，复赛题目的特点是：1-2题算法和数据结构比较明显、或者和数学关系比较大的题目，得率比较高；1题好上手，但程序量要大一点或数据规模大的题目，考虑全面、得满分也不容易；还有1题一般是搜索、或者算法不明显、或者用到复杂高深一点的数据结构的题目，难度较大。但顺序不一定！！！
 
Ø       如何备战复赛
1.       做做以往历年的竞赛题和网上的模拟题，熟悉比赛的题型和要求，找出自己的不
足，加强训练；
2.       增强自己编写代码和调试的熟练程度，提高做题的时间和节奏感；
3.       熟练掌握文件的输入/输出操作，新大纲中对复赛的要求；
4.       提高自己设计测试数据的能力；
5.       提高自己做题的正确率（分数/时间）；
6.       算法方面：递推、递归、动态规划、贪心、搜索（初中到回溯就差不多了）基本
上是必考！！！对一些经典问题和算法，一定要熟练的不能再熟练；
7.         数据结构方面：字符串经常考，树（尤其二叉树）、图的基本算法（最短路径、最
小生成树等）；
 
Ø       复赛注意事项
1.              认真审题，尤其要注意问题的规模（数据范围），从某种意义上说，问题规模也暗示了你可能的算法。数据小，也许是搜索派上用场的时候；数据大了，可能只能考虑动态规划，数学方法等高算法了。
2.              正确的估计题目的难度和自己的水平。拿到试题后先从总体上分析一下题目，做到心中有数！注意：题目的难易对所有人是公平的，只要最大限度地发挥自己的水平，不要有包袱，考出自己的最佳成绩。
3.              正确地选择题目去做（最擅长、最简单的先完成），合理地安排时间和解题顺序。
4.              复赛中：一定提高正确率！！！解题速度是其次。
5.              复赛考查的算法并不困难，选手在实现上的问题往往要多一些。建议大家：
1）  充分利用草稿纸，不要对自己的“心算能力”太自信！编程熟练的同学喜欢“一气呵成”，拿到题目就开始编码。我认为这样不好，做信息学竞赛题的思维过程是丰富而曲折多变的，考虑问题必须全面，仅凭一时的“感觉”来编程往往是漏洞百出。比如初学者常常忘记做一些初始化工作（远不止变量赋初值这种最简单的），即使有经验的同学也难免因一时疏忽写出几个错误的语句。最要命的是“第一感觉”的算法是错误的或者效率太低（命题者的陷阱），而程序编了大半才发现，时间浪费了不说，还影响了信心和发挥。
2）  做一些复杂的题目，编码采取自顶向下，逐步求精的方法，调试时采用输出中间结果的办法及时找出错误的地方。可以这么说，思路越清晰，对自己程序的算法和编码越了解，调试也会越顺利（一定不要忽视这一点）。
3）  多测试：样例数据、极限（小大）数据、特殊数据，分析能否在规定的时空范围内出解，精度是否够，格式是否对，输入输出文件名、格式是否正确等。
4）  不一定要拿满分，有些题目如果你很拿手，也肯定能做对，那么一定要保证拿满分；但有些题目，在有限的竞赛时间里，你很难拿满分，或者自己觉得没有足够的时间和信心，没有好的方法，那么在很少的时间内用投机取巧的方法（如贪心等）能得到不错的分数，也是一种很大的成功。
 
Ø       历年复赛题目分布如下（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个单词。
算法上可以从以下几个方面考虑：
1、贪心法
毎次根据数组shortest选定一个分段位置使得被截断的最短单词最少,将这些被截断的最短单词从数组shortest中去除,重复上述过程,直到将给定的字符串分成k段为止；
2、随机化算法
用随机的方法将给定的字符串分成k段,统计毎一段中包含的单词数,全部段包含的单词总数即为问题的一个解,多次随机直到限定时间用完为止,此时输出最优解；
3、结合以上两种方法；
4、动态规划
substr(b,e)表示给定字符串中从第b个字符到第e个字符为止的子串,用数组most记录给定字符串中从第一个字符到任意一个字符为止的子串被分成i段后包含的最多单词数,如most[i,t]表示子串substr(1,t)分成i段后包含的最多单词数,则most[i+1,j]=max(most[i,t]+maxword(substr(t+1,j))),t=i..j-1,其中maxword为求某字符串中最多单词的函数,程序中没有用二维数组,去掉了第一维,递推时下标要从大往小推,类似于杨辉三角用一维数组递推。
程序：见文件夹。
 
3. 字符串（1998年高中组2： 连接多位数）
[问题描述]
设有n个正整数（n≤20），将它们联接成一排，组成一个最大的多位整数。
例如：n=3时，3个整数13，312，343联接成的最大整数为：34331213
又如：n=4时，4个整数7，13，4，246联接成的最大整数为：7424613
程序输入：n
           n个数
程序输出：联接成的多位数
[问题分析]
举例说明正常的字符串比较缺陷！如：A=’321’，B=’32’，按照标准的字符串比较规则因为A>B，所以A+B > B+A ，而实际上’32132’< ’32321’。
所以，自定义一种字符串的比较规则：即如果A+B>B+A,则我们认为A>B。且可以证明：如果A+B>=B+A,B+C>=C+B,则一定有：A+C>=C+A。
    这样一来，程序就很简单了。分3步，先把n个数字转换成字符串存储；再按照自定义的规则把n个字符串排序；最后按照从大到小的顺序输出这些字符串。
    小结：有些问题看起来是数学问题，认真分析会发现用字符串处理很简单。另外，一定要掌握有关字符串的各种函数，以免用到时自己编子程序。
    程序：略。
 
4.贪心（删数问题）
[问题描述]
键盘输入一个高精度的正整数n（小于等于240位），去掉其中任意s个数字后，剩下的数字按原次序将组成一个新的正整数。编程对给定的n和s，寻找一种方案，使得剩下的数字组成的新数最小。
[输入格式]
   n
       s
[输出格式]
   顺序列出s个被删去的数字。
[算法分析]
    首先，这是一个高精度数。但是否一定用数组存放这个数呢？这要看具体的算法实现。由于正整数n的有效数位为240位，因此我们采用字符串类型存贮n。
为了尽可能逼近目标，我们的“贪心策略”是：每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序搜索，若各位数字递增，则删最大（最后）的数字；否则删第一个递减区间的首字符，这样便形成了一个新数串。然后回到串首，按上述规则删下一个数字，……，依次类推，直到删除了s个数字为止，输出剩余部分即可。
例如：n=‘1 7 8 5 4 3’        s=4
删数过程如下：
          n=‘1 7 8 5 4 3’        删‘8’ 
            ‘1 7 5 4 3’          删‘7’
            ‘1 5 4 3’            删‘5’
            ‘1 4 3’              删‘4’
‘1 3’
这样删数问题与“如何寻找递减区间首字符”这样一个简单的问题对应起来。按贪心策略编制的程序框架为：
begin
输入n,s；
    while s>0 do
      begin
        i：=1；    {从串首开始找}
        while (i<length(n)) and (n[i]<=n[i+1]) do  i:=i+1；
        delete (n，i，1)；   {删除字符串n的第i个字符}
s:=s-1；
      end；
    while (length(n)>1)and (n[1]=‘0’) do delete(n，1，1)；  {删去串首的无用零}
    输出n；
  end.
    程序：略。
 
例3、贪心举例：取数游戏
[问题描述]
给出2*n个自然数。游戏双方分别为A方（计算机方）和B方（对奕的人）。只允许从数列两头取数。A先取，然后双方依次轮流取数。取完时，谁取得的数字总和最大为取胜方；双方和相等，属于A胜。试问A方可否有必胜的策略
[输入] 2*n个自然数
[输出]
前2*n行为游戏经过。每两行分别为A方所取的数和B方所取的数，其中B方取数时应给予提示，让游戏者选择取哪一头的数（L/R—左端或右端）。最后一行分别为A方取得的数和和B方取得的数和。
[问题分析]
设自然数列:7  9  3  6  4  2  5  3
我们设计一种方案，从数大的一头让A、B轮流取两个连续数：
A方：7   3   4   5
B方：9   6   2   3
由此得出：
       A方取得的数和为7+3+4+5=19
       B方取得的数和为9+6+2+3=20
按照规则，判定A方输。虽然A方败给B方，但是我们却发现了一个有趣的事实：A方取走偶位置的数后，剩下两端数都处于奇位置；反之，若A方取走奇位置的数后，剩下两端数都处于偶位置。即无论B方如何取法，A方即可以取走奇位置的所有数，亦可以取走偶位置的所有数。由此萌发一种“贪心策略”：让A方取走“数和较大的奇（或偶）位置上的所有数”，则A方必胜。这样，取数问题便对应于一个简单问题：让A方取奇偶位置中数和较大的一半数。设j为A取数的奇偶位置标志，则：
     
    设SA，SB分别表示A方取数和，B方取数和（SA≥SB）；a存储2*n个自然数序列；lp，rp为序列的左端位置和右端位置；ch为B方取数的位置信息（’L’或’R’）；则，程序框架如下：
begin
SA：=0；SB：=0；     {计算A方取数和、B方取数和，A方取数的位置标志}
    for i：=1 to n do
      begin
        SA：=SA+a[2*i-1]；SB：=SB+a[2*i]；
      end；
if SA>=SB then j:=1
              else begin j:=0；交换SA和SB；end；
    lp：=1；rp：=2*n；
    for i：=1 to n do                {A方和B方依次进行n次对奕}
      begin
        if ((j=1) and (lp mod 2=1)) or ((j=0)and (lp mod 2=0))
{若A方应取奇位置数且左端位置为奇，
或者A方应取偶位置数且左端位置为偶，
则A方取走左端位置的数}
        then begin 输出A方取a[lp]；lp：=lp+1；end
        else begin 输出A方取a[rp]；rp：=rp-1；end；{否则A方取走右端位置的数}
输出提示信息：B方的取数位置（L/R）；
        repeat
          读ch；
          if ch=‘L’ then begin  输出B方取a[lp]；lp：=lp+1；end；
          if ch=‘R’ then begin  输出B方取a[rp]；rp：=rp-1；end；
        until ch {‘L’，’R’}；
      end；
输出A方取数的和SA和B方取数的和SB；
end.
    程序：略。
 
5．穷举（2000年高中组1：进制转换）
[问题描述] 
我们可以用这样的方式来表示一个十进制数： 将每个阿拉伯数字乘以一个以该数字所处位置的（值减１）为指数，以１０为底数的幂之和的形式。例如：１２３可表示为１＊１０２＋２＊１０１＋３＊１００这样的形式。
     与之相似的，对二进制数来说，也可表示成每个二进制数码乘以一个以该数字所处位置的（值－１）为指数，以２为底数的幂之和的形式。一般说来，任何一个正整数Ｒ或一个负整数－Ｒ都可以被选来作为一个数制系统的基数。如果是以Ｒ或－Ｒ为基数，则需要用到的数码为０，１，．．．．Ｒ－１。例如，当Ｒ＝７时，所需用到的数码是０，１，２，３，４，５和６，这与其是Ｒ或－Ｒ无关。如果作为基数的数绝对值超过１０，则为了表示这些数码，通常使用英文字母来表示那些大于９的数码。例如对１６进制数来说，用Ａ表示１０，用Ｂ表示１１，用Ｃ表示１２，用Ｄ表示１３，用Ｅ表示１４，用Ｆ表示１５。
在负进制数中是用－Ｒ作为基数，例如－１５（十进制）相当于１１０００１（－２进制），并且它可以被表示为２的幂级数的和数：
   110001＝1*（-2）５ + 1*（-2）４ + 0*（-2）３ + 0*（-2）２ + 0*（-2）１ + 1*（-2）０
[问题求解]
设计一个程序，读入一个十进制数和一个负进制数的基数, 并将此十进制数转换为此负进制下的数：     －Ｒ∈｛－２，－３，－４，．．．，－２０｝　
[输入]
    输入的每行有两个输入数据。
    第一个是十进制数Ｎ（－32768＜＝Ｎ＜＝32767）；  第二个是负进制数的基数－Ｒ。
[输出]
结果显示在屏幕上，相对于输入，应输出此负进制数及其基数，若此基数超过１０，则参照１６进制的方式处理。
[样例输入]
３００００　－２
－２００００　－２
２８８００　－１６
－２５０００　－１６
[样例输出]
３００００＝１１０１１０１０１０１１１００００（ｂａｓｅ　－２）
－２００００＝１１１１０１１０００１０００００　（ｂａｓｅ　－２）
２８０００＝１９１８０　　　（ｂａｓｅ　－１６）
－２５０００＝７ＦＢ８　　　（ｂａｓｅ　－１６）
[问题分析]
其实，本题拿到手的第一个想法是进制转换的常规方法“除R取余，除尽为止，倒取输出”，但当你用一个样例去试的时候，发现毫无规律（如果有的人习惯不好，拿到手自以为是，不喜欢用草稿纸，则会沿着死路往前走）。
其实，分析一下问题的规模N（注意这是第1题），-32767-32768！！！穷举。对任一个-R进制数k(从0开始)，计算它对应的十进制数是多少，如果等于N，则输出这个-R进制数，否则继续找下一个-R进制数。
思考：-R进制数好象没有符号位哎：）
程序：见文件夹。
 
6．简单搜索、回溯（1999年高中组4：邮票面值设计）
[问题描述] 
给定一个信封，最多只允许粘贴N张邮票，计算在给定K（N+K≤40）种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值MAX，使在1～MAX之间的每一个邮资值都能得到。
    例如，N=3，K=2，如果面值分别为1分、4分，则在1分～6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）；如果面值分别为1分、3分，则在1分～7分之间的每一个邮资值都能得到。可以验证当N=3，K=2时，7分就是可以得到的连续的邮资最大值，所以MAX=7，面值分别为1分、3分。
    样例输入与输出：
    INPUT                   OUTPUT
    N=3  K=2                 1  3
                             MAX=7
[问题分析]
首先，看数据规模n+k<=40，显然很大，所以有的选手想用动态规划，但注意本题具有明显的后效性（前面方案的不同使得构成某面值的邮票数不同），所以不满足动态规划的条件。
那么，解决这类问题只能用递归搜索了。但很快有人发现：搜索所能解决的问题规模远远达不到题目的要求，一般搜索到n,k同时超过6，就不行了。而实际的测试数据也就到n=10,k=5,且n+k<13。
所以，我们总结出分区联赛的题目难易程度，其实和数据规模（尤其是实际测试数据）息息相关。有的题目很难，但实际的测试数据很简单（小）；而有的题目算法和思想很简单，但数据规模巨大。如果题目难度大且测试数据很刁钻、很大，那么得分率就会极低，这时就相当于去掉这一题比赛（比如2002高中组的矩形覆盖问题）。这种题目这几年基本上是用搜索！所以，选手做题时应充分估计4个题目的难度和命题人的命题动机。对难度小的、有把握的要拿满分；对于难度大，但小数据能很容易算出的要把该拿的分拿住；对于自己能力以外的，不要浪费宝贵的时间（记住：评奖的原则是名次，而不是分数和哪一条题目）。
回到原题中来，首先面值为1的邮票是必须的；此后每加进一种面值都要把当前所能取得的金额记下来。通过k-1次添加得到一种方案。穷举所有的方案得到最优解。
在搜索的过程中，对数据的记录方式很关键。如果仅仅记录一个金额能否被达到，则这样的记录基本上没有用，因为下一次添加邮票时，不知能否从这个金额出发再加上新邮票，推导出达到哪些新面值，必须全部重算，浪费了大量时间；所以，我们记录最少要用几张邮票达到一个面值，这样有利于添加新邮票时迅速判断可行性。
搜索一种新邮票面值的起点（即新邮票的选择策略）应该是：从上一个面值加1开始，直到当前连续取得的最大金额加1。因为过大会造成不连续，过小得不到最优解。
程序：见文件夹。
 
7．搜索+剪枝优化+构造（1997年高中组1：素数方阵）
[问题描述]
在N*N的棋盘上（1≤N≤10），填入1，2，…，N*N共N*N个数，使得任意两个相邻的数之和为素数。

其相邻数的和为素数的有：
1+2，1+4，4+3，2+3
   例如：当N=2时，有：

1
2
4
3
         当N=4时，一种可以填写的方案如下：
 1
2
11
12
16
15
8
5
13
4
9
14
6
7
10
3
    在这里我们约定：左上角的格子里必须填数字1。
    程序要求：
        输入：N；
        输出：如有多种解，则输出第一行、第一列之和为最小的排列方案；若无解，则输出“NO！”。
[问题分析]
由于素数的变换是没有规律的，本题只能搜。因为N的值是从1到10的之间的任意一个自然数，每个方格中的数字不相同，所以采用递归回溯的方法实现。具体讲，就是将所有方格编一个次序，根据“如有多种解，则输出第一行、第一列之和为最小的排列方案“这句话，填数的顺序应是先填第一行第一列（1），以后选择填入的数应该从小到大依次选择，首先选一个2到N*N之间的自然数填入第一行第二列，要求填入的数与已填的相邻方格中的数之和为素数；然后再用相同的方法填第一行的第三列到第N列，填完第一行后，再依次填第一列中的第二行到第N行。依此类推，再填第二行的第二列到第N列，再填第二列的第三行到第N行，……，直到右下角最后一个数填好为止（再按要求输出）。
在填数的过程中有几个要求：一要保证填入的数没用过（很简单，设一个used[1..n*n]，值为布尔型）；二是当前格子选不到数填时要回溯，……，直到所有情况都搜索到了（回溯的控制）；三是判断填入的数是否合法（类似于N皇后问题的判断合法性）。
对于第三个问题，如果每填入一个数，都要判断它与上方和左方的格子中的数之和是否为素数，效率会很低。所以想到了用构造（查表）法判断素数。因为任意一个格子的最大数为N*N，所以相邻两个格子的数之和最大为2N*N。即把1到2N*N中的素数求出来保存好（200以内的素数太简单了），然后每次判断只要查表了。
小结：1.素数总是一奇一偶的和，所以，行列上肯定是奇数偶数相隔的，优化？
      2.如果去掉a[1,1]=1这个约定，则发现：只有当a[1,1]中填奇数时问题才有可能有解，为什么？因为1..n*n个数中奇数的个数一定大于等于偶数的个数，再结合1。
      3.求所有解及总数。
程序：见文件夹。
发表于 dayu ( 2007年11月13日, 08:31:10 AM CST ) Permalink 评论 [0]

20071024 Wednesday 2007年10月24日

初赛题

10. 一位艺术史学家有20000 幅1024 * 768 的真彩色图像，如果将这些图像以位图形式保存
在CD 光盘上（一张CD 光盘的容量按600M计算），大约需要（ ）张CD光盘。
A. 1 B. 10 C. 100 D. 1000 E. 10000


<7> 为了便于处理表达式，常常将普通表达式（称为中缀表示）转换为前缀{运算符在前，如X/Y写为/XY}
和后缀 { 运算符在后，如X/Y写为XY/}的表达形式。
在这样的表示中可以不用括号即可确定求值的顺序，如：
          （P+Q）*（R-S）→*+PQ-RS 或  →  PQ + RS -*
① 试将下面的表达式改写成前缀与后缀的表示形式：
　　<A>  A+B*C/D            <B>  A-C*D+B∧E
　　② 试将下面的前缀表示还原成中缀的表示形式，同时写出后缀表示：
　　+△A *B△C {前缀式中△表示一元运算符取负号，如△A表示（-A）}
设数组A[10..100,20..100] 以行优先的方式顺序存储，每个元素占4个字节，且已知A[10，20]的地址为1000，则A[50，90]的地址是 
一个向量第一个元素的存储地址是100，每个元素的长度是2，则地5个元素的地址是（  ）。
A）110  B）108  C）100  D）109
15．已知A = 35H，A /\ 05H \/ A /\ 30H 的结果是：（  ）。
A）30H  B）05H  C）35H  D）53H

17．按照二叉数的定义，具有3个结点的二叉树有（  ）种。
    A）3  B）4  C）5  D）6
4.满二叉树的叶结点个数为N，则它的结点总数为（  ）。
A. N   B. 2 * N   C. 2 * N – 1   D. 2 * N + 1   E. 2N – 1


20．设栈S和队列Q的初始状态为空，元素e 1 ，e 2 ，e 3 ，e 4 ，e 5 ，e 6依次通过栈S，一个元素出栈后即进入队列Q，若出队的顺序为e 2 ，e 4 ，e 3 ，e 6 ，e 5 ，e 1 ，则栈S的容量至少应该为（  ）。
    A）2  B）3  C）4  D）5
设有一棵k叉树，其中只有度为0和k两种结点，设n 0 ，n k ，分别表示度为0和度为k的结点个数，试求出n 0 和n k之间的关系（n 0 = 数学表达式，数学表达式仅含n k 、k和数字）。
在 Pascal 语言中，表达式  (21 xor 2)的值是（      ）
 
A. 441       B. 42       C.23      D.24       E.25
4. 完全二叉树的结点个数为4 * N + 3，则它的叶结点个数为（ ）。
A. 2 * N B. 2 * N - 1 C. 2 * N + 1 D. 2 * N - 2 E. 2 * N + 2
13. 二叉树T的宽度优先遍历序列为A B C D E F G H I，已知A是C的父结点，D 是G 的
父结点，F 是I 的父结点，树中所有结点的最大深度为3（根结点深度设为0），可知E
的父结点可能是（ ）（多）。
A. A B. B C. C D. D E. F

14. 设栈S的初始状态为空，元素a, b, c, d, e, f, g依次入栈，以下出栈序列不可能出现的有
（ ）。（多）
A. a, b, c, e, d, f, g B. b, c, a, f, e, g, d C. a, e, c, b, d, f, g
D. d, c, f, e, b, a, g E. g, e, f, d, c, b, a

发表于 dayu ( 2007年10月24日, 11:14:17 AM CST ) Permalink 评论 [0]

题

1、    计算ex，lnx。X=1，2，3…..10

2、    计算ex，lnx。X=1.1，1.2，1.3…..2.0

3、    计算10个数的和、平均值、积

4、    输入n，计算n的阶乘(n!)

5、    计算1！，2！….20!

6、    求两个数的最大公约数和最小公倍数

7、    输入字母a、b….z，反序输出

8、    求菲波拉切数

发表于 dayu ( 2007年10月24日, 11:13:23 AM CST ) Permalink 评论 [0]

jinming

const m=40;
type yu= array[1..m] of integer;
     yu1=array[1..4,1..m] of integer;
var
v,w,q:yu;
e,i,j,k,t,n,l:integer;
f:array[0..40,0..80]of longint;
p,v1:yu1;

{function fla(var r:yu;f:integer):boolean;
var
flag:boolean;
i:integer;
begin
flag:=true;
for i:=1 to 40 do
if (r[i]=f) then begin flag:=false; break;end;
fla:=flag;
end;}
begin
readln(t,n);
for i:=1 to n do

readln(v[i],w[i],q[i]);

i:=1;
j:=1;
while i<=n do
begin
if q[i]=0 then  begin v1[j][1]:=v[i];p[j][1]:=v[i]*w[i]; inc(j); end
else begin e:=q[i]; v1[e][2]:=v[e]+v[i];v1[e][3]:=v[e]+v[i+1];v1[e][4]:=v[e]+v[i]+v[i+1];
           p[e][2]:=v[e]*w[e]+v[i]*w[i];p[e][3]:=v[e]*w[e]+v[i+1]*w[i+1];p[e][4]:=v[e]*w[e]+v[i]*w[i]+v[i+1]*w[i+1];
           inc(i);
           end ;
           inc(i);
end;
for i:=1 to t do
f[0][i]:=0;
for i:=1 to j-1 do

 for l:=0 to t do
  for k:=1 to 4 do


 begin

   if (l>v1[i][k]) and ((f[i-1][l-v1[i][k]]+p[i][k])>f[i-1][l]) then begin

                                                       f[i][l]:=(f[i-1][l-v1[i][k]]+p[i][k]);

                                                       end
   else f[i][l]:=f[i-1][l];
   end;
   writeln(f[j-1][t]);
   for i:=1 to j-1 do
    for l:=1 to 4 do
    writeln(p[i][l]);
end.

发表于 dayu ( 2007年10月24日, 11:12:00 AM CST ) Permalink 评论 [0]

金明的预算方案 明的预算方案

(budget.pas/c/cpp)

【问题描述】

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：

主件

附件

电脑

打印机，扫描仪

书柜

图书

书桌

台灯，文具

工作椅

无

如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：

v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。（其中*为乘号）

请你帮助金明设计一个满足要求的购物单。

【输入文件】

输入文件budget.in 的第1行，为两个正整数，用一个空格隔开：

N m

（其中N（<32000）表示总钱数，m（<60）为希望购买物品的个数。）

从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数

v p q

（其中v表示该物品的价格（v<10000），p表示该物品的重要度（1~5），q表示该物品是主件还是附件。如果q=0，表示该物品为主件，如果q>0，表示该物品为附件，q是所属主件的编号）

【输出文件】

输出文件budget.out只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<200000）。

【输入样例】

1000 5

800 2 0

400 5 1

300 5 1

400 3 0

500 2 0

【输出样例】

2200

发表于 dayu ( 2007年10月24日, 11:11:22 AM CST ) Permalink 评论 [0]

算法实例－关于旅行者的背包问题

算法实例－关于旅行者的背包问题

基本问题：

0/1背包问题中，需要对容量为C的背包进行装载。从N个物品中选取装入背包的物品，每件物品I的重复为W(I)，价值为P(I)。如何装入价值最大的物品？

算法：

贪心准则1－从剩余的物品中找出一个可以装入背包的价值最大的物品。

贪心准则2－从剩余的物品中找出可以装入背包的重量最小的物品。

贪心准则3－计算价值密度P(I)/W(I)。从剩余的物品中选择可装入包的P/W(I) 物品。

贪心算法之K阶优化－从答案中取出K件物品，并放入另外K件，获得的结果不会比原来的差。这样优化整个放入物品的序列。

动态规划－用递归进行计算求解。每一步求出基于现在状况下的最优解。（特点－计算复杂）

回溯算法－首先形成一个递归算法，去找到可获得的最大收益。即列出所有的候选解，然后依次检查每一个，在检查完所有或部分候选解后，即可找出所需要的解。（特点－候选解数量庞大）

变形问题：

·货郎的背包

·野外生存者的背包

·公司经理（？）的背包。

发表于 dayu ( 2007年10月24日, 11:08:09 AM CST ) Permalink 评论 [0]

©下落的石头