tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

2008年noip提高组复赛题解


2008年noip
提高组试题讨论

2015/11/25

北京12中庄燕文

1、 笨小猴(word) 题意简述:给出一个单词,统计其中出现最多的字母 出现的次数maxn,以及出现最少的字母的次数minn, 如果maxn-minn是质数的话则作为一个Lucky Word..否则即为No Answer.

r />【解题分析】 1、读入字符串(文件) 2、构造一个数组,记录a-z各字符出现的次数。枚举字符串中 每个字符,将该字符对应数组元素加一。 3、枚举数组中a-z,找出最大值和非零最小值,求出它们的差。 4、判断差值是否为素数,数据规模很小,可用试除法。注意 0,1的特殊情况。 5、输出,注意大小写、换行符。
参考程序
2015/11/25 北京12中庄燕文

第二题 matches 题意简述: 给你n(n<=24)根火柴棒,叫你拼出 "A + B = C"这样的等式,求方案数.
【题目类型】搜索 【建议编程时间】30分钟。若某些问题未考虑到,调试20分钟。

【解题分析】 1、 读入整数n,减去加号和等号需要的4根火柴。 2、 采用搜索方法,先递归枚举火柴拆分成每个数字对应根数(存在数组里),再枚 举加号和等号的位置,计算对应的A,B,C,最后判断A+B=C,统计总数。 3、 输出tot,注意换行。 【编程注意】 1、 注意最高位不能为零,即除非该数为零,最高位不为零。 2、 递归函数两个入口,表示当前剩余火柴根数、当前位数。枚举下一根火柴的数字, 记录,递归(剩余-当前火柴,位数+1)。 3、 当剩余根数为零时,枚举A,B,C的拆分方式。 4、 计算A时,先将A设为首位,若首位为零且位数大于1,则失败退出(最高位不为零) 从首位+1到末位:A*=10, A+=a[i]. 字符串转为整数的常用方法。 5、 注意个数为0时的特殊处理。

参考程序

2015/11/25

北京12中庄燕文

第三题 message 题意简述: 给一个矩阵(左上角和右下角固定为0),从左 上角走两次到右下角,两次走的路径不能有交集(即一 个点不能被走两次),求两次走过的格子上的数的和最 大是多少.(类似二取方格数.) 解题思路: 二取方格数很经典的题目了,于是便直接以 f[i][j][k][p] 表示第一条路径走到(i,j),第二条路径走到 (k,p)所取到的数的最大值..转移方程就很好办了..同时 注意判断两条路不要从同一个点转移过来就好了.
参考程序
2015/11/25 北京12中庄燕文

双栈排序(twostack) i> 贪心的错误 这道题拿到手,很容易想到贪心。但我们可以举一反例证明: 251463 按照贪心策略这个序列不是双栈排序序列。但事实上这个序列是双栈排序序列。 问题出在4入栈时,按照贪心策略4将进入s1,但这样导致了6无法入栈。为了让 其成为双栈排序序列,我们让4进入s2。 ii> 在过程中调整贪心 由上面的例子可知,当我们遇到一个数无法进入队列时,我们要考虑两种情况: 其一是这个序列不是双栈排序序列;另外一种是前面贪心策略有误。 现在,我们要解决的问题就是如何判断前面贪心策略有误,有误的话怎样修正。 1调整是单向的 需要调整说明栈s1、s2的栈头元素都小于要入栈的数。只有将一个栈的末尾移至 另一栈末尾,才可能使要入栈的数得以进入。 2调整是从s1向s2的 所有元素入栈的第一选择便是进入s1,只有进入不了s1的才会进入s2。s1中的元 素相对在它后进栈的s2元素来说较小 3出栈元素不用考虑 4无法调整则说明这个序列不是双栈排序序列

2015/11/25

北京12中庄燕文

【题目类型】双线程动态规划 【建议编程时间】40分钟。这里的编程时间包括调试时间。 【空间复杂度】约27M,全局变量完全可承受。50*50*50*50*sizeof(int)=2.5*10^7. 【解题分析】 1、 读入矩阵,注意行列。 2、 采用一个四维数组记录当前两条路走到的位置(i1,j1,i2,j2)时取得的最大值,初始化为 0,表示不可能到达。(0,0,0,0)为1,最后减1输出。 3、 一个四重循环枚举两条路分别走到的位置。由于每个点均从上或左继承而来,故内部 有四个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]},表示两点均从 上面位置走来。 4、 输出右下角处的最大值f[m][n][m][n],注意换行。 【编程注意】 1、 在数组边界处特殊处理,避免数组越界。 2、 若待继承的点最大值为零,则停止判断,不能从这里走来。 3、 显然,非矩阵右下角的汇合点,两个位置不能重合(否则路径相交),若重合则最大 值为0,不可达。

2015/11/25 参考程序

北京12中庄燕文

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依次取出的),则取出该元素,最大元素自增,栈元素 个数自减。
2015/11/25 北京12中庄燕文

【正确解题分析】 这道题大概可以归结为如下题意: 有两个队列和两个栈,分别命名为队列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.如果可以,求出字典序最小的一个操作序列.

2015/11/25

北京12中庄燕文

这道题的错误做法很多,错误做法却能得满分的也很多, 这里就不多说了.直接切入正题,就是即将介绍的这个基 于二分图的算法. 注意到并没有说基于二分 图匹配,因为这个算法和二分图匹配无关.这个算法只是 用到了给一个图着色成二分图. 第一步需要解决的问题是,判断是否有解. 考虑对于任意两个数q1[i]和q1[j]来说,它们不能压入同 一个栈中的充要条件是什么(注意没有必要使它们同时 存在于同一个栈中,只是压入了同一个栈).实际上,这个 条件p是:存在一个k,使得i<j<k且q1[k]<q1[i]<q1[j].
2015/11/25 北京12中庄燕文

首先证明充分性,即如果满足条件p,那么这两个数一定不能压入同一 个栈.这个结论很显然,使用反证法可证. 假设这两个数压入了同一个栈,那么在压入q1[k]的时候栈内情况如 下:…q1[i]…q1[j]… 因为q1[k]比q1[i]和q1[j]都小,所以很显然,当q1[k]没有被弹出的时候, 另外两个数也都不能被弹出(否则q2中的数字顺序就不是1,2,3,…,n 了). 而之后,无论其它的数字在什么时候被弹出,q1[j]总是会在q1[i]之前弹 出.而q1[j]>q1[i],这显然是不正确的.
接下来证明必要性.也就是,如果两个数不可以压入同一个栈,那么它 们一定满足条件p.这里我们来证明它的逆否命题,也就是"如果不满 足条件p,那么这两个数一定可以压入同一个栈." 不满足条件p有两种情况:一种是对于任意i<j<k且 q1[i]<q1[j],q1[k]>q1[i];另一种是对于任意i<j,q1[i]>q1[j].
2015/11/25 北京12中庄燕文

第一种情况下,很显然,在q1[k]被压入栈的时候,q1[i]已经被弹出栈. 那么,q1[k]不会对q1[j]产生任何影响(这里可能有点乱,因为看起来, 当q1[j]<q1[k]的时候,是会有影响的,但实际上,这还需要另一个数r, 满足j<k<r且q1[r]<q1[j]<q1[k],也就是证明充分性的时候所说的情 况…而事实上我们现在并不考虑这个r,所以说q1[k]对q1[j]没有影 响). 第二种情况下,我们可以发现这其实就是一个降序序列,所以所有数 字都可以压入同一个栈. 这样,原命题的逆否命题得证,所以原命题得证. 此时,条件p为q1[i]和q1[j]不能压入同一个栈的充要条件也得 证.

2015/11/25

北京12中庄燕文

这样,我们对所有的数对(i,j)满足1<=i<j<=n,检查是否存在i<j<k满 足p1[k]<p1[i]<p1[j].如果存在,那么在点i和点j之间连一条无向边, 表示p1[i]和p1[j]不能压入同一个栈.此时想到了什么?那就是二分 图~ 二分图的两部分看作两个栈,因为二分图的同一部分内不会出现任 何连边,也就相当于不能压入同一个栈的所有结点都分到了两个栈 中. 此时我们只考虑检查是否有解,所以只要O(n)检查出这个图是不是 二分图,就可以得知是否有解.

2015/11/25

北京12中庄燕文

此时,检查有解的问题已经解决.接下来的问题是,如何找到字典序最小的解. 实际上,可以发现,如果把二分图染成1和2两种颜色,那么结点染色为1对应 当前结点被压入s1,为2对应被压入s2.为了字典序尽量小,我们希望让编号 小的结点优先压入s1. 又发现二分图的不同连通分量之间的染色是互不影响的,所以可以每次选取 一个未染色的编号最小的结点,将它染色为1并从它开始DFS染色,直到所有 结点都被染色为止.这样,我们就得到了每个结点应该压入哪个栈中.接下来 要做的,只不过是模拟之后输出序列啦~ 还有一点小问题,就是如果对于数对(i,j),都去枚举检查是否存在k使得 p1[k]<p1[i]<p1[j]的话,那么复杂度就升到了O(n^3).解决方法就是,首先预处 理出数组b,b[i]表示从p1[i]到p1[n]中的最小值.接下来,只需要枚举所有数对 (i,j),检查b[j+1]是否小于p1[i]且p1[i]是否小于p1[j]就可以了. 附代码(除去注释不到100行),带注释.代码中的a数组对应文中的队列p1. 已经过掉所有标准数据,以及5 7 2 4 1 6 3这组让很多贪心程序挂掉的数据~

2015/11/25

北京12中庄燕文


推荐相关:

2008noip提高组复赛题解

2008noip提高组复赛题解_学科竞赛_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档2008noip提高组复赛题解_学科竞赛_高中教育_教育专区。NOIP2008 提高组...


NOIP2008提高组复赛试题及题解

NOIP2008提高组复赛试题题解_IT认证_资格考试/认证_教育专区。noip历届复赛试题及解析全国信息学奥林匹克联赛(NOIP2008)复赛 提高组一、题目概览中文题目名称 英文...


NOIP2008提高组解题报告

(2008-11-16 15:19:06) 标签: noip2008 复赛 提高组 普及组 twostack 第分类:编程经验 四题 noip 复测数据 能 AC 的题解: #include <string> #include...


NOIP2008提高组复赛模拟试题

NOIP 2008 复赛模拟试题 (提高组) 全国青少年信息学奥林匹克 联赛复赛模拟试题...[1,n]为所求的解 时间复杂度:o(N^3); 此题需要选手对算法的时间复杂度...


2009noip提高组复赛题解

2009noip提高组复赛题解_企业管理_经管营销_专业资料。NOIP2009 提高組複賽試題解題報告 NOIP2009 提高組複賽試題解題報告 一、潛伏者(spy) 問題描述: 給出密文及...


2011noip提高组复赛题解

2011noip提高组复赛题解_学科竞赛_高中教育_教育专区。Noip 2011 提高组 (Day 1) 解题报告及程序 一、铺地毯 正着扫一遍 判断每个矩形是否覆盖询问的点,覆盖则...


NOIP2009提高组复赛题解

NOIP2009提高组复赛题解_IT/计算机_专业资料。NOIP2009提高组复赛题解 NOIP2009 提高组复赛题解(1) 2010-02-21 19:38 1. 潜伏者 (spy.pas/c/cpp) 【问题...


NOIP2008提高组前三题解题报告

​2​0​0​8​提​高​组​前​三​题​解​题​报...NOIP2008 提高组复赛 解题思路 1、字符串中统计字母出现次数 最大减最小的 ...


NOIP2009提高组复赛题解

NOIP2009提高组复赛题解_高考_高中教育_教育专区。noip历届复赛试题及解析1...NOIP2006提高组复赛解题... NOIP2007提高组解题报告 NOIP2008提高组复赛试题......


2008年NOIP联赛提高组初赛试题及答案

2008年NOIP联赛提高组初赛试题及答案_学科竞赛_高中教育_教育专区。本资料来自于...ABCD 三、问题求解:(共 2 题,每题 5 分,共计 10 分) 1.7 2.3060 ...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com