HDU 5787 数位dp

港控/mmm° 2022-09-25 05:16 139阅读 0赞

# K-wolf Number #

**Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)**  
**Total Submission(s): 1041    Accepted Submission(s): 394**

Problem Description

Alice thinks an integer x is a K-wolf number, if every K adjacent digits in decimal representation of x is pairwised different.  
Given (L,R,K), please count how many K-wolf numbers in range of \[L,R\].

Input

The input contains multiple test cases. There are about 10 test cases.  
  
Each test case contains three integers L, R and K.  
  
 1≤L≤R≤1e18  
 2≤K≤5

Output

For each test case output a line contains an integer.

Sample Input

1 1 2
    20 100 5

Sample Output

1
    72

题意：K-wolf number是连续k位各不相同的数，求L到R之间的K-wolf number。

分析：数位dp的模板题，连续K位不相同，只要记录前面k-1位就行了，用不着的位用10来代替，还有前导零的处理，设置一个标记判断每次要覆盖的数字是不是非0，如果覆盖的数字中不存在非0数字，那么当前这次选择就可以选择0，我们可以先把前导0去掉在比较，如果存在，那么就不用去掉前导零。

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    #define F first
    #define S second
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;int f=1;
        while((c=getchar())<'0' || c>'9')if(c=='-')f=-1;
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res*f;
    }
    const int N=100010,MOD=1e9+7;
    int bit[20],k,cnt;
    ll dp[20][11][11][11][11][2][2];
    
    //n数组表示数位的前面几位，now表示前面覆盖掉的数有没有不是0的数
    ll dfs(int pos,int n[],bool now,bool lim)
    {
        if(pos < 0){
            //printf("%d %d %d %d %d~\n",n[1],n[2],n[3],n[4],now);
            return 1;
        }
        if(!lim && ~dp[pos][n[1]][n[2]][n[3]][n[4]][now][lim])
            return dp[pos][n[1]][n[2]][n[3]][n[4]][now][lim];
    
        int mx = lim? bit[pos] : 9;
        ll ret = 0;
        int tmp[5];
        bool tmp_now=now;
    
        for(int i=0;i<=mx;i++){
            bool ok = 1;
            if(now){
                for(int j=1;j<=4;j++){
                    if(n[j] == i){
                        ok = 0;
                        break;
                    }
                }
                if(ok){
                    for(int x=1;x<4;x++){
                        tmp[x] = n[x+1];
                    }
                    tmp[4] = i;
                    for(int j=1;j<=4-k;j++) tmp[j] = 10;
                    ret += dfs(pos-1,tmp,now,lim && i==mx);
                }
            }
            else{
                int j=1;
                for(;j<=4;j++){
                    if(n[j] != 10 && n[j]) break;  //除去前导零
                }
                for(;j<=4;j++){
                    if(n[j] == i){
                        ok = 0;
                        break;
                    }
                }
                if(ok){
                    for(int x=1;x<4;x++){
                        tmp[x] = n[x+1];
                    }
                    tmp[4] = i;
                    tmp_now = now;
                    if(n[4-k+1] != 10 && n[4-k+1]) tmp_now=1; //要覆盖掉的数不是0
                    for(int j=1;j<=4-k;j++) tmp[j] = 10;
                    ret += dfs(pos-1,tmp,tmp_now,lim && i==mx);
                }
            }
        }
        if(!lim) dp[pos][n[1]][n[2]][n[3]][n[4]][now][lim] = ret;
        return ret;
    }
    
    ll solve(ll t)
    {
        cnt=0;
        while(t)
        {
            bit[cnt++] = t%10;
            t /= 10;
        }
        int n[5];
        for(int i=1;i<=4;i++){
            n[i] = 10;
        }
        return dfs(cnt-1,n,0,1);
    }
    
    int main()
    {
        ll L,R;
    
        while(cin>>L>>R>>k)
        {
            mem(dp,-1);   //注意每次初始化， 这个每次的k是改变的。
            k--;         //k位的时候需要记录前面k-1位
            ll ans = solve(R)-solve(L-1);
            printf("%I64d\n",ans);
        }
        return 0;
    }