首页 > 其他 > 详细

NOIP 赛前模拟记录

时间:2016-08-12 01:16:54      阅读:193      评论:0      收藏:0      [点我收藏+]

8.11

T1 给定一个序列M,求出能过构造出的序列使得(Si+Si+1)/2=Mi成立的序列个数.保证M,S递增。

T2 平面点集中最大的四边形面积

T3 不太懂得一道国家队选拔的加强版。

 

90+20+10=120 三题暴力

T1写了一个非常不正确的O(n)结果拿了90,T2只想到了n^3的做法,T3暴力

Sol:

T1显然知道S中的一个数就可以知道所有的S,每个S都可以由S1和Mi来表示,那么由于S是递增的就可以列出一些很有规律的不等式,解不等式即可。

不正确的做法就是对于每三个M的差,两边的和-中间的最小值。

T2四边形肯定会有一条的对角线那么枚举对角线,在枚举对角线的两端就能做到O(n^3)

会发现答案的四边形显然会在凸包上,那么离对角线最远的点总是单调的。

T3看了不会

 

NOIP 赛前模拟记录

原文:http://www.cnblogs.com/yyjxx2010xyu/p/5763159.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!