4
11
2015
0

BestCoder Round #37

怕掉rating上了小号。。。赛后有点儿后悔

A.很烦的分类讨论题,幸好没有被hack

B.如果l!=1&&r!=n的话我们发现只需要再割一下,然后就可以枚举这个拆分点了。

  否则那么就剩下了一段要求切2下,使得3段能够成一个三角形。

  我们枚举左端点,可行的区域一定是

 考试的时候第二种情况 没发现什么特别好的做法就直接枚举左端点无脑二分了。然后居然没有FST。。。

  忽然发现二分是错的QAQ 每次可行的是一段区间,但可能是不可行 可行 不可行 不满足单调性这也能不FST?

  

正解应该是左端点确定的时候右端点最大肯定是中间那段最大,最小肯定是中间那段是最小的。直接统计ans即可。不过好像直接把三个不等式列出来就可以知道ans了

 

C.刚开始看见没想法,后来想了想是不是有什么鬼畜的条件。然后发现每次数的个数变成了原来的二倍,那么r<=10^18那么也就是说不会超过70个数啦,然后就暴力把前面插入的数去查询有多少个,排个序暴力扫。

  然后果断FST了。。。原因在于我可以插入5W个数,然后只查询1-10^18 但不会超过70个数这70个数是刚刚插入的70个数。

D.弃疗了 不过发现题解中有个好玩的东西,笔记一下啦

  一个n个点每个点度数都是偶数的无向图的个数与一个n-1个点的无向图一一对应。

  因为我们可以把第n个点加入的时候向所有奇度数的点连边。这样就能保证所有点的度数都是偶数了。

 

Category: bestcoder | Tags: | Read Count: 385

登录 *


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

| Theme: Aeros 2.0 by TheBuckmaker.com