当前位置:首页 >> 学科竞赛 >>

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提高组复赛题解
2008noip提高组复赛题解_学科竞赛_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档2008noip提高组复赛题解_学科竞赛_高中教育_教育专区。NOIP2008 提高组...
NOIP2008提高组复赛试题及题解
NOIP2008提高组复赛试题题解_IT认证_资格考试/认证_教育专区。noip历届复赛试题及解析全国信息学奥林匹克联赛(NOIP2008)复赛 提高组一、题目概览中文题目名称 英文...
2009noip提高组复赛题解
2009noip提高组复赛题解_企业管理_经管营销_专业资料。NOIP2009 提高組複賽試題解題報告 NOIP2009 提高組複賽試題解題報告 一、潛伏者(spy) 問題描述: 給出密文及...
NOIP2008提高组解题报告
(2008-11-16 15:19:06) 标签: noip2008 复赛 提高组 普及组 twostack 第分类:编程经验 四题 noip 复测数据 能 AC 的题解: #include <string> #include...
2011noip提高组复赛题解
2011noip提高组复赛题解_学科竞赛_高中教育_教育专区。Noip 2011 提高组 (Day 1) 解题报告及程序 一、铺地毯 正着扫一遍 判断每个矩形是否覆盖询问的点,覆盖则...
NOIP2009提高组复赛题解
NOIP2009提高组复赛题解_IT/计算机_专业资料。NOIP2009提高组复赛题解 NOIP2009 提高组复赛题解(1) 2010-02-21 19:38 1. 潜伏者 (spy.pas/c/cpp) 【问题...
NOIP2008提高组复赛模拟试题
NOIP 2008 复赛模拟试题 (提高组) 全国青少年信息学奥林匹克 联赛复赛模拟试题...[1,n]为所求的解 时间复杂度:o(N^3); 此题需要选手对算法的时间复杂度...
NOIP2008提高组前三题解题报告
​2​0​0​8​提​高​组​前​三​题​解​题​报...NOIP2008 提高组复赛 解题思路 1、字符串中统计字母出现次数 最大减最小的 ...
NOIP2008提高组复赛试题
NOIP2008 提高组复赛试题 2008 年 12 月 06 日 星期六 16:54 全国信息学奥...NOIP2008_复赛试卷_提高... 6页 免费 NOIP2008提高组复赛题解 37页 免费 ...
noip2008普及组复赛试题(附题解)
noip2008普及组复赛试题(附题解)_IT/计算机_专业资料。NOIP2008的复赛试题(普及组)+题解 全国信息学奥林匹克联赛(NOIP2008)复赛 普及组 全国信息学奥林匹克联赛...
更多相关标签:
noip2008提高组复赛 | noip2016提高组复赛 | noip2015提高组复赛 | noip2014提高组复赛 | noip2010提高组复赛 | noip2012提高组复赛 | noip2013提高组复赛 | noip2011提高组复赛 |