WA0 样例没过求调
查看原帖
WA0 样例没过求调
817524
CR400BFAZ5254楼主2025/8/1 16:43
#include<bits/stdc++.h>
#define MAXN 15
using namespace std;
using ll=long long;
ll l,r;
ll f[MAXN][2][MAXN][2];
ll p[MAXN];
// tt表示数码出现次数 eq表示当前位是否顶死
ll dfs(ll ws,bool eq,ll tt,bool is0,ll k){
    //1.判断边界 2.记忆化 3.枚举 4.存储记忆化答案
    ll ans=0;
    if(ws==0) return tt;
    if(f[ws][eq][tt][is0]!=-1 && !is0 && !eq) return f[ws][eq][tt][is0];
    for(int i=0;i<=9;i++){
        if(eq==1 && i>p[ws]) break;
        int t=ans;
        ans+=dfs(ws-1,eq&(i==p[ws]),tt+(!is0|i)&(i==k),is0&(i==0),k);
    }
    if(!is0 && !eq) f[ws][eq][tt][is0]=ans;
    return ans;
}
ll query(ll x,ll i){
    int tot=0;
    memset(f,-1,sizeof f);
    while(x){
        tot++;
        p[tot]=x%10;
        x/=10;
    }
    return dfs(tot,0,0,1,i);
}
int main(){
    cin >> l >> r;
    for(int i=0;i<10;i++){
        cout << query(r,i)-query(l-1,i) << " ";
    }




    return 0;
}
2025/8/1 16:43
加载中...