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

noip2014


noip 2014民间题解
2014-11-08 13:57:22 By ydc 萌萌哒ydc来放题解了

先放day1,day2明天才考

T1:
考你会不会编程

T2:
n 个点n?1 条边的无向连通图就是个树

考虑距离为2的点对,可以理

解为枚举i ,i 能走到的点集两两之间距离为2
我们要做的是对于一个数组a 1 ,a 2 ,a 3 ,…,a m ,要求a i a j ,i≠j 的Σ与max

max是个很简单的事情,你只要求a 数组的最大值与次大值即可

至于Σ,我们知道∑ i=1 n ∑ j=1 n a i a j =(∑ i=1 n a i ) 2 ,于是容易推出我们要求的就是(∑ i=1 n a i ) 2 ?∑ i=1 n a 2 i
当然你也可以令s=∑ i=1 n a i ,求∑ i=1 n a i (s?a i )
复杂度应该是O(n) 的

T3
我们很容易看出一个很经典的完全背包的框架:我们可以在某个时刻上升1,2,3,…∞ 次,有n 个时刻

当然根据题意,这题和完全背包有很多的不同,比如能下降,不能选择上升0 次,下界不可到上界不可越,有些位置不允许,等等等等

即使如此,我们仍然能以完全背包的思想为核心,解决这个题

由于是完全背包,显然可以用滚动数组优化将空间降为O(m) 。为了便于理解,我们用二维状态来描述:dp i,j 表示横坐标为i ,纵坐标为j 的最小步数

由于不能上升0 次,我们这样转移:dp i,j =max(dp i?1,j?x i +1,dp i,j?x i +1)
由于有障碍,我们求出dp i,j 后再将障碍位置的值赋值为∞
由于上界可以越过,所以要特殊转移一下,dp i,m =max(dp i?1,k +s k ) ,s k 为k 达到m 处的花费,他是个式子,在此不将其展开

最后由于能下降,所以dp i,j 还可以由上一步在j+y i 的状态转移

如此问题就解决了,时间复杂度O(nm)

相关文章:
NOIP2014提高组复赛试题day1+day2
CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 1.生活大爆炸版石头剪刀布 (rps.cpp/c/pas) 【问题描述】 石头剪刀布是常见的猜拳游戏:石头胜剪刀,...
NOIP2014提高组复赛试题
CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 1.生活大爆炸版石头剪刀布 (rps.cpp/c/pas) 【问题描述】 石头剪刀布是常见的猜拳游戏:石头胜剪刀,...
NOIP2014普及组复赛试题解答
NOIP2014普及组复赛试题解答_学科竞赛_初中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 NOIP2014普及组复赛试题解答_学科竞赛_初中教育_教育专区。NOIP2014...
NOIP2014信息学奥赛全国联赛提高组参考答案
NOIP2014信息学奥赛全国联赛提高组参考答案_学科竞赛_高中教育_教育专区。NOIP2014信息学奥赛全国联赛提高组参考答案第二十届全国青少年信息学奥林匹克联赛初赛 提高组参...
NOIP2014 题解
NOIP2014 题解_IT/计算机_专业资料。NOIP2014 题解 D1T1 : 生活大爆炸版石头剪刀布(rps) 100% : 模拟。另一种方法,可以先求出 na,nb 的最小公倍数 l,...
NOIP2014提高组复赛试题(C语言版)
NOIP2014提高组复赛试题(C语言版)_其它课程_高中教育_教育专区。NOIP2014提高组复赛试题 C语言CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 (请选手务...
NOIP2014提高组复赛试题
CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 (请选手务必仔细阅读本页内容)一.题目概况 中文题目名称 英文题目与子目录名 可执行文件名 输入文件名 ...
noip2014普及组复赛题解
noip2014普及组复赛题解_财会/金融考试_资格考试/认证_教育专区。noip2014普及组复赛题解 余姚中学 罗方炜 余姚中学 罗方炜 1. 珠心算测验 注意看清题意:其中有...
noip2014普及组初赛试题
noip2014普及组初赛试题_学科竞赛_初中教育_教育专区。noip2014普及组初赛试题 第二十届全国青少年信息学奥林匹克联赛初赛普及组 pascal 语言试题 1、以下哪个是面向...
noip2014普及组解题报告
noip2014普及组解题报告_学科竞赛_初中教育_教育专区。noip2014普及组复赛解题报告1. 珠心算测验 穷举+桶排 b[i]=0 表示第 i 个数不等于集合中另外两个(不同...
更多相关标签:
noip2014提高组 | noip | noip2014普及组初赛 | noip2014提高组复赛 | noip2013 | noip2015 | noip2014提高组day2 | noip2014飞扬的小鸟 |