当前位置：首页 >> 学科竞赛 >>
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 题解
- NOIP2014 题解_IT/计算机_专业资料。NOIP2014 题解 D1T1 : 生活大爆炸版石头剪刀布(rps) 100% : 模拟。另一种方法,可以先求出 na,nb 的最小公倍数 l,...
- NOIP2014初赛普及组C++题目及答案
- NOIP2014初赛普及组C++题目及答案_学科竞赛_高中教育_教育专区。本文是noip2014年普及组c++的题目及答案,有需要的可以下载学习。第二十届全国青少年信息学奥林匹克...
- NOIP2014提高组第一试题解
- NOIP2014 提高组第一试题解【第一题】石头剪刀布 rps 【题目大意】 a 和 b 石头剪刀布游戏,每个人一共有五种方式,相互之间的胜负关系给出,a 和 b 出拳的...
- noip2014普及组复赛题解
- noip2014普及组复赛题解_财会/金融考试_资格考试/认证_教育专区。noip2014普及组复赛题解 余姚中学 罗方炜 余姚中学 罗方炜 1. 珠心算测验 注意看清题意:其中有...
- NOIP2014初赛普及组试题_C++
- NOIP2014初赛普及组试题_C++_学科竞赛_初中教育_教育专区。NOIP2014初赛普及组试题 第二十届全国青少年信息学奥林匹克联赛初赛 普及组 C++语言试题 一、快单项选择题...
- noip2014初赛普及组Pascal试题及答案
- noip2014初赛普及组Pascal试题及答案_学科竞赛_初中教育_教育专区。noip2014初赛普及组Pascal试题及答案 第二十届全国青少年信息学奥林匹克联赛初赛 普及组 Pascal 语言...
- Noip2014初赛提高组C试题及答案(完整版)
- Noip2014初赛提高组C试题及答案(完整版)_IT认证_资格考试/认证_教育专区。Noip2014 初赛提高组试题及答案(完整版) 提高组 C 语言试题 一、单项选择题(每题 1.5...
- NOIP2014普及组复赛试题解答2
- NOIP2014普及组复赛试题解答2_IT认证_资格考试/认证_教育专区。NOIP2014普及组复赛试题 螺旋矩阵 解答 NOIP2014 普及组复赛试题解答 3. 螺旋矩阵 【问题描述】 一...
- NOIP2014提高组复赛试题
- CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 (请选手务必仔细阅读本页内容)一.题目概况 中文题目名称 英文题目与子目录名 可执行文件名 输入文件名 ...
- NOIP2014复赛提高组模拟试题
- toy.out 14 第 3 页,共 5 页 CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 day1 3.跑步 (running.cpp/c/pas)【问题描述】 某校开展了同学们喜闻乐见的阳...
