cf 834 E. Ever-Hungry Krakozyabra(爆搜+数位dp)

题意:

定义一种inedible tail为一个数把每一位数字按不降的顺序排列后，去掉前导0组成的序列

比如57040 组成的就是457 54组成就是45 45组成的也是45

问区间\([L,R]\)内有多少种inedible tail

题解: 直接数位dp做，需要存状态，太大处理不了。

这个问题等价于\(x0+x1+x2+...x9=18\)的非负整数解

组合数学插空法 \(18+9个1,选9个插空，其余变1就是解,C(18+9,9) \approx 4*10^{6}\)

所以可以暴力枚举出所有方案,然后快速判断这种方案在\([L,R]\)内是否合法

用类似数位dp的思想，用上下界来枚举每一位能取的数字，到到达某一位时即不在上界也不在下界，说明后面的数字可以随便取，那么一定取得出这种方案

由于只有在上界或者下界的时候递归才会继续往下走，所以最多走18次，线性复杂度判断

#include<bits/stdc++.h>

#define LL long long

#define P pair<int,int>

#define ls(i) seg[i].lc

#define rs(i) seg[i].rc

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define ls rt<<1

#define rs (rt<<1|1)

using namespace std;

int read(){

    int x = 0;

    char c = getchar();

    while(c < '0' || c > '9') c = getchar();

    while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();

    return x;

}

int pos,ans;

int a[20],b[20];

int cnt[10];///数字为i的个数

bool is(int pos,bool Lbound,bool Rbound){

    if(pos == 0) return true;

    if(!Lbound && !Rbound) return true;///不是上下界,后面的数字可以任意取一定存在合法的情况

    int l = Lbound?a[pos]:0;

    int r = Rbound?b[pos]:9;

    if(l > r) return false;

    for(int i = l;i <= r;i++){///枚举每一位能取的数字

        if(cnt[i]){

            cnt[i]--;

            if(is(pos - 1,Lbound && i == l, Rbound && i == r)){

                cnt[i]++;

                return true;

            }

            cnt[i]++;

        }

    }

    return false;

}

void dfs(int cur,int total){

    if(cur == 9){

        cnt[cur] = total;

        ans += is(pos,1,1);

        return ;

    }

    for(int i = 0;i <= total;i++){

        cnt[cur] = i;

        dfs(cur + 1, total - i);

    }

}

int digit(int *d,LL x){

    int pos = 0;

    while(x){

        d[++pos] = x % 10;

        x /= 10;

    }

    return pos;

}

int main(){

    LL L,R;

    cin>>L>>R;

    pos = digit(a,L);

    pos = digit(b,R);

    ans = 0;

    dfs(0,pos);///暴力枚举所有的组合

    cout<<ans<<endl;

    return 0;

}

巴特西

cf 834 E. Ever-Hungry Krakozyabra

cf 834 E. Ever-Hungry Krakozyabra(爆搜+数位dp)

题意:

最新文章

热门文章