4
21
2015
0

2015省选互测#6

从做题的顺序开始说:

D.3613: [Heoi2014]南园满地堆轻絮

首先答案是可以二分的,那我们要做的就是判断一个x是否可行。

而转化后的问题就是一个数列,第i项可以为a[i]-x到a[i]+x中的任意一项,那么问是否这个数列能不降?

这就变成了这道题[Poi2011]Temperature 当然只是弱化版,从前往后扫一遍即可。

这样是O(nlogn)的 不知道怎么就过掉了

然后正解是ans=差值最大的逆序对的差值+1>>1

正确性显然。。。

B.BZOJ3164: [Heoi2013]Eden的博弈问题

搞清题意之后DP一下,顺便记录状态的转移就好了。

A.BZOJ3163: [Heoi2013]Eden的新背包问题

醉啦。。。维护一个前缀多重背包和后缀多重背包,每次询问暴力合并两边的背包。这复杂度居然还就过了

C.BZOJ3165: [Heoi2013]Segment

考场上写暴力还写跪了没有线段交的时候忘了把ans变成0了

正解是这样的:wyl8899

 

Category: 模拟赛 | Tags: | Read Count: 855

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com