95992828九五至尊2

617888九五至尊2[您发出新的未分配科技点]数位dp:从懵X到板子(例题:HDU2089 不要62)[bzoj1833][ZJOI2010]count 数字计数——数位dp

九月 27th, 2018  |  617888九五至尊2

数位dp主要用来处理同系列需要数屡的题材,一般套路为“求[l,r]区间内满足要求的数/数个之个数”

题目:

(传送门)[http://www.lydsy.com/JudgeOnline/problem.php?id=1833]

要求五花八门……比如“不出新有数字序列”,“某种数之面世次数”等等……

题解:

率先不成接触频繁个dp,真的是恶意。
首先看了森居多等同维dp,因为若拍卖前缀0,所以从做不知情。
询问了dalaolidaxin的博客,又查看了资料:
初探数位dp
才完全将明白是写。
具体的,我们设
f[i][j][k]啊考虑有i位数,最高位吗j数,之中k的数。
咱俩可得出方程:
\[f[i][j][k] = \sum
f[i-1][l][k] (j!=k)\]
\[f[i][j][k] = \sum
f[i-1][l][k] + 10^{i-1} (j==k)\]
咱针对这方程作出解释:
眼前一模一样项非常好理解,后一致码之口舌虽是前(i-1)位数共有\(10^{i-1}\)个,对于内部各级一个,我们且可以在前方加k。
这样咱们事先处理出来了f。
下一场我们着想对n分块计算。
以n = 4321为例。
第一统计3各类和以下的累,这些数字没有限制,直接加就是哼。
接下来统计4员数。
对于一个4各类数,我们一样各项一各项往下考虑,如果最高位<k,直接加,如果=k,加上n+1
切实见代码。

面对这种频繁数开,暴力的想法是枚举每个数,判断是否满足条件

代码

#include <cstdio>
#include <cstring>
using namespace std;
#define ll long long
const int N = 25;
struct node {
  ll a[N];
  node() { memset(a, 0, sizeof(a)); }
  ll &operator[](const int &x) { return a[x]; }
};
node operator+(const node &x, const node &y) {
  node tmp;
  for (int i = 0; i <= 9; i++)
    tmp.a[i] = x.a[i] + y.a[i];
  return tmp;
}
int len, a[N];
ll pow[N];
node f[N][N];
void init(ll n) {
  len = 0;
  while (n) {
    a[++len] = n % 10;
    n /= 10;
  }
  for (int i = 0; i <= 9; i++)
    f[1][i][i] = 1;
  for (int i = 2; i <= 14; i++) {
    for (int j = 0; j <= 9; j++) {
      for (int k = 0; k <= 9; k++)
        f[i][j] = f[i][j] + f[i - 1][k];
      f[i][j][j] += pow[i - 1];
    }
  }
}
node calc(ll n) {
  node ans;
  if (!n)
    return ans;
  memset(f, 0, sizeof(f));
  init(n);
  //统计前len-1位
  for (int i = 1; i <= len - 1; i++) {
    for (int j = 1; j <= 9; j++) {
      ans = ans + f[i][j];
    }
  }
  //开始统计len位数
  for (int i = 1; i <= a[len] - 1; i++)
    ans = ans + f[len][i];
  n %= pow[len - 1];
  ans[a[len]] += n + 1; //对于每一个最高位都可以统计一发
  for (int i = len - 1; i; i--) {
    for (int j = 0; j < a[i]; j++)
      ans = ans + f[i][j];
    n %= pow[i - 1];
    ans[a[i]] += n + 1;
  }
  return ans;
}
int main() {
  pow[0] = 1;
  for (int i = 1; i <= 14; i++)
    pow[i] = pow[i - 1] * 10;
  ll x, y;
  scanf("%lld %lld", &x, &y);
  node ans1 = calc(y), ans2 = calc(x - 1);
  for (int i = 0; i <= 8; i++)
    printf("%lld ", ans1[i] - ans2[i]);
  printf("%lld\n", ans1[9] - ans2[9]);
  return 0;
}

照这样:

#include<cstdio>
using namespace std;
typedef long long LL;
LL l,r,cnt; 
int main()
{
    scanf("%lld%lld",&l,&r);
    for(LL i=l;i<=r;i++)
        if(/*i符合条件*/)cnt++;
    printf("%lld",cnt);
} 

如此很显会T……所以我们着想以一些出乎意料之属性来数数(一般这些性可用来递推、或是dp一样的变换)

比如看下面一起例题:

对于被定闭区间[L,R],求非0往往各类出现的个数

sample input:23 233

sample output: 515

先是转化为calc[1~R]-calc[1~L-1](我们若数字的低位也第1位,次低为各类第2号,以此类推)

做法1:专门统计数位的艺术:我们先行预处理bin[i]也10底i次方,再预处理dp[i]代表于i位数的限外(1~99…999(i个9))某种数字之个数

那考虑dp[i]和dp[i-1]内的更换:

先是,第i员的数字为0~9时犹可针对第i号数字之dp值产生dp[i-1]的贡献

也即:[0~10…(i-1个0)…0)的末i-1位贡献+[10…(i-1个0)…0~20…(i-1个0)…0)的末i-1位贡献+……+[90…(i-1个0)…0~10…0(i个0))的末i-1位贡献

紧接着,后面i-1各呢任意数是还见面给第i员之数字出+1的献,由排列组合知总共有bin[i-1]的贡献

从而换是dp[i]=10*dp[i-1]+bin[i-1](其实化简一下相,也堪写成dp[i]=i*bin[i-1])

发矣这dp数组我们着想什么算对于有数字x计算[1~x]某个数位st的起个数,这个进程及事先递推的进程很一般

咱们枚举x的第i员位bit

1° bit>st
第i位取0~bit时犹足以追加dp[i-1]的贡献,而0~bit里一定会出应声无异各项取st的状况,贡献加上bin[i-1]

因此ans+=bin[b-1]+d*dp[b-1];

2° bit==st
设tail=x%bin[i-1](x的前i-1个数之值)第i员取0~bit时还得长dp[i-1]的孝敬,但是当第i各项取st(bit)时,只有tail+1种数比x小,因此贡献只有来tail+1

此时ans+=tail+1+d*dp[b-1];

3°bit<st 第i位取0~bit时都好加dp[i-1]的贡献,但0~bit取不到st

所以ans+=d*dp[b-1];

但是当统计截止答案后,如果我们统计的st==0,前导0被多统计了(第i员不克取0,因此多加了bin[0]+bin[1]+…+bin[再三的位数-1]),在最终减去即可

代码见下:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath>
 5 using namespace std;
 6 typedef long long LL;
 7 typedef unsigned long long ULL;
 8 LL l,r,bin[20],dp[20];
 9 inline void intn()
10 {    
11     bin[0]=1;//bin[i]是10的j次方 
12     for(int i=1;i<=18;i++)
13         bin[i]=bin[i-1]*10,dp[i]=dp[i-1]*10+bin[i-1];
14             //第i位是0~9的时候,都会有+dp[i-1]的新贡献
15             //而后面i-1位任一情况时都会给第i位的数字贡献+1,一共有bin[i-1]种情况 
16 }
17 inline LL calc(LL sum,int state)
18 {
19     LL tmp=sum;
20     int b=0,d;LL ans=0;//tail是末几位的数字大小 
21     while(sum)
22     {
23         d=sum%10;sum/=10,b++;
24         if(d>state)ans+=bin[b-1]+d*dp[b-1];
25         //对本位(指第i位)有bin[b-1](末i-1位随意选择)的贡献,第i位是0~d的时候都会有贡献 
26         else if(d==state)ans+=(tmp%bin[b-1])+1+d*dp[b-1];
27         //本位的贡献仅限于末位的数字大小+1(全0也会提供贡献) 
28         else ans+=d*dp[b-1];//本位没有贡献 
29     }
30     d=0;
31     if(state==0)
32     //前导0被重复计算了,一位数多算了一个0,两位数多算了10个零,如此我们减去多算的就好了   
33         while(tmp)  
34             ans-=bin[d++],tmp/=10;  
35     return ans; 
36 }
37 inline LL work(LL data)
38 {
39     LL ans=0;
40     for(int i=1;i<=9;i++)
41         ans+=calc(data,i);
42     return ans;
43 }
44 int main()
45 {
46     scanf("%lld%lld",&l,&r);
47     intn();
48     LL ansr=work(r);
49     if(l==0)printf("%lld",ansr);
50     else printf("%lld",ansr-work(l-1));
51 }

做法2:正经(?)dp法

我们设f[i][j]为x的前面i位数并且第i位数为j时j的产出次数,依然预处理bin[i]同上

那类别上面的做法

首先f[i][j]+=Σ(f[i-1][k],0<=k<=9);接着,如果j不是0,我们以长第i员对是数之贡献bin[i-1](其实就落实了面统计时最后消去前导0的历程)

假如顾的一些凡是[0~10…(i-1个0)…0)等都是一个荒谬闭右起区间,如果算work(R)-work(L-1),就无法统计R的贡献

因而我们算时也采用不当闭右起区间,计算work(R+1)-work(L)就哼啊

代码见下:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
LL l,r,bin[20];
LL f[30][15];//f[i][j]表示前i位,第i位数字为j的j出现次数 
int bit[20];
inline void intn()
{
    bin[0]=1;//bin[i]是10的j次方 
    for(int i=1;i<=18;i++)
        bin[i]=bin[i-1]*10;
    for(int i=1;i<=18;i++)
        for(int j=0;j<10;j++)
        {
            for(int k=0;k<10;k++)
                f[i][j]+=f[i-1][k];            
            f[i][j]+=(j==0)?0:bin[i-1];
        }
}
inline LL work(LL x){
    int cnt=0,b=0;while(x)bit[++b]=x%10,x/=10;//bit表示每一位 
    LL ans=0;
    for(int i=b;i;i--)
    {
        for(int j=0;j<bit[i];j++)
             ans+=f[i][j];//第i位是0~bit[i]-1的情况 
        ans+=bin[i-1]*bit[i]*cnt;//第i位是bit[i]的情况 
        //这里的cnt记录了“第i位以前(第i+1位到最高位)有多少个数不是0”,因为他们也算是非0数位。 
        if(bit[i])cnt++;
    }
    return ans;
}
int main()
{
    scanf("%lld%lld",&l,&r);
    intn();
    LL ansr=work(r+1);
    if(l==0)printf("%lld",ansr);
    else printf("%lld",ansr-work(l));
}

脚我们还来平等志例题:[HDU2089]不要62

不要62

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K
(Java/Others)

Problem Description

杭州口如那些傻乎乎粘嗒嗒的人工62(音:laoer)。杭州交通管理局时会扩大一些的士车牌照,新近出来一个好信息,以后上牌照,不再含有不吉利的数字了,这样一来,就好免个别的士司机和乘客的心理障碍,更安全地劳动群众。不红的数字呢具含有4要么62之数码。例如:62315
73418
88914还属于无吉利号码。但是,61152虽说涵盖6暨2,但无是62连号,所以不属无吉祥数字的列。

您的天职是,对于每次吃来底一个牌照区间号,推断出交管局今次同时如果实在为小辆新的士车上牌照了。

Input

输入的且是整数对n、m(0<n≤m<1000000),如果遇上都是0的平头针对性,则输入完毕。

Output

对每个整数对,输出一个请勿含不吉祥数字的统计个数,该数值占一行位置。

Sample Input

1 100 0 0

Sample Output

80

 

题解:

咱俩依旧定义f[i][j]多次组,为前i位数第i个呢j时之法定频的多寡

初始化时f[0][0]=1;

这就是说泾渭分明当且仅当j!=4&&!(j==6&&k==2)时,能生易f[i][j]+=f[i-1][k];

统计答案时,我们还是由高位向亚统计,当我们枚举的数位j满足j!=4&&!(x的第i+1各类==6&&j==2)时好统计答案。

需要注意的是:如果我们发现原数中的有平介乎出现了62或4,我们一直了统计,因为617888九五至尊2于高位相等的前提下更小之位数一定不合法了。

代码见下:

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 typedef long long LL;
 5 int l,r,bit[15],f[10][15];
 6 inline void intn()
 7 {
 8     f[0][0]=1;
 9     for(int i=1;i<=8;i++)
10         for(int j=0;j<10;j++)
11         {
12             if(j==4)continue;
13             for(int k=0;k<10;k++)
14             {
15                 if(j==6&&k==2)continue;
16                 f[i][j]+=f[i-1][k];
17             }
18         }
19 }
20 inline int work(int x)
21 {
22     memset(bit,0,sizeof(bit));
23     int b=0,cnt=0,ans=0;
24     while(x)bit[++b]=x%10,x/=10;
25     for(int i=b;i;i--)
26     {
27         for(int j=0;j<bit[i];j++)
28         {
29             if(j==4||(bit[i+1]==6&&j==2))continue;
30             ans+=f[i][j];
31         }
32         if(bit[i]==4||(bit[i+1]==6&&bit[i]==2))break;
33     }
34     return ans;
35 }
36 int main()
37 {
38     intn();
39     while(scanf("%d%d",&l,&r)==2)
40     {
41         if(l==r&&r==0)break;
42         printf("%d\n",work(r+1)-work(l));
43     }
44 }
45      

 

 

相关文章

标签:,

Your Comments

近期评论

    文章归档

    功能


    网站地图xml地图