4
4
2015
0

BestCoder Round #36

比赛结束前1分钟交上去过了D题,还以为能AK了。然后终测完了发现没判n=1FST了

题意什么的直接去看chinese吧。

A.sb题(sb题你还WA一发)

B.sb题。出题人不卡map和set 超差评!!!害怕fst我还重交了一发hash!!!

C.无脑暴力题。把数和询问都从小到大排序O(n)搞掉。(出题人还用线段树什么鬼)

D.出题人说用生成函数。而我没(bu)用(hui)生成函数。 

  考虑枚举最大的,然后问题就变成了多重集合的组合数并且每个元素选的个数既有上界又有下界。特殊性是上界和下界都是一样的。

  那我们就可以枚举有多少个超出了范围然后用插板法容斥一下(其实是组合数学上的)

  复杂度并不是m^2而是m/1+m/2+……m/m=mlnm可以AC。

  坑点就是n=1的时候输出1

QAQ

 

Category: bestcoder | Tags: | Read Count: 466

登录 *


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

| Theme: Aeros 2.0 by TheBuckmaker.com