NOIP2008提高组解题报告.docVIP

NOIP2008提高组解题报告石家庄二中 李博杰1.笨小猴【问题描述】输入一个由小写字母构成的字符串,统计出现最多与最少字母的个数,若两数之差为质数,输出Lucky Word和差值;否则输出No Answer和0.【题目类型】模拟【建议编程时间】10分钟(细心一些,避免出错).【解题分析】1,读入字符串(文件)2,构造一个数组,记录a-z各字符出现的次数.枚举字符串中每个字符,将该字符对应数组元素加一.3,枚举数组中a-z,找出最大值和非零最小值,求出它们的差.4,判断差值是否为素数,数据规模很小,可用试除法.注意0,1的特殊情况.5,输出,注意大小写,换行符.2.火柴棒等式【问题描述】给n根火柴棒,问能拼出多少种形如A+B=C的等式.【题目类型】有哪些信誉好的足球投注网站【建议编程时间】30分钟.若某些问题未考虑到,调试20分钟.【解题分析】读入整数n,减去加号和等号需要的4根火柴.采用有哪些信誉好的足球投注网站方法,先递归枚举火柴拆分成每个数字对应根数(存在数组里),再枚举加号和等号的位置,计算对应的A,B,C,最后判断A+B=C,统计总数.输出tot,注意换行.【编程注意】注意最高位不能为零,即除非该数为零,最高位不为零.递归函数两个入口,表示当前剩余火柴根数,当前位数.枚举下一根火柴的数字,记录,递归(剩余-当前火柴,位数+1).当剩余根数为零时,枚举A,B,C的拆分方式.计算A时,先将A设为首位,若首位为零且位数大于1,则失败退出(最高位不为零)从首位+1到末位:A*=10, A+=a[i]. 字符串转为整数的常用方法.注意个数为0时的特殊处理.3.传纸条【问题描述】从m*n的矩阵中,只能向下,右两个方向走,找到两条互不相交的路径,使得两条路径上的权值之和最大.【题目类型】双线程动态规划【建议编程时间】40分钟.这里的编程时间包括调试时间.【空间复杂度】约27M,全局变量完全可承受.50*50*50*50*sizeof(int)=2.5*10^7.【解题分析】读入矩阵,注意行列.采用一个四维数组记录当前两条路走到的位置(i1,j1,i2,j2)时取得的最大值,初始化为0,表示不可能到达.(0,0,0,0)为1,最后减1输出.一个四重循环枚举两条路分别走到的位置.由于每个点均从上或左继承而来,故内部有四个if,分别表示两个点从上上,上左,左上,左左继承来时,加上当前两个点所取得的最大值.例如,f[i][j][k][l] = max{f[i][j][k][l], f[i-1][j][k-1][l] + a[i][j] + a[k][l]},表示两点均从上面位置走来.输出右下角处的最大值f[m][n][m][n],注意换行.【编程注意】在数组边界处特殊处理,避免数组越界.若待继承的点最大值为零,则停止判断,不能从这里走来.显然,非矩阵右下角的汇合点,两个位置不能重合(否则路径相交),若重合则最大值为0,不可达.4.双栈排序【问题描述】通过两个栈S1,S2,将一个给定的输入序列升序排列.定义a操作将元素压入S1栈,b操作从S1栈中取出栈顶元素,c操作将元素压入S2栈,d操作从S2栈中取出栈顶元素.求字典序最小的操作序列.【建议编程时间】贪心算法40分钟(包括调试),可得30分.【解题分析】(贪心算法,30分)1,读入序列2,若能进入S1栈,则执行a操作,进入S1栈;重复执行b操作,将S1栈中当前元素弹出,直到不可行为止.3,若能进入S2栈(c),并将S2中符合要求的元素弹出(d),直到不可行.4,若两栈均无法进入,失败退出5,输出操作序列【判断是否能进栈】若当前元素小于栈顶元素,则进栈,栈元素个数自增;否则不能进栈.因为栈中必须保持降序,这样才能保证依次输出时升序.【判断是否能出栈】用全局变量表示当前取出的最大元素.若栈内元素个数不为零,且当前栈顶元素等于最大元素+1(因为元素是1-n依次取出的),则取出该元素,最大元素自增,栈元素个数自减.【正确解题分析】(转载,感谢提供解题方法的大牛)这道题大概可以归结为如下题意:有两个队列和两个栈,分别命名为队列1(q1),队列2(q2),栈1(s1)和栈2(s2).最初的时候,q2,s1和s2都为空,而q1中有n个数(n=1000),为1~n的某个排列.现在支持如下四种操作:a操作,将 q1的首元素提取出并加入s1的栈顶.b操作,将s1的栈顶元素弹出并加入q1的队列尾.c操作,将 q1的首元素提取出并加入s2的栈顶.d操作,将s2的栈顶元素弹出并加入q1的队列尾.请判断,是否可以经过一系列操作之后,使得q2中依次存储着1,2,3,…,n.如果可以,求出字典序最小的一个操作序列.这道