【数学/数位DP】牛客网19寒假R3G

链接:https://ac.nowcoder.com/acm/contest/329/G
来源:牛客网

经过了选号和漫长的等待,处女座终于拿到了给小姐姐定制的手环,小姐姐看到以后直呼666!

处女座其实也挺喜欢6这个数字的,实际上他做手环的时候选取的k=6。所以他对于包含数码6的数字极其敏感。每次看到像4567这样的数字的时候他的心就像触电了一样,想起了小姐姐。

现在你要给处女座展示一系列数字,你想知道他的内心会激动多少次。对于同一个数字,他最多只会激动一次,即如果这个数是66666,他还是只会激动一次。

输入描述:

一行包括两个数字l,r,表示你给处女座展示的数字范围为 [l,r]

输出描述:

一行一个整数,表示处女座内心激动的次数。

  • 示例1

  • 输入
    10 20

  • 输出
    1

  • 备注
    0≤l≤r≤10^18

此题做法很多。

1. 数学

可以先想求不含6的数有多少个,那么题目实际上是问的去掉6以后,给定一个数,问这个数在不含6的数组成的序列中排第几个。那么可以看成是给定一个9进制数,问在十进制数里排第几个(值是多少)。

比如18,看成九进制1\times9^1 + 7\times9^0 = 16
由于6被去掉了,那么8就排在了第7位。这个思想在很多题目里都可以用到。

那么如果给定的数本来就含6怎么处理呢?
第一,x5999x6xxx内所包含的 不含6 的数其实是一样多的。
第二,通过列表可以发现,凡是某一位有6的都不存在了,相当于问12之间有多少个1。所以对于含6的数,把最高位的6改为5,低位全部改成9就可以了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll l,r,pl,pr;
ll ni[22]={0},num[22]={0};

string s;
int len;
ll getnum(ll k)
{
    if(k<6) return k;
    return k-1;
}
ll solve(ll k)
{
    int cnt=0;
    memset(num,0,sizeof(num));
    int flag=0;
    while(k)
    {
        if(k%10==6) flag=1;
        num[cnt++]=k%10;
        k/=10;
    }
    if(flag) 
        for(int i=cnt-1;i>=0;i--) 
            if(num[i]==6) 
                for(num[i]=5,i--;i>=0;i--) num[i]=9;
    //x6xxx == x5999
    ll ret=0;
    for(int i=0;i<cnt;i++)
    {
        ret+=(getnum(num[i]) * ni[i]);
    }
    return ret;
}
int main()
{
    cin>>l>>r;
    pl=l;pr=r;
    ni[0]=1;
    for(int i=1;i<19;i++)
    {
        ni[i]=ni[i-1]*9;
    }
    if(l!=0) pl=solve(--l);
    pr=solve(r);
    cout<<(r-pr)-(l-pl)<<endl;
}</code></pre>

2.数位DP

数位DP一般用于求区间内,符合某个特征的值的个数。

数位DP的思想大概是由小区间求大区间。比如[0,9]求出来了那么[10,19] [20,29][90,99]都可以由低一位的区间求出。

  • 假设求[0,5874]
  • [0,999]以内先求出
  • [1000,4999]再求出
  • 最高位单独计算处理

所以数位DP如果写成记忆化搜索,那么一般会有标记记录是否满足条件,计算到第几位,是否计算到9(full)或只计算到本位的数字大小。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[25], num[25];
ll l,r;
ll dfs(int i,bool full)
{
    if(i==0) return 1;
    if(full && dp[i]!=0) return dp[i];
    int n=full?9:num[i];
    ll ret=0;
    for(int j=0;j<=n;j++)
    {
        if(j!=6)
        {
            ret+=dfs(i-1,full || j!=n);
        }
    }
    if(full) dp[i]=ret;
    return ret;
}
ll solve(ll x)
{
    if(x<0) return 0;
    memset(num,0,sizeof(num));
    int len=0;
    while(x)
    {
        num[++len]=x%10;
        x/=10;
    }
    return dfs(len,0);
}
int main()
{
    memset(dp,0,sizeof(dp));
    cin>>l>>r;
    ll al,ar;
    if(l!=0) al=solve(l-1);
    ar=solve(r);
    cout<<(r-l+1)-(ar-al)<<endl;
}</code></pre>

发表评论

邮箱地址不会被公开。 必填项已用*标注