当前位置:首页 >> 工作总结/汇报 >>

NOIP2010提高组解题报告2


1. translate(20 分) 简单模拟。开一个 1000 的队列,时刻保持队列长度不大于 M,每次接受翻译请 求时, 先在队列中查找, 查找失败则将单词加入队列。 查找使用 Hash 则为 O(N), 直接扫描 O(MN),都在可接受范围内。 考试时只打了 20 分,原因至今不明,告诫大家对于水题不要多想,就像这道题 最好不开 hash,因为一个系统的可靠度是该系统所有子系统可靠度之积,程序 越复杂越可能出错。

2. tortoise(50 分) 基础动规。可以从题目背景中抽象出这样的问题: 有一四维立方体(这里的立方体棱长不必相等,每一维对应一种卡片,每维的棱 长对应该种卡片个数) ,每走一格(即使用一张卡片)的收益是当前位置坐标的 ....... 函数。求从(0,0,0,0)走到(a1,a2,a3,a4)最大收益。 .. 故有方程 f[x,y,z,t]=max{ f[x-1,y,z,t], f[x,y-1,z,t], f[x,y,z-1,t], f[x,y,z,t-1] } + w[1 + x + y*2 + z*3 + t*4] 目标状态: f[a1,a2,a3,a4] O(b^4)的代价,数据保证 b<=40,完全满足要求

3. prison(70 分) 问题可以重新描述为:寻找最小的冲突值 c,使得存在一种方案,将原图分为两 部分,并去掉这两部分之间的所有边后,余下的边权都不大于 c。 对于这个问题我们可以二分查找 c,并判定其可行性。 判定可行性的方法至今没想好。考试的时候我是用并查集,将所有与 u 相连并与 u 之间边权大于 c 的点 (设为点集 Zu) 必然不与 u 在同一集合中, 枚举所有的 u, 每次将 Zu 合并成为一个集合,若存在某点 u 和 Zu 某个点处于同一个集合中,则 c 不可行,反之则可行。但这种方法貌似存在 bug,能拿 70 分。 如果把并查集合并查找的时间代价看作常数,则这种做法的时间代价为 O(elogK),e 是边数,K 为最大的冲突值。

4. flow(100 分)

1

先用 floodfill 预处理出上 个布尔矩阵, 行下标表示最上 矩阵对应点的值表示相应两 一题, 可以发现这道题是有贪 看作一个二分图 U-D 的压缩 U,下方与沙漠相邻的点集为 点入度为 0,则不存在合法的

2 3 4 5 U 6

方的每个格子能覆盖到下方的格子, 构造一 方的某个点,列下标表示最下方的某个点, 个点的覆盖关系。回想 BYTELAND 射击竞赛 心策略的。 为了描述方便, 这里把布尔矩阵 邻接矩阵, 其中最上方与水源相邻的点集为 D。 如果 DD 中某个 1 2 3 4 5 6 建立方式。 1 T T F F F F 1 2 F T F F F F 2 3 F T T T F F 3 4 F T T T T F 4 5 F F F F T F 5 6 F F F F T T 6

贪心策略: A. 每次选择 D 中入度最小的,设为 u。 B. 选择 U 集合中与 u 相连并且出度最大的点 v。 C. 在 v 处建立水源设施,并从二分图中删去 v 和与 v 相连的所有点、边。 D. 重复 ABC,直至 D 集合为空 可以证明,以这样的贪心策略构造的建立方式一定是最优的。 这样,floodfill 时间代价 O(NM^2)(可以通过记忆化优化至 O(NM),但不是很 必要),贪心部分最多执行 M 次,每次贪心需要扫描出入度表和布尔矩阵的一行 一列,时间代价 O(M^2),总的时间代价在立方级,勉强可以接受。

时间分配(可以看出很不合理) : translate : 5min tortoise : 110min prison : 10min flow : 30min 考试感言: NOIP’10 难度和去年相仿,思维量可能略大一些。去年缺席的动规今年回归, 表明动态规划仍是 NOIP 的重要考点。 1、2 两题杯具了,导致整套题分数拉低了不少,没进省队,有点遗憾。不过拿

1=走人也是个不错的选择。就当我是在 DP 吧,局部次优解导致了全局最优解。 这次我的时间分配不够合理。开始读题的时候把第二题当作多重背包了,所以打 算 30min 内刷完 1、2 两题。等到上手第二题的时候才发现思路不正确。然后我 的思路就被局限在了背包问题上,之后的三、四题的编码过程都是穿插在第二题 的思考过程中的。但是到最后也没想出来第二题的正解,反而耽误了很多检查时 间,最后剩 20min 的时候我才决定把第二题定型在 50 分程序上。这也间接导致 了我由于没时间出有技巧的测试数据而在第一题上栽跟头。 再说一句,写 DP 方程一定要查冗余状态,我做第二题的时候的最终思路类似正 解,但多加了一个冗余状态,即距出发点的距离 d。但显然 d=x+y*2+z*3+t*4, 这一维被其余四维唯一确定。虽然我用的是记忆化搜索,冗余的状态空间不影响 程序速度,但是多出的一维直接导致后 50 分内存溢出,只拿了一半分数。


相关文章:
noip2010提高组解题报告.doc
noip2010提高组解题报告_学科竞赛_高中教育_教育专区。noip2010提高组解题报告 ...【输入输出样例】 prison.in prison.out 46 1 4 2534 2 3 3512 1 2 ...
NOIP2010提高组复赛试题及解题报告.doc
NOIP2010提高组复赛试题及解题报告 - NOIP2010 提高组复赛试题及解题报告 1.机器翻译 (translate.pas/c/cpp) 【问题描述】 小晨的电脑上安装了一个机器翻译软...
NOIP2010提高组解题报告.doc
NOIP2010提高组解题报告 - 1:机器翻译 var m,n,i,j,k,p
NOIP2010复赛提高组题解加程序.pdf
NOIP2010复赛提高组题解加程序_IT认证_资格考试/认证_教育专区。esiotrot o- ...NOIP2010复赛提高组试题 7页 2下载券 NOIP2010提高组解题报告 6页 1下载券 ...
NOIP2010提高组解题报告.doc
提高组解题报告 NOIP2010 提高组解题报告 首先对这次比赛 做一个总体分析。第一题我觉得没什么好说的,作为一道简单 题还是挺简单的。第二题是动态规划,朴素的...
noip2010提高组解题报告.doc
Noip2010 反观 2010 年的提高组题目:第一题机器翻译是一道纯模拟的题目, 第二题乌龟棋 DP 类型 的题目,第三题实际上就是求最大值最小问题,最后一题难度高...
NOIP2011提高组解题报告day2.doc
NOIP2011提高组解题报告day2 - 计算系数 【问题描述】 给定一个多项
2010noip提高组解题报告.doc
2010noip提高组解题报告_IT/计算机_专业资料。2010noip提高组解题报告 带pascal源...(x+y)div 2].w; while i<=j begin while (i<=j) and (a[i].w>...
乌龟棋 (NOIP2010)复赛 提高组 试题二 解题代码.doc
乌龟棋 (NOIP2010)复赛 提高组 试题二 解题代码分类: C/C++ 解题代码 2011-07-23 18:56 271 人阅读 评论(2) 收藏 举报 view plaincopy to clipboardprint? ...
2011noip提高组解题报告.pdf
2011noip提高组解题报告 - 第一题很简单,用循环队列可做出。我当初为省时
NOIP2010解题报告.doc
NOIP2010解题报告 - NOIP2010 解题报告 天津市南开中学 钱桥 首先对这次比赛做一个总体分析。第一题我觉得没什么好说的,作为一道简单 题还是挺简单的。第二题是...
NOIP2010提高组试题.doc
(过滤行末空格及文末回车) 二.提交源程序文件名对于 pascal 语言 对于 C ...NOIP2010提高组解题报告 6页 免费 noip2010提高组PASCAL初... 11页 免费 ...
NOIP2010复赛提高组题解加程序.txt
(过滤行末空格及文末回车)题目类型 传统 传统 传统 传统 二.提交源程序文件名...NOIP2010提高组解题报告 6页 1下载券 NOIP2010提高组解题报告... 3页 免费...
NOIP2010提高组初赛试题答案C++.doc
国际信息学奥林匹克竞赛(IOI) NOIP2010 初赛 提高组 C++ 1 D
NOIP2010题解_图文.ppt
NOIP2010题解 - NOIP2010提高组 NOIP2010提高组 题目分
NOIP2009提高组复赛题解.doc
NOIP2009 提高组复赛题解(2) 2010-02-21 19:57 2. Hankson 的趣味题 (...复赛NOIP2009提高 19页 免费 NOIP2009提高组解题报告 16页 免费 noip...
Noip2010提高组初赛试题及答案(C语言).doc
} CCF NOIP2010 提高组(C 语言)参考答案与评分标准 提高组( 语
NOIP2010初赛提高组试题及答案(Pascal).doc
第十六届全国青少年信息学奥林匹克联赛初赛试题试题及答案 NOIP2010(Pascal 提高组) ( 提高组)一、单项选择题 1.与 16 进制数 A1.2 等值的 10 进制数是 ()...
NOIP2006和2010提高组复赛命题与解题报告.doc
NOIP2006和2010提高组复赛命题与解题报告 - NOIP2006 提高组复赛命题与解题报告 1.能量项链(energy.pas/c/cpp) .能量项链 【问题描述】 在 Mars 星...
Noip2010提高组试题.doc
Noip2010提高组试题 - 全国信息学奥林匹克联赛(NOIP2010)复赛
更多相关标签: