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

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提高组解题报告 NOIP2010 解题报告(提高) 作者:张宇昊所有见解仅供参考 考试时。。。发挥 1/3 已经...
NOIP2010提高组复赛试题及解题报告.doc
NOIP2010提高组复赛试题及解题报告 - NOIP2010 提高组复赛试题及解题报告 1.机器翻译 (translate.pas/c/cpp) 【问题描述】 小晨的电脑上安装了一个机器翻译软...
noip2010提高组解题报告.doc
noip2010提高组解题报告_IT/计算机_专业资料。我只能算是归纳,有些代码
NOIP2010提高组解题报告.doc
NOIP2010提高组解题报告 - 1:机器翻译 var m,n,i,j,k,p
NOIP2010提高组解题报告1.doc
NOIP2010提高组解题报告1_其它_总结/汇报_实用文档。解题报告 【NOI
NOIP2010提高组解题报告2.doc
NOIP2010提高组解题报告2 - 1. translate(20 分) 简单
NOIP2010复赛提高组题解加程序.pdf
NOIP2010复赛提高组题解加程序 - esiotrot o- ++g ml-
2010noip提高组解题报告.doc
2010noip提高组解题报告_IT/计算机_专业资料。2010noip提高组解题报告 带pascal源程序 第一题很简单,用循环队列可做出。我当初为省时间,开了十万的数组,没用循环,...
NOIP2010解题报告.doc
NOIP2010解题报告 - NOIP2010 解题报告 天津市南开中学 钱桥
NOIP2010复赛提高组题解加程序.txt
全国信息学奥林匹克联赛(NOIP2010)复赛 提高组第 1 页共 7 页全国信息学奥...NOIP2009提高组复赛题解 12页 1下载券 NOIP2010提高组解题报告 6页 免费 ...
Noip2010提高组初赛试题及答案(C语言).doc
Noip2010提高组初赛试题及答案(C语言)_初一数学_数学_初中教育_教育专
NOIP2010第16届初赛提高组P试题和答案.doc
NOIP2010第16届初赛提高组P试题和答案 - 第十六届全国青少年信息学奥林匹克联赛初赛试题 (提高组 Pascal 语言 两小时完成) ●● 全部试题答案均要求写在答卷纸上...
NOIP2010提高组初赛试题_C++含答案.doc
NOIP2010提高组初赛试题_C++含答案 - 第十六届全国青少年信息学奥林匹
noip2010提高组PASCAL初赛试题(解析).doc
第十六届全国青少年信息学奥林匹克联赛初赛试题试题及答案 NOIP2010(Pascal 提高组)一、单项选择题 1.与 16 进制数 A1.2 等值的 10 进制数是 () A.101.2 ...
NOIP2010题解_图文.ppt
NOIP2010题解 - NOIP2010提高组 NOIP2010提高组 题目分
Noip2010提高组试题.doc
Noip2010提高组试题 - 全国信息学奥林匹克联赛(NOIP2010)复赛
全国信息学奥林匹克联赛(NOIP2010)复赛_普及组_解题报....doc
全国信息学奥林匹克联赛(NOIP2010)复赛 普及组解题报告 1.数字统计 (
NOIP2006和2010提高组复赛命题与解题报告.doc
NOIP2006和2010提高组复赛命题与解题报告 - NOIP2006 提高组复赛命题与解题报告 1.能量项链(energy.pas/c/cpp) .能量项链 【问题描述】 在 Mars 星...
Noip2010提高组初赛试题及答案(C语言).doc
(); return 0; } 输入: 5 13579 4 2 6 10 14 输出: CCF NOIP2010 提高组(C 语言)参考答案与评分标准 提高组( 语言)一、单项选择题(共 10 题,每题...
NOIP2010普及组解题报告.doc
NOIP2010普及组解题报告_调查/报告_表格/模板_应用文书。NOIP2010 普及组解题报告时间:2011-09-14 10:39:27 来源:网络 作者:网络 首先前两题可以说非常水,第三...
更多相关标签: