tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> 学科竞赛 >>

2008noip提高组复赛题解


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 分钟。 【解题分析】 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 时的特殊处理。

3.传纸条

【问题描述】 从 m*n 的矩阵中,只能向下、右两个方向走,找到两条互不相交的路径,使得两条路径上 的权值之和最大。 【题目类型】 双线程动态规划 【建议编程时间】 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,不可达。

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.如果可以,求出字典序 最小的一个操作序列. 这道题的错误做法很多,错误做法却能得满分的也很多,这里就不多说了.直接切入正题,就是 即将介绍的这个基于二分图的算法. 注意到并没有说基于二分图匹配,因为这个算法和二分图匹配无关.这个算法只是用到了给一 个图着色成二分图. 第一步需要解决的问题是,判断是否有解. 考虑对于任意两个数 q1[i]和 q1[j]来说,它们不能压入同一个栈中的充要条件是什么(注意没 有必要使它们同时存在于同一个栈中,只是压入了同一个栈).实际上,这个条件 p 是:存在一个 k,使得 i<j<k 且 q1[k]<q1[i]<q1[j]. 首先证明充分性,即如果满足条件 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]. 第一种情况下,很显然,在 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]不能压入同一个栈的充要条件也得证. 这样,我们对所有的数对(i,j)满足 1<=i<j<=n,检查是否存在 i<j<k 满足 p1[k]<p1[i]<p1[j].如果存 在,那么在点 i 和点 j 之间连一条无向边,表示 p1[i]和 p1[j]不能压入同一个栈.此时想到了什么? 那就是二分图~ 二分图的两部分看作两个栈,因为二分图的同一部分内不会出现任何连边,也就相当于不能压 入同一个栈的所有结点都分到了两个栈中. 此时我们只考虑检查是否有解,所以只要 O(n)检查出这个图是不是二分图,就可以得知是否有 解. 此时,检查有解的问题已经解决.接下来的问题是,如何找到字典序最小的解. 实际上,可以发现,如果把二分图染成 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 这组让很多贪心程序挂掉的数据~ #include <iostream> using namespace std; const int nn = 1002, mm = nn * 2, inf = 1000000000; int n, tot, now; int a[nn], b[nn], head[nn], color[nn]; int adj[mm], next[mm]; int stack[3][nn]; bool result; void addEdge(int x, int y) //加边 { ++ tot; adj[tot] = y; next[tot] = head[x]; head[x] = tot; } bool dfs(int i) //DFS 染色,检查图是否是二分图的经典算法

{ int temp = head[i]; while (temp) //邻接表,检查每一条边 { if (! color[adj[temp]]) //如果与当前结点的结点还未染色 { color[adj[temp]] = 3 - color[i]; //进行染色 dfs(adj[temp]); //DFS } if (color[adj[temp]] == color[i]) return false; //如果两个相邻结点染色相同,说明此图不是二分图,返回无解 temp = next[temp]; } return true; } int main() { freopen("twostack.in", "r", stdin); freopen("twostack.out", "w", stdout); //输入 scanf("%d", &n); for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]); //预处理 b 数组 b[n + 1] = inf; for (int i = n; i >= 1; -- i) b[i] = min(b[i + 1], a[i]); //"min" in STL //枚举数对(i,j)并加边 tot = 0; for (int i = 1; i <= n; ++ i) for (int j = i + 1; j <= n; ++ j) if (b[j + 1] < a[i] && a[i] < a[j]) { addEdge(i, j); addEdge(j, i); } //DFS 染色 memset(color, 0, sizeof(color)); result = true; for (int i = 1; i <= n; ++ i) //每次找当前未染色的编号最小的结点,并染颜色 1 if (! color[i]) //当前位置尚未被染色

{ color[i] = 1; if (! dfs(i)) //染色时出现矛盾,此时图不是一个二分图,即无法分配到两个栈中 { result = false; //记录无解 break; } } if (! result) //无解 printf("0"); else //有解 { //模拟求解 now = 1; for (int i = 1; i <= n; ++ i) { //将当前数字压入对应的栈 if (color[i] == 1) printf("a "); else printf("c "); stack[color[i]][0] ++; stack[color[i]][stack[color[i]][0]] = a[i]; //this will work even if stack[1][0] = 0 //循环检查,如果可以的话就从栈顶弹出元素 while (stack[1][stack[1][0]] == now || stack[2][stack[2][0]] == now) { if (stack[1][stack[1][0]] == now) { printf("b "); stack[1][0] --; } else if (stack[2][stack[2][0]] == now) { printf("d "); stack[2][0] --; } now ++; } } } 第四题上述程序转载自 www.oibh.org。

结语
以上四道题全部做完,需要约 140 分钟,距离三小时的时限还有 40 分钟,可以编一些 特殊的、极端的数据对程序进行测试。 这个阶段要做好源代码备份,除非发现重大问题,不要修改程序源代码,尤其在离终 场 10 分钟以内时,因为此时头脑紧张,极易改错。 这样下来,330 分不是大问题,在河北省就进入省队了。但是,很多平时成绩不错的大 牛考试时粗心大意, 丢分现象十分严重。 这次考试的题目很水, 更考察选手的细心认真程度。 真正的高手不仅会做难题,水题也能保证不出错。只有不出错,才能省队,因为第四题竞赛 时几乎没人想出正确解法;只有保证错误不足半道,才能一等奖,因为河北省一等奖分数线 是 280 分。实际上,对于如此普及组难度的水题,即使实力一般,也可能拿到不错的成绩。 希望 NOIP2008 成功的同学总结经验,再接再厉,创造更好的成绩;NOIP 失利的同学 不要气馁,总结教训,认真细致,下次再争取。


推荐相关:

2008noip提高组复赛题解.doc

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


NOIP2008 提高组 复赛试题.pdf

第 1 页共 6 页 全国信息学奥林匹克联赛(NOIP2008)复赛 提高组 1


2009noip提高组复赛题解.doc

2009noip提高组复赛题解_企业管理_经管营销_专业资料。NOIP2009


NOIP2008提高组复赛模拟试题.doc

NOIP2008提高组复赛模拟试题_IT认证_资格考试/认证_教育专区。NOIP 2008 复赛...[1,n]为所求的解 时间复杂度:o(N^3); 此题需要选手对算法的时间复杂度...


NOIP2008提高组前三题解题报告.doc

NOIP2008 提高组复赛 解题思路 1、字符串中统计字母出现次数 最大减最小的 ...了,那我就不在这里献丑了 好象是用二分图来做的,在 OIBH 上有详细的题解 ...


NOIP2010提高组复赛试题及解题报告.doc

NOIP2010提高组复赛试题及解题报告 - NOIP2010 提高组复赛试题及解题报告 1.机器翻译 (translate.pas/c/cpp) 【问题描述】 小晨的电脑上安装了一个机器翻译软...


NOIP2010复赛提高组题解加程序.pdf

NOIP2010复赛提高组题解加程序 - esiotrot o- ++g ml-


NOIP2008提高组复赛试题.doc

NOIP2008 提高组复赛试题 2008 年 12 月 06 日 星期六 16:54 全国信息学奥林匹克联赛(NOIP2008)复赛 提高组 一、题目概览 中文题目名称 英文题目名称 可执行...


NOIP2008提高组复赛试题.doc

NOIP2008提高组复赛试题 - 全国信息学奥林匹克联赛(NOIP2008)复


NOIP2008复赛提高组试题.doc

NOIP2008复赛提高组试题 - 全国信息学奥林匹克联赛(NOIP2008)复赛 提高组 一、题目概览 中文题目名称 英文题目名称 可执行文件名 输入文件名 输出文件名 每个测试...


NOIP2008 提高组试题.doc

NOIP2008复赛试题 提高组 8页 免费 Noip2010提高组试题 10页 免费 NOIP2009提高组复赛题解 12页 1财富值 NOIP2009高中复赛试题 7页 免费如要投诉违规内容,请到...


Noip 2013 提高组 解题报告.pdf

Noip 2013 提高组 解题报告_学科竞赛_高中教育_教育...第一题:转圈游戏(快速幂)根据题目, 答案明显是(x...NOIP2008提高组解题报告 13页 1下载券 NOIP2009提高...


NOIP2011提高组复赛DAY1解题报告.doc

NOIP2011提高组复赛DAY1解题报告 - NOIP2011DAY1 解题报


NOIP2011提高组复赛试题与简解(转载).doc

NOIP2011提高组复赛试题与简解(转载)_中考_初中教育_教育专区。NOIP2011提高组...威锋上果然有完全题解啊,第 14 关果然是样例啊有木有!!!人类智力威武, Orz...


2008NOIP初赛提高组试题.doc

2008NOIP初赛提高组试题 - 第十四届全国青少年信息学奥林匹克联赛初赛试题 ( 提高组 Pascal 语言 二小时完成 )●● 全部试题答案均要求写在答卷纸上,写在试卷纸...


IthneaNOIP2009提高组解题报告.doc

2009-12-04 08:56 A.M. | 回复 回复...: 首先,SPFA 的 k 已被证明...NOIP2009提高组复赛题解 12页 1下载券 Noip 2003 提高组 解题报... 12页...


NOIP2014提高组复赛试题.doc

NOIP2014提高组复赛试题 - CCF 全国信息学奥林匹克联赛(NOIP20


复赛NOIP2010提高组题解.doc

复赛NOIP2010提高组题解 - 1. translate(20 分) 简单模


2011noip提高组复赛题解.doc

2011noip提高组复赛题解_学科竞赛_高中教育_教育专区。Noip 2011


NOIP2009提高组复赛题解.doc

NOIP2009提高组复赛题解 - 1、潜伏者 program spy; var

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