tceic.com
学霸学习网 这下你爽了
相关标签
当前位置:首页 >> 学科竞赛 >>

noip2010提高组解题报告


NOIP2010 解题报告(提高)
作者:张宇昊
所有见解仅供参考 考试时。。。发挥 1/3 已经不错了。。真 理。。! 考试结束。。觉得题都可做。。。
No1. 1.机器翻译 (translate.pas/c/cpp) 【问题描述】 小晨的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。 这个翻译软件的原理很简单,它只是从头到尾,依次将每个英文单词用对应的中文 含义 来替换。对于每个英文单词,软件会先在内存中查找这个单词的中文含义,如果内 存中有, 软件就会用它进行翻译;如果内存中没有,软件就会在外存中的词典内查找,查出 单词的中 文含义然后翻译,并将这个单词和译义放入内存,以备后续的查找和翻译。 假设内存中有 M 个单元, 每单元能存放一个单词和译义。 每当软件将一个新单词存 入 内存前,如果当前内存中已存入的单词数不超过 M?1,软件会将新单词存入一个未 使用的 内存单元;若内存中已存入 M 个单词,软件会清空最早进入内存的那个单词,腾出 单元来, 存放新单词。 假设一篇英语文章的长度为 N 个单词。给定这篇待译文章,翻译软件需要去外存查 找多

少次词典?假设在翻译开始前,内存中没有任何单词。 【输入】 输入文件名为 translate.in,输入文件共 2 行。每行中两个数之间用一个空格隔开。 第一行为两个正整数 M 和 N,代表内存容量和文章的长度。 第二行为 N 个非负整数,按照文章的顺序,每个数(大小不超过 1000)代表一个 英文 单词。文章中两个单词是同一个单词,当且仅当它们对应的非负整数相同。 【输出】 输出文件 translate.out 共 1 行,包含一个整数,为软件需要查词典的次数。 【输入输出样例 1】 translate.in translate.out 37 1215441 5 【输入输出样例 1 说明】 整个查字典过程如下: 每行表示一个单词的翻译,冒号前为本次翻译后的内存状况: 空:内存初始状态为空。 1. 1:查找单词 1 并调入内存。 2. 1 2:查找单词 2 并调入内存。 3. 1 2:在内存中找到单词 1。 4. 1 2 5:查找单词 5 并调入内存。 5. 2 5 4:查找单词 4 并调入内存替代单词 1。 6. 2 5 4:在内存中找到单词 4。 7. 5 4 1:查找单词 1 并调入内存替代单词 2。 共计查了 5 次词典。 全国信息学奥林匹克联赛(NOIP2010)复赛 提高组 第 3 页 共 7 页 【输入输出样例 2】

translate.in translate.out 2 10 8 824 11 78 11 78 11 78 8 264 6 【数据范围】 对于 10%的数据有 M=1,N≤ 5。 对于 100%的数据有 0

这题不用多说。 。 开个 1000 的队列, l,r 纪录队首, 队尾, 当 r-l>=m 时 inc(r)即可。 。 No.22.乌龟棋 (tortoise.pas/c/cpp) 【问题描述】 小明过生日的时候,爸爸送给他一副乌龟棋当作礼物。 乌龟棋的棋盘是一行 N 个格子,每个格子上一个分数(非负整数)。棋盘第 1 格 是唯一 的起点,第 N 格是终点,游戏要求玩家控制一个乌龟棋子从起点出发走到终点。 …… 1 2 3 4 5 …… N 乌龟棋中 M 张爬行卡片,分成 4 种不同的类型(M 张卡片中不一定包含所有 4 种 类型 的卡片,见样例),每种类型的卡片上分别标有 1、2、3、4 四个数字之一,表示 使用这种卡 片后,乌龟棋子将向前爬行相应的格子数。游戏中,玩家每次需要从所有的爬行卡 片中选择 一张之前没有使用过的爬行卡片,控制乌龟棋子前进相应的格子数,每张卡片只能 使用一次。 游戏中,乌龟棋子自动获得起点格子的分数, 并且在后续的爬行中每到达一个格子, 就得到 该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所 有格子的

分数总和。 很明显,用不同的爬行卡片使用顺序会使得最终游戏的得分不同,小明想要找到一 种卡 片使用顺序使得最终游戏得分最多。 现在,告诉你棋盘上每个格子的分数和所有的爬行卡片,你能告诉小明,他最多能 得到 多少分吗? 【输入】 输入文件名 tortoise.in。输入文件的每行中两个数之间用一个空格隔开。 第 1 行 2 个正整数 N 和 M,分别表示棋盘格子数和爬行卡片数。 第 2 行 N 个非负整数,a1, a2, ……, aN,其中 ai 表示棋盘第 i 个格子上的分数。 第 3 行 M 个整数,b1,b2, ……, bM,表示 M 张爬行卡片上的数字。 输入数据保证到达终点时刚好用光 M 张爬行卡片,即 N?1=ΣM

ib
1 。 【输出】 输出文件名 tortoise.out。 全国信息学奥林匹克联赛(NOIP2010)复赛 提高组 第 4 页 共 7 页 输出只有 1 行,1 个整数,表示小明最多能得到的分数。 【输入输出样例 1】 tortoise.in tortoise.out 95 6 10 14 2 8 8 18 5 17 13121 73 【输入输出样例 1 说明】

小明使用爬行卡片顺序为 1,1,3,1,2,得到的分数为 6+10+14+8+18+17=73。 注意, 由于起点是 1,所以自动获得第 1 格的分数 6。 【输入输出样例 2】 tortoise.in tortoise.out 13 8 4 96 10 64 55 13 94 53 5 24 89 8 30 11111241 455 【数据范围】 对于 30%的数据有 1 ≤ N≤ 30,1 ≤M≤ 12。 对于 50%的数据有 1 ≤ N≤ 120,1 ≤M≤ 50,且 4 种爬行卡片,每种卡片的张数不 会超 过 20。 对于 100%的数据有 1 ≤ N≤ 350,1 ≤M≤ 120,且 4 种爬行卡片,每种卡片的张 数不会 超过 40;0 ≤ ai ≤ 100,1 ≤ i ≤ N;1 ≤ __________bi ≤ 4,1 ≤ i ≤M。输入数据 保证 N?1=ΣM

ib
1 。 让我奔溃的就是这道题。。我么看到只有 4 种卡片。。知道后变得简单 开数组 f[i,a,b,c]{i 表示前 i 个,a 表示第一种卡片剩余数量 b 表示第二种 c-三,可 用计算公式(i-1-a-2b-3c}div 4 得出第四种卡片数量。} 于是 dp(动态规划)求解 f[i,a,b,c]= max{f[i-1,a+1,b,c],f[i-2,a,b+1,c],f[i-3,a,b,c+1], f[i-4,a,b,c]}+a[i]; 最后输出 f[n,0,0,0]即可 No3. 3.关押罪犯 (prison.pas/c/cpp)

【问题描述】 S 城现有两座监狱,一共关押着 N 名罪犯,编号分别为 1~N。他们之间的关系自 然也极 不和谐。很多罪犯之间甚至积怨已久,如果客观条件具备则随时可能爆发冲突。我 们用“怨 气值”(一个正整数值)来表示某两名罪犯之间的仇恨程度,怨气值越大,则这两名 罪犯之 间的积怨越多。如果两名怨气值为 c 的罪犯被关押在同一监狱,他们俩之间会发生 摩擦,并 造成影响力为 c 的冲突事件。 每年年末,警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列 表, 然后上报到 S 城 Z 市长那里。公务繁忙的 Z 市长只会去看列表中的第一个事件的 影响力, 如果影响很坏,他就会考虑撤换警察局长。 在详细考察了 N 名罪犯间的矛盾关系后,警察局长觉得压力巨大。他准备将罪犯们 在 两座监狱内重新分配, 以求产生的冲突事件影响力都较小,从而保住自己的乌纱帽。 假设只 要处于同一监狱内的某两个罪犯间有仇恨,那么他们一定会在每年的某个时候发生 摩擦。那 么,应如何分配罪犯,才能使 Z 市长看到的那个冲突事件的影响力最小?这个最小 值是多 全国信息学奥林匹克联赛(NOIP2010)复赛 提高组 第 5 页 共 7 页 少? 【输入】 输入文件名为 prison.in。输入文件的每行中两个数之间用一个空格隔开。 第一行为两个正整数 N 和 M,分别表示罪犯的数目以及存在仇恨的罪犯对数。 接下来的 M 行每行为三个正整数 aj, bj, cj, 表示 aj 号和 bj 号罪犯之间存在仇恨, 其怨

气值为 cj。数据保证 a b N j j 1 ≤ < ≤ ,0 < ≤ 1,000,000,000 j c ,且每对罪犯组 合只出现一 次。 【输出】 输出文件 prison.out 共 1 行,为 Z 市长看到的那个冲突事件的影响力。如果本年 内监狱 中未发生任何冲突事件,请输出 0。 【输入输出样例】 prison.in prison.out 46 1 4 2534 2 3 3512 1 2 28351 1 3 6618 2 4 1805 3 4 12884 3512 【输入输出样例说明】 罪犯之间的怨气值如下面左图所示,右图所示为罪犯的分配方法,市长看到的冲突 事件 影响力是 3512(由 2 号和 3 号罪犯引发)。其他任何分法都不会比这个分法更优。 【数据范围】 对于 30%的数据有 N≤ 15。 对于 70%的数据有 N≤ 2000,M≤ 50000。 对于 100%的数据有 N≤ 20000,M≤ 100000。

这道题也不是很难,听许多人说用二分答案,而我用的是贪心+并查集 。

首先贪心,每次取出最大的一组犯人。由于之后的所有事件影响都小于他,所以使 它不产生一定比其他状态优,所以尽量使它不发生。所以安排这组犯人 x,y 在两个 牢房.于是就将 y 的父亲赋值为 x,权值-1。 而其中用并查集做,压缩路径时,权值等于各边权值的积。而如果原来已经有 x,y 的关系,而又和现在要赋的矛盾,则 x,y 只能在一起,最严重的值即为 w[x,y]。 No.4 三 4.引水入城 (flow.pas/c/cpp) 【问题描述】 湖泊 沙漠 在一个遥远的国度,一侧是风景秀美的湖泊,另一侧则是漫无边际的沙漠。该国的 行政 区划十分特殊,刚好构成一个 N 行 M 列的矩形,如上图所示,其中每个格子都代 表一座城 市,每座城市都有一个海拔高度。 为了使居民们都尽可能饮用到清澈的湖水,现在要在某些城市建造水利设施。水利 设施 有两种,分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所 在城市的 蓄水池中。因此,只有与湖泊毗邻的第 1 行的城市可以建造蓄水厂。而输水站的功 能则是通 过输水管线利用高度落差,将湖水从高处向低处输送。故一座城市能建造输水站的 前提,是 存在比它海拔更高且拥有公共边的相邻城市,已经建有水利设施。 由于第 N 行的城市靠近沙漠,是该国的干旱区,所以要求其中的每座城市都建有水 利 设施。那么,这个要求能否满足呢?如果能,请计算最少建造几个蓄水厂;如果不 能,求干 旱区中不可能建有水利设施的城市数目。 【输入】 输入文件名为 flow.in。输入文件的每行中两个数之间用一个空格隔开。 输入的第一行是两个正整数 N 和 M,表示矩形的规模。

接下来 N 行,每行 M 个正整数,依次代表每座城市的海拔高度。 【输出】 输出文件名为 flow.out。 输出有两行。如果能满足要求,输出的第一行是整数 1,第二行是一个整数,代表 最少 建造几个蓄水厂;如果不能满足要求,输出的第一行是整数 0,第二行是一个整数, 代表有 几座干旱区中的城市不可能建有水利设施。 【输入输出样例 1】 flow.in flow.out 25 91543 87612 1 1 全国信息学奥林匹克联赛(NOIP2010)复赛 提高组 第 7 页 共 7 页 【样例 1 说明】 只需要在海拔为 9 的那座城市中建造蓄水厂,即可满足要求。 【输入输出样例 2】 flow.in flow.out 36 845644 734333 322112 1 3 【样例 2 说明】

湖泊 845644 734333 322112 沙漠 上图中,在 3 个粗线框出的城市中建造蓄水厂,可以满足要求。以这 3 个蓄水厂为 源头 在干旱区中建造的输水站分别用 3 种颜色标出。当然,建造方法可能不唯一。 【数据范围】 本题共有 10 个测试数据,每个数据的范围如下表所示: 测试数据编号能否满足要求 N M 1 不能 ≤ 10 ≤ 10 2 不能 ≤ 100 ≤ 100 3 不能 ≤ 500 ≤ 500 4 能 = 1 ≤ 10 5 能 ≤ 10 ≤ 10 6 能 ≤ 100 ≤ 20 7 能 ≤ 100 ≤ 50 8 能 ≤ 100 ≤ 100 9 能 ≤ 200 ≤ 200 10 能 ≤ 500 ≤ 500 对于所有的 10 个数据,每座城市的海拔高度都不超过 106。

第四题是最难的一道题。第一小问是简单的,最快可以 n^2 处理每个上面的点管辖 哪些下面的点,如果有 没有受管辖的点则输出-1 以及数量。若是都被管辖了,则 进入第二小问。 每个点可以管辖一些点,求管辖所有点的最小方案,这看似是一个指数级的问题, 也没有算法能处理,可是需要注意的是,这题有个特殊的地方,那就是每个第一行 的点管辖的最后一行的点一定是连续的

这是可以证明的。

这样问题就简单了,l[i],r[i]表示 i 管辖的最左端或最右端,1~m 枚举 i, f[r[i]]:=f[l[i]-1]+1,f[l[i]到 r[i]]都变成 f[l[i]-1]+1。 然后输出 f[m]就好了。。。。


推荐相关:

NOIP2010提高组解题报告

noip2010提高组解题报告 11页 免费 NOIP2011提高组复赛试题与... 13页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈...


NOIP2010提高组C++

欢迎访问 NOI 网站 CCF NOIP2010 初赛 提高组 C++ 2 7.关于拓扑排序,下面说法正确的是( )。 A. 所有连通的有向图都可以实现拓扑排序 B. 对同一个图而言,...


NOIP2010提高组解题报告2

Noip2010提高组试题 10页 免费 NOIP2010提高组解题报告 6页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...


2010noip提高组解题报告

noip2010提高组解题报告 11页 免费 NOIP2011 提高组 试题 Day... 4页 2财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进...


NOIP2010解题报告

解题报告 11页 免费 NOIP2010普及组个人解题... 9页 免费 全国信息学奥林匹克联赛... 6页 免费 NOIP2010提高组解题报告... 2页 免费 NOIP2010年提高组结题...


NOIP2010普及组解题报告

NOIP2010普及组解题报告_调查/报告_表格/模板_应用文书。NOIP2010 普及组解题报告时间:2011-09-14 10:39:27 来源:网络 作者:网络 首先前两题可以说非常水,第三...


NOIP2010年提高组结题报告

题目:[NOIP2010]关押罪犯 问题编号:600 题目描述 S 城现有两座监狱,一共关押...noip2009提高组解题报告... 10页 1下载券 NOIP2011提高组解题报告... 9页 ...


NOIP2010解题报告(附代码)

NOIP2010解题报告 3页 免费 NOIP2010提高组解题报告... 2页 免费 NOIP2010解题报告 15页 1下载券喜欢此文档的还喜欢 NOIP2010提高组解题报告 6页 免费 noip2010...


Noip2010提高组 第1题 translate 机器翻译

Noip2010 提高组 第 1 题 translate 机器翻译 【题意分析】 现在要翻译一段...NOIP2010年提高组结题报... 9页 免费 NOIP2010提高组解题报告... 2页 ...


NOIP2009提高组解题报告

xnhua2011贡献于2010-10-20 0.0分 (0人评价)暂无用户评价 我要评价 ...NOIP2009提高组解题报告NOIP2009提高组解题报告隐藏>> NOIp 2009 解题报告 November...

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