当前位置:首页 >> 学科竞赛 >> 冲刺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模拟day2 4页 1下载券 NOIP2011提高组解题报告... 9页 2下载券 NOIP2011 提高组 Day2 4页 免费 冲刺NOIP2011长乐一中da... 暂无评价 4页 免费 杭...

NOIP2011提高组解题报告day1

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

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

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

模拟NOIP2011试题

冲刺NOIP2011模拟试题一 3页 1下载券 冲刺NOIP2011模拟试题(十... 4页 2下载...一题: 第一题:模拟开关 题目描述:有 N 盏电灯排成一行,依次编号为 1,2,...
更多相关标签:
网站地图

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