code festival 2017 qualb题解

Source

code festival 2017 qualb

E

请先思考后再展开

此题不难,网上的题解搞得玄乎得一匹都不知道在说啥qwq,code

  1. 浅层分析:注意到一定存在一种方案,使得使用s或t的时候是为蓝色球服务的,所以我们更关心某一时刻能否选蓝色;而这个也是分阶段的,就是【仅红】、【t蓝】、【仅红】、【s蓝】、【仅红】;然后由贪心,我们可以强制t为第一次取蓝球的位置,同时这个球也是最前面的蓝球

  2. 考虑求$solve(A,B)$,枚举$t=1..A+1$,那么序列以$A+1-t$ 个红球和$1$个蓝球开始,不重不漏;此时剩下$t-1$个红球和$B-1$个蓝球,随后的$B-1$次任意选颜色(可能红色用完);设最后剩下共$t-1$个球,转化为子问题

  3. $$
    首先有x个红球和y个蓝球的多重集排列数=\frac{(x+y)!}{x!y!}=C_{x+y}^y,设pp(y,x)=\sum_{i=0}^x C_y^i \\
    solve1(A,0)=1,
    solve1(A,B>0)
    =\sum_{t=1}^{A+1} \sum_{i=0}^{t-1} C_{B-1}^i
    =\sum_{t=0}^{A} pp(B-1,t),本质上是前缀和 \\
    solve2(A,0)=1,
    solve2(A,B>0)=\sum_{t=1}^{A+1} \sum_{i=0}^{t-1} C_{B-1}^i solve1(t-1-i,i),O(n^2)
    $$

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/b5b79302.html
转载请注明出处,谢谢!