当前位置:首页 >> 学科竞赛 >> 冲刺NOIP2011长乐一中day1解题报告

冲刺NOIP2011长乐一中day1解题报告


题1

骑士守卫

这是第一题,比较水。 容易想到做 BFS,先做骑士的 BFS,算出城堡被骑士走到的最短时间 min, 然后从每个入侵者出发做一次 BFS,判断他能不能到城堡,但是这样的理论复杂 度是 O(knm),k 是入侵者个数。 当然我们可以进行优化,不用从每个入侵者出发做一次 BFS,改从城堡出发 做 BFS,算出每个入侵者最迟什

么时候出发时间能顺利进入城堡, (城堡的位置 的最迟出发时间为 min-1,因为这个时刻还不走就会被发现) ,如果某个入侵者 的最迟出发时间大于等于 0,那他就可以进入城堡,否则就算他一开始就走也不 可以) 。这样做的时间复杂度就是 O(nm),不会超时了。 既然是第一题,就有可能更水,只要你想清楚。 我们做 BFS 的目的除了判断入侵者会不会在城堡被发现, 还判断了会不会在 途中被发现。 这题的骑士是向四边同时扩展的,也就是说如果某个入侵者会在途 中被发现, 那么他到达城堡的最短时间一定大于等于城堡被骑士走到的最短时间 min。 所以我们直接枚举每个骑士,算出他和城堡的曼哈顿距离,取最小,即上面 的 min。 然后枚举每个入侵者,再算和城堡的曼哈顿距离,直接判断即可。

题2

信任链

本题一般的想法开一个 f[i]的数组,代表以第 i 个人为结尾的信任链的最长 长度。 显然:f[i]=max{f[j]+1}, j<I,I % p[j]=0。 这样的状态为 O(N),转移代价为 O(N),所以总的时间复杂度为 O(N^2)。对 于题目给的 N=100000,压力还是很大的。 仔细想一下就会发现:对于两个相同的 P,它能推到的状态是相同的。所以 我们只需要在 DP 的时候开一个数组 a[p]记录一下每个 P 值所达到的最长长度, 在计算每个 DP 状态的时候只需要暴力枚举一下所有的 P 值即可。 新的方程:f[i]=max{a[p]+1},I % p=0。 这样转移代价就变为 O(P),所以总时间复杂度为 O(NP)。

题3

树形图计数

这道题看到数据范围 n<=8 应该很容易想到搜索。 比较容易想到先枚举一个根,然后向下搜它有哪些子结点,但是这样的话等 于我们还要枚举一个点有几个子结点,复杂度高了点,处理起来也不方便。 这里提供一种方法: 依然是先枚举一个根, 然后依次搜索每个点的父结点,就是给每个点确定它 的父结点是谁,搜索过程中用并查集维护当前每个点的祖先。 比如现在搜索 I 点的父亲,枚举一个点 J,如果当前 J 的祖先不是 I,那么 J 就可以作为 I 的父亲。 枚举的根没有父亲,当每个点都找到父亲后累加答案即可。


更多相关文档:

冲刺NOIP2011长乐一中day2

福建省长乐一中 冲刺 Noip2011 冲刺 NOIP2011 长乐一中 day2 题目名称 存盘文件名 输入文件名 输出文件名 时限 内存限制 内存管理 ram ram.in ram.out 1s 128...

NOIP2011提高组解题报告day1

NOIP2011提高组解题报告day1_学科竞赛_高中教育_教育专区。NOIP2011提高组解题报告day1NOIP2011 提高组解题报告 day1 (2011-12-13 09:29:54) 标签: 杂谈 铺地...

NOIP2011复赛模拟题Day2

noip2011模拟day2 4页 1下载券 NOIP2011提高组解题报告... 9页 2下载券 NOIP2011 提高组 Day2 4页 免费 冲刺NOIP2011长乐一中da... 暂无评价 4页 免费 杭...

NOIP2011 提高组 day1 试题

NOIP2011 提高组 day1 试题_其它考试_资格考试/认证_教育专区。NOIP,2011,DAY...NOIP2011提高组复赛试题... 6页 1下载券 NOIP2011提高组解题报告... 9页 ...

Noip 2013 Day1 解题报告

Noip 2013 Day1 解题报告 --By GreenCloudS 第一题:转圈游戏(快速幂)根据题目,答案明显是(x+10^km) mod n,化简一下,就成了(x + m (10^k mod n) ...

长乐一中生物组方应钱

15页 1下载券 冲刺NOIP2011长乐一中da... 3页 免费 长乐一中高二竞赛 暂无评价...能力目标:搜集胚胎工程研究进展的资料,撰写专题综述报告。 3.情感目标:认同胚胎...

NOIP2015提高组day1第二题解题报告

NOIP2015提高组day1第二题解题报告_学科竞赛_高中教育_教育专区。NOIP2015提高组day1第二题的解题报告因为太简单所以写出来(误作者:蒟蒻zrw ...

NOI导刊冲刺NOIP2011模拟试题(一)

NOI导刊冲刺NOIP2011模拟试题(一)_信息与通信_工程科技_专业资料。信息学竞赛模拟试题模拟试题 十二) 试题( 冲刺 NOIP2011 模拟试题(十二) 1.单词分类(word.c/cp...

NOIP2015提高组解题报告

NOIP2015提高组解题报告_学科竞赛_高中教育_教育专区...NOIP2011 提高组 解题报... 4页 1下载券 NOIP...NOIP2015提高组day1第二... 8页 免费 NOIP2015...

NOIP2014普及组解题报告

NOIP2014 普及组复赛解题报告本人是潍坊一中的 wyw,...我表示如果把这个放在提高组 day1 的最后一题的话...Noip2014解题报告 15页 1下载券 NOIP2011普及组解题...
更多相关标签:
noip 2016 day1 | noip2016提高组day1 | noip2014day1 | noip2013提高组day1 | noip2016解题报告 | noip2015解题报告 | noip2015day2解题报告 | 冲刺noip2011 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com