HDU 5787 K-wolf Number（数论）

迈不过友情╰ 2022-07-18 16:23 117阅读 0赞

题外话：前几天刚做了51nod上一道题，感觉和这个题套路有点像，给个链接https://www.51nod.com/onlineJudge/questionCode.html\#!problemId=1607，有兴趣的可以去看看。

顺便表示第一次自己想出的算法能跑这么快，小激动

![这里写图片描述][dcaaba114d4a2df6f1615717ea574197.png]

下面正题：

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5787

题目大意：给你一个区间l，r，你需要在l，r中找出一些数字，这些数字中连续的k位必须不能有重复数字。

解题思路：我们可以计算1到x的中的值，最后答案就是1到r减去1到l-1。

关于x我们可以先处理出比它低位的所有数的值。

即假如x是9位数，我们可以先处理出1位的，2位的值，3位的值---->9位的值，具体的值也是有规律的，下面举例说明。

假设x=58665432 k=5  
第一位1-9 9个  
第二位 10 -99 9\*9个  
第三位100-999 9\*9\*8个  
第四位1000-9999 9\*9\*8\*7个  
同理  
五位 9\*9\*8\*7\*6个  
因为只要和前k(在这里是5)个不相同就好了 所以  
六位 9\*9\*8\*7\*6\*6个  
七位 9\*9\*8\*7\*6\*6\*6个

这样 1-100000000便计算完了

接着要处理10000000-58335432，同样举例说明，就拿上面例子。

对于第一位 我们可以取值1-5，当第一位取1 2 3 4时，后面取值的个数为9\*8\*7\*6\*6\*6\*6，总的就为4\*9\*8\*7\*6\*6\*6\*6

当第一位为5时第二位的取值为0-8，同理，当第二位0-7时，后面的取值为8\*7\*6\*6\*6\*6，注意，应用一个数组记录当前k个数中的值，判断取值的时候应将一样的去除，如果所有的都被去除，则直接返回之前计算的结果，在这里第二位不能取5，所以总的为7\*8\*7\*6\*6\*6\*6

当第一位为5第二位为8时，第三位的取值为0-3，同理，当第三位为0-2时后面的取值为7\*6\*6\*6\*6，总的为3\*7\*6\*6\*6\*6

当第一位为5第二位为8第三位为3时，同理，第四位的取值为0-3，当第四位取值为0-2时后面的取值为6\*6\*6\*6，总的为3\*6\*6\*6\*6，注意这里不能再等于3了，因为前面出现过3，所以我们为第四位取2，又因为第四位为2的时候我们已经计算过了，所以直接返回答案。

如果没有上述情况，边计算边加到结束就可以了，注意最后一位的取值有些特殊。

AC代码：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <string>
    #include <vector>
    #include <list>
    #include <map>
    #include <queue>
    #include <stack>
    #include <algorithm>
    #include <numeric>
    #include <functional>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define mem(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9;
    const int inf1=-1*1e9;
    double EPS=1e-10;
    typedef long long LL;
    LL k;
    int time[15],num[50];
    
    LL cal(LL len)//计算某长度所有值
    {
        LL ans=9;
        LL q=9;
        len--;
        int time=1;
        while(len)
        {
            if(time<k)
            {
                ans*=q;
    
                time++;
                if(time<k) q--;
            }
            else
            {
                ans*=q;
            }
            len--;
        }
        return ans;
    
    }
    
    
    
    
    LL call(LL x)
    {
        if(x==0) return 0;
        if(x<10) return x;
        LL a[50];
        LL len=1;
        while(x)
        {
            a[len]=x%10;
            x/=10;
            len++;
        }
        LL ans=0;
        for(int i=1; i<len-1; i++)
        {
            ans+=cal(i);//加上低位的所有制
        }
        for(int i=1; i<=len/2; i++)
            swap(a[i],a[len-i]);//将此数存到数组里
    
        memset(time,0,sizeof(time));
        LL t=cal(len-1)/9;//t保存后面的取值
        LL ans11=0;
        ans11=ans11+cal(len-1)/9*(a[1]-1);//第一位的所有可能值
        ans+=ans11;
        num[1]=a[1];
        time[num[1]]++;
        int i;
    
        for(i=2; i<len-1; i++)//2-len-2位的所有可能值
        {
            if(i<k) t=t/(9-i+2);
            else t/=(9-k+2);
            LL x=0;
            if(i>k) time[num[i-k]]--;
            for(int j=0; j<=a[i]; j++)
            {
                if(!time[j]) x++;//0-a[i]每一个都出现过直接返回就可以了
            }
            if(x==0) return ans;
            if(time[a[i]])//判断最高位是否出现过，出现过计算完低位就可以直接返回了
            {
                ans+=t*x;
                return ans;
            }
            else
            {
                x--;
                ans+=t*x;
                //标记此位的值，并表示已经出现过
                num[i]=a[i];
                time[num[i]]++;
            }
        }
        if(i>k) time[num[i-k]]--;//最后一位特殊处理
        for(int j=0; j<=a[i]; j++)
        {
            if(!time[j]) ans++;
        }
    
        return ans;
    }
    
    int main()
    {
        LL l,r;
        while(scanf("%I64d %I64d %I64d",&l,&r,&k)!=EOF)
        {
            if(r==1e18) r--;
            cout<<call(r)-call(l-1)<<endl;
        }
    
        return 0;
    }

[dcaaba114d4a2df6f1615717ea574197.png]: /images/20220718/e4eff19d81af42f5a1dd189a23a8a247.png