当前位置:首页 >> 学科竞赛 >>

冲刺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长乐一中day2解题报告 隐藏>> 解题报告题 1、内存管理题目大意:对于每次申请,使用最小的内存块,对于每次访问,给出是否允许。 朴素算法:每次扫描一遍,...
冲刺NOIP2011长乐一中day1解题报告
3页 1财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 冲刺NOIP2011长乐一中day1解题报告 隐藏>> 题1 骑士守卫 ...
冲刺NOIP2011长乐一中day1
NOIP2011提高组试题-day1 6页 2财富值 NOIP2011提高组解题报告da... 15页 ...第 1 页共 3 页 福建省长乐一中 冲刺 Noip2011 题2 信任链 【问题描述】 ...
冲刺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) 标签: 杂谈 铺地...
2011noip复赛解题报告day1
冲刺NOIP2011长乐一中day1... 1页 免费 NOIP2008普及组 复赛解题报... 11页...2011noip解题报告 13页 1财富值如要投诉违规内容,请到百度文库投诉中心;如要提出...
NOIP 2011 提高组 day1 题解
NOIP 2011 提高组 day1 题解_其它考试_资格考试/认证_教育专区。NOIP2011 题...NOIP2011提高组解题报告... 9页 2下载券 NOIP2011 提高组 解题报... 4页...
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页 ...
NOIP2015提高组day1第二题解题报告
NOIP2015提高组day1第二题解题报告_学科竞赛_高中教育_教育专区。NOIP2015提高组day1第二题的解题报告因为太简单所以写出来(误作者:蒟蒻zrw ...
更多相关标签:
noip2016提高组day1 | noip2016day1 | noip2013day1 | noip2015day1 | noip2015提高组day1 | noip2012day1 | noip2014day1 | noip2016 day1 t2 |