当前位置:首页 >> 经济学 >>

NOIP2010提高组解题报告

NOIP2010 解题报告
Translate 开一个队列进行模拟就行了。 PS:这题数据比较厚道,按照题目的描述来说,单词的编号是非负整数, 也就是说可以是 0。但是数据中并没有 0,否则就要有很多人要降 10 分 了。 Tortoise 动态规划。 用 F[i1,i2,i3,i4]表示数字 1 的卡片取了 i1 张,数字 2 的卡片取了 i2 张, 数字 3 的卡片取了 i3 张,数字 4 的卡片取了 i4 张,可以取得最大的分 数。写起来很好写,四个 for,再加上四个 if。 F[i1,i2,i3,i4]=max(F[i1-1,i2,i3,i4],F[i1,i2-1,i3,i4],F[i1,i2, i3-1,i4],F[i1,i2,i3,i4-1])+score[1+i1+i2*2+i3*3+i4*4] PS:这题用 120*40*40*40,350*40*40*40 的算法都是可以的。 Prison 二分+二分图判定\并查集 解法 1:先二分答案,然后进行二分图的判定。判定方法如下:首先取 一个没有走过的结点放在了左图,然后把和这个点有边的点放在右图, 然后再把和这些右图有边的点放在左图,一直下去,知道把所有点都放 好,或者出现矛盾为止。 解法 2:把边权从大到小排一次序,依次插入。用并查集维护这些边之 间有没有矛盾。详情看并查集经典例题:PKU1182 食物链。 Flow

[(floodfill\动态规划\各种乱搞算法)+(贪心+动态规划\各种乱搞算法)]\最
短路

显然第一问一次 O(NM)的 floodfill 就可以求出是否可以到达全部最后一 层的格子。现在假设最后一行的所有格子都可以到达。 定理 1:从第一行的格子,可以到达的最后一行的格子必然是连续的一 段。 证明 1:假设格子 A 可以到达的最后一行中间有部分格子不可到达。由 题设可知,必有另一个格子 B 可以到达这些 A 不可到达的格子。但是, 显然 A 到达下面格子的路径必然与 B 到达这些 A 不可到达的格子的路 径有重合部分,所以,A 也能到达下面的 A 到达不了的格子。矛盾,所 以假设不成立,原命题成立。 定理 2:第一行从左到右的格子对应下面的格子区间的左边界和右边界 必然是单调不递减的。 证明 2:假设第一行有格子 A、B,并且 A 在 B 左边,最后一行有格子 C、D,并且 C 在 D 左边。假设 A 能到达 D 不能到达 C,B 能到达 C 不能到达 D。那么,A 到 D 和 B 到 C 的路径必然有重合的部分,所以 A 也能到达 C,B 也能到达 D。所以假设不成立,原命题成立。 定理 3:从任何一个格子出发,可以到达的最后一层格子也是连续。 证明 3:与定理 1 类似,略。 上面 3 个定理,可以得出一个大概的算法: 第一步:先把上面每一个格子对应的区间求出来; 第二步:然后再对这些区间进行操作。

第一步方法 1:枚举上面一层每个格子,进行 floodfill,把下面可以到 达的区间求出来。然后对于第一层每个格子,它需要枚举当且仅当它左 边和右边的格子都不能到达它。 第一步方法 2: fl[x,y]表示(x,y)能到达区间的左边界, fr[x,y]表示(x,y) 从 用 能到达区间的右边界。fl[x,y]:=min(fl[x1,y1]),fr[x,y]:=min(fr[x1,y1]), 条件是(x,y)可以走到(x1,y1)。转移顺序按照格子的海拔从小到大进行。 第二步方法 1:贪心。 第二步方法 2:动态规划。如果嫌时间多可以加上个单调队列去优化一 下。 事实上这题的瓶颈在于第 1 步,第一步方法 1 是 O(N^3)的,但是经过 试验,我在这题加上了若干常数优化后,A 掉了。详细的运行时间看下 面的图片。 新增一个最短路的方法:
NOIP2010 第四题引水入城最短路解法 这道题目可以说正统的解法是找区间,然后再进行贪心。而经过我的研究发现, 这题是可以用最短路来解决的!

首先,那样例作为说明:

首先,把每个格子当做一个点,然后如果格子 A 的水能流到格子 B,就从 A 到 B 连一条边

现在称这个图为 G。然后我们要构造一个 G`,就是把 G 所有边反向。下图为了后 面描述方便,就把 G`的 pic 进行上下翻转了一下。

然后,要构建主图 H。主图 H 有 M 个点:A1,A2,A3...Am+1,对于任意 1<=i<=m,

从 Ai+1 到 Ai 连一条边。注意:这里的连边是按照编号逆序的。然后把 G 和 G` 连到主图 H 上,G 图最下面一层第 i 个点连到 Ai+1 上,然后 Ai 连到 G`图最下面 一层第 i 个点。图如下(注:再说多一次,前一句的最下面一层是指对应原矩阵 的最下面一层的点,这里的 G`图为了绘画方便,把图像进行了上下翻转操作):

到目前为止,所有连到的边的权值都是 0。最后,从 G`图最上面一层第 i 个点连 一条权值为 1 的边到 G 图最上面一层第 i 个点。至此,图已建完:

现在, 点一共有 O(NM)条, 由于这是一个平面图, 边与点同阶。 所以边也有 O(NM) 条。 现在可以用 SPFA 或者 Dijkstra+Heap 解决。如果考虑此图的特殊性(边权只有 0 和 1),就可以采用最原始的 BFS 进行解决。 至此,这题可以完美地转换为一个简单的最短路特殊模型了。 PS:别问我建这个图的原理,想知道详情推导过程请参考 NOI2008 志愿者招募


相关文章:
NOIP2010提高组复赛试题及解题报告.doc
NOIP2010提高组复赛试题及解题报告 - NOIP2010 提高组复赛试题及解题报告 1.机器翻译 (translate.pas/c/cpp) 【问题描述】 小晨的电脑上安装了一个机器翻译软...
复赛NOIP2010提高组题解.doc
复赛NOIP2010提高组题解 - 1. translate(20 分) 简单模
NOIP2010提高组解题报告2.doc
NOIP2010提高组解题报告2 - 1. translate(20 分) 简单
NOIP2006和2010提高组复赛命题与解题报告.doc
NOIP2006和2010提高组复赛命题与解题报告 - NOIP2006 提高组复赛命题与解题报告 1.能量项链(energy.pas/c/cpp) .能量项链 【问题描述】 在 Mars 星...
NOIP2018提高组解题报告.doc
NOIP2018提高组解题报告_学科竞赛_高中教育_教育专区。第34届全国青少年信息学奥林匹克联赛NOIP2018提高组复赛解题报告此前的版本有少许笔误,已修订 ...
NOIP2009提高组解题报告.doc
xnhua2011贡献于2010-10-20 0.0分 (0人评价)暂无用户评价 我要评价 ...NOIP2009提高组解题报告NOIP2009提高组解题报告隐藏>> NOIp 2009 解题报告 November...
NOIP2010解题报告.doc
NOIP2010解题报告 - NOIP2010 解题报告 天津市南开中学 钱桥
Noip2010提高组初赛试题及详细解析(C语言).doc
Noip2010提高组初赛试题及详细解析(C语言) - 第十六届全国青少年信息学
备战NOIP2010提高组初赛复习问题求解篇.doc
备战NOIP2010 提高组初赛复习问题求解篇 问题求解是信息技术竞赛初赛中常见...NOIP2010复赛提高组题解... 8页 免费 NOIP2010提高组解题报告 6页 1下载...
NOIP2011提高组解题报告day1.doc
NOIP2011 提高组解题报告 day1 (2011-12-13 09:29:
noip2017提高组复赛解题报告.doc
noip2017 提高组复赛解题报告 定期推送帐号信息学新闻,竞赛自主招生,信息
NOIP2000-2009提高组解题报告.doc
swsp2009贡献于2010-11-06 0.0分 (0人评价)暂无用户评价 我要评价 ...收集整理NOIP2000-2009提高组解题报告收集整理NOIP2000-2009提高组解题报告隐藏>>...
NOIP2010提高组C参考答案.doc
NOIP2010提高组C参考答案 - CCF NOIP2010 提高组(C 语言
NOIP2010提高组C.doc
NOIP2010提高组C - 第十六届全国青少年信息学奥林匹克联赛初赛试题 (
Noip2010提高组初赛试题及答案(C语言).doc
("pause"); return 0; } CCF NOIP2010 提高组(C 语言)参考答案与评分标准 提高组( 语言) 一、单项选择题(共 10 题,每题 1.5 分,共计 15 分) 1 C ...
NOIP2010提高组C++.doc
NOIP2010提高组C++ - 第十六届全国青少年信息学奥林匹克联赛初赛试题
NOIP2011提高组解题报告day2.doc
NOIP2011提高组解题报告day2 - 计算系数 【问题描述】 给定一个多项
Noip2010提高组 第1题 translate 机器翻译.doc
Noip2010提高组 第1题 translate 机器翻译 - Noip2010 提高组 第 1 题 translate 机器翻译 【题意分析】 现在要翻译一段文章,于是需要查词典。而计算机拥...
Noip_2013_提高组_Day2_解题报告.doc
Noip_2013_提高组_Day2_解题报告 - 第二题:花匠(动态规划) 1
NOIP2007提高组复赛试题解题报告三.doc
NOIP2007提高组复赛试题解题报告三 - 4、【问题描述】 帅帅经常更同学玩