CodeForces571A. Lengthening Sticks(组合数学-容斥)

题目大意:

a,b,c三根木棍可以增加三个不同的数字,aa,bb,cc,且aa+bb+cc<=L,问能构成三角形的木棒有多少种方案

题目思路:

如果我们直接考虑把L分配给aa,bb,cc好像不好下手

所以逆向考虑

合法的情况  =  所有情况 - 不合法的情况

 

step1:

首先计算所有的情况

假设L当时为l

我们把长度为l分配去的总的方案

这个问题我们等效为:有三个篮子,每个篮子放至少一个个物品,总共l个物品,问有多少种方案


我们用插板法解决这个问题

因为每个篮子放至少一个,而我们的目标是可以放0个,怎么办呢?

我们可以增加几个物品使初始每个篮子中就有一个,这里假设有m个篮子,n个物品

那我们的物品个数变为n+m,这时候会产生n+m-1个隔板

然后我们要选出m部分来,也就是放m-1个隔板

此时的方案为C(n+m-1,m-1)

 

回到这个题目

此时长度为l时,方案为C(l+3-1,3-1)

然后我们枚举一遍l,求和算出总的方案

所以得到为l的时候方案为C(l+2,2)

step2:

求不合法的方案==

假设a+aa,b+bb,c+cc(aa,bb,cc分别为分配的增加的长度)

假设a+aa是那条最长的边

此时不合法需要满足如下条件:

b+bb+c+cc<=a+aa

bb+cc<=l-aa

bb+cc<=min(l-aa,a-b-c+aa)

令T=bb+cc

这个时候再进行一下问题转化

有T个物品,分配到三个篮子里(可以分配0个)

三个篮子分别是bb,cc和多余的部分

回到上面的插板法一样的解法C(t+3-1.3-1)

然后用总的减去不合法就ok了

 CODE:

CodeForces571A. Lengthening Sticks(组合数学-容斥)
ll b,c,a,l;
int main() {
    a=read(),b=read(),c=read(),l=read();
    ll zong = (l+1)*(l+2)*(l+3)/6ll;
    ll no;
    for(int aa=0 ; aa<=l ; aa++) {
        ll t = min(l-aa,a-b-c+aa);
        if(t<0) continue;
        no = (t+2)*(t+1)/2ll;
        zong-=no;
    }
    for(int bb=0 ; bb<=l ; bb++) {
        ll t = min(l-bb,b-a-c+bb);
        if(t<0) continue;
        no = (t+2)*(t+1)/2ll;
        zong-=no;
    }
    for(int cc=0 ; cc<=l ; cc++) {
        ll t = min(l-cc,c-b-a+cc);
        if(t<0) continue;
        no = (t+2)*(t+1)/2ll;
        zong-=no;
    }
    out(zong);
    return 0;
}
View Code

 

上一篇:编译原理-消除左递归(自己看)


下一篇:解析export * from 与 export {default} from