数位DP——CF55D Beautiful numbers(洛谷)

题意翻译

题目描述

Volodya是一个很皮的男♂孩。他认为一个能被它自己的每一位数上的数整除的数是很妙的。我们先忽略他的想法的正确性(如需证明请百度“神奇海螺”),只回答在l到r之间有多少个很妙的数字。

输入输出格式

输入:总共有t个询问:

第一行:t;

接下来t行:每行两个数l和r。

注意:请勿使用%lld读写长整型(虽然我也不知道为什么),请优先使用cin(或者是%I64d)。

输出:t行,每行为一个询问的答案。

题意很明了

但是没有什么思路

首先不可能模拟,绝对灰渣。

那就只能DP了,不难想到数位DP,顾名思义:一位一位的DP(胡扯的感觉)

如果不会数位DP,看博客:https://www.cnblogs.com/StungYep/p/12254173.html#2662535644(引用liuchang)

然后到了涨芝士的时候了(没有做广告)

小学生必备数学知识:(有点惭愧)

对于一个正整数,什么情况下它才能被组成它的非零数字整除呢

只有当这个正整数能被它所有数位的最小公倍数整除时,它才能被每一个数位整除

而且,1,2,3,4,5,6,7,8,9的最小公倍数是2520(常识哟)

学习芝士结束。

下面开始DP部分:

我们要进行DP的话,肯定要定义一个f 数组存储我们计算过的值

因为这道题和数位有关,所以第一位我们要定义当前遍历到了第几位

而且我们还要判断当前的数是否能被它所有数位的最小公倍数整除

所以我们还要开两维记录当前的数和它所有数位的最小公倍数

所以,最后的f数组就是f[当前枚举到了第几位][当前的数][当前数所有数位的最小公倍数]

题目中给出的最大的数就是9e18,所以最多有19位,那么第一维我们开20就可以了

第二维我们显然不能开到9e18,会超内存

因为我们最终统计的是这个数能否被它所有数位的最小公倍数整除,所以我们不必要记录原数的值

我们只需要记录原数对2520取模的结果就可以,因为2520是1到9的最小公倍数,所以取模之后不会有影响,x与x%2520是等效的

这时我们算一下内存20*2520*2520,还是会M掉

所以我们考虑减省一下第三维,由于第三维记录的是所有数位的最小公倍数,所以有很多数并不会出现

比如11、13、17、19……它们并不是1到9中任意几个数的最小公倍数

所以我们只需要记录2520的因数就可以了,这样的数有48个,所以我们开50就可以了

附48个数:

1 2 3 4 5 6 7 8 9 10 12 14 15 18 20 21 24 28 30 35 36 40 42 45 56 60 63 70 72 84 90 105 120 126 140 168 180 210 252 280 315 360 420 504 630 840 1260 2520 

 OK,大体思路应该有了,

下面是具体步骤:

首先要有个map,建立个映射。48个数

然后看代码吧,我写了一些注释,方便理解

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <iostream>
 5 #define DZN return//一定要先看这个 
 6 #define longdie 0;
 7 #define ll long long
 8 using namespace std;
 9 int digit[20],mp[2521],cnt;
10 ll dp[20][2521][50];
11 int gcd(int a,int b){//the most biggest 公约数 
12     DZN b==0?a:gcd(b,a%b);
13 }
14 ll dfs(int len,int pre,int mod,int limit){//主体部分 
15     if(!len) DZN pre%mod==0;
16     if(!limit&&dp[len][pre][mp[mod]]!=-1) DZN dp[len][pre][mp[mod]];
17     ll ret=0;int ed=limit?digit[len]:9;
18     for(int i=0;i<=ed;i++)
19         ret+=dfs(len-1,(pre*10+i)%2520,i==0?mod:mod*i/gcd(mod,i),limit&&i==ed);
20     if(!limit) dp[len][pre][mp[mod]]=ret;
21     DZN ret;
22 }
23 ll calc(ll n){//预处理 
24     int len=0;
25     while(n){
26         digit[++len]=n%10;
27         n/=10;
28     }
29     DZN dfs(len,0,1,1);
30 }
31 int main(){
32     //freopen("a.in","r",stdin);
33     memset(dp,-1,sizeof(dp));
34     for(int i=1;i<=2520;i++)
35         if(2520%i==0) mp[i]=++cnt;
36     int T;ll l,r;
37     cin>>T;
38     while(T--){
39         cin>>l>>r;
40         cout<<calc(r)-calc(l-1)<<endl;//差分 
41     }
42     DZN longdie 
43 }

 

代码有点皮!呵呵,防伪代码。

不要直接copy哟。

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

上一篇:一次好的聊天可以超过自己努力啃几周的书籍


下一篇:CF55D Beautiful(数位dp)