BZOJ3134 [Baltic2013]numbers+BZOJ3679数字之积-数位dp

3134是三年前写的题,这次复习顺便再写一道3679

BZOJ3134

题意:

一个数是非回文数当且仅当不包含长度大于1的回文数。比如16276是无回文数,而17276因为含有727而不是。
求区间内有多少个非回文数。

Solution:

非常经典的数位dp问题,一开始想到$f[len][pre][pre2][0/1]$表示第len位,第len-1位是pre,第len-2位是pre2,是否到达上界的方案数,但是发现这种状态下前导零会影响答案,那么我们多存储两个状态:$f[len][pre][pre2][zero1][zero2][0/1]$表示第len位,第len-1位是pre,第len-2位是pre2,第len-1位是否是前导零,第len-2位是否是前导零,是否到达上界的方案数,
记忆化搜索即可。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
long long ans;
long long f[20][10][10][2][2][2];
long long n;
int s[20];
int len=0;
long long dp(int l,int pre,int pre2,bool zero1,bool zero2,bool edg)
{
if (l>len) return 1;
if (f[l][pre][pre2][zero1][zero2][edg]) return f[l][pre][pre2][zero1][zero2][edg];
long long sum=0;
if (edg)
{
for (int i=0;i<=s[l];i++)
if ((zero1||i!=pre)&&(zero2||i!=pre2))sum+=dp(l+1,i,pre,zero1&&(i==0),zero1,edg&&i==s[l]);
f[l][pre][pre2][zero1][zero2][edg]=sum;
return sum;
}
else
{
for (int i=0;i<=9;i++)
if ((zero1||i!=pre)&&(zero2||i!=pre2))sum+=dp(l+1,i,pre,zero1&&(i==0),zero1,0);
f[l][pre][pre2][zero1][zero2][edg]=sum;
return sum;
}
}
long long solve(long long n)
{
memset(f,0,sizeof(f));
if (n<0) return 0;
len=0;
while (n)
{
len++;
s[len]=n%10;
n/=10;
}
reverse(s+1,s+1+len);
return dp(1,0,0,1,1,1);
}
int main()
{
scanf("%lld",&n);
n--;
ans-=solve(n);
scanf("%lld",&n);
ans+=solve(n);
printf("%lld",ans);
}

BZOJ3679

题意:

一个数x各个数位上的数之积记为f(x) (不含前导零)
求$[L,R)$中满足$0<f(x)\leq n$的数的个数

$ 0<L<R<10^{18} , n\leq10^9$

Solution:

其实可以发现大部分数位DP是比较套路的,设出状态后记忆化搜索就可以了。

这道题状态也比较显然:$f[i][sum][tag][zero]$表示第i位,当前的数之积是sum,是否是上界,前面有无前导0

然后通过记忆化搜索转移即可。

虽然n的级别是1e9,但是实际上我们只需要找其中部分2,3,5,7的倍数就可以,其实包含的状态很少,用map进行转移即可。

面对数位DP,记忆化搜索就是永远滴神!

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<cstdio>
#include<map>
#include<iostream>
using namespace std;
map<long long,long long> f[20][2][2];
map<long long,bool> vis[20][2][2];
long long n,L,R;
long long fin;
int cnt,a[20];
long long dp(int i,long long sum,bool tag,bool zero)
{

if (vis[i][tag][zero][sum]) return f[i][tag][zero][sum];

if (sum>n||(sum==0&&(!zero))||(zero&&i>cnt)) return 0;
if (i>cnt) return 1;
vis[i][tag][zero][sum]=1;
long long ans=0;
if (tag)
{
for (int k=0;k<=a[i];k++)
ans+=dp(i+1,sum*k,tag&&(a[i]==k),zero&&(k==0));
f[i][tag][zero][sum]=ans;
return ans;
}
if (zero)
{
for (int k=0;k<=9;k++)
ans+=dp(i+1,k,0,zero&&(k==0));
f[i][tag][zero][sum]=ans;
return ans;
}
for (int k=0;k<=9;k++)
ans+=dp(i+1,sum*k,0,zero&&(k==0));
f[i][tag][zero][sum]=ans;
return ans;
}
int main()
{
scanf("%lld",&n);
scanf("%lld%lld",&L,&R);
R--;
while (R)
{
a[++cnt]=R%10;
R/=10;
}
for (int l=1,r=cnt;l<=r;l++,r--) swap(a[l],a[r]);
dp(1,1,1,1);
fin=f[1][1][1][1];
for (int i=1;i<=cnt;i++)
{
vis[i][0][0].clear(),f[i][0][0].clear(),
vis[i][1][0].clear(),f[i][1][0].clear(),
vis[i][0][1].clear(),f[i][0][1].clear(),
vis[i][1][1].clear(),f[i][1][1].clear();
}

L--;
cnt=0;
while (L)
{
a[++cnt]=L%10;
L/=10;
}
for (int l=1,r=cnt;l<=r;l++,r--) swap(a[l],a[r]);
dp(1,1,1,1);
fin-=f[1][1][1][1];
printf("%lld",fin);
}

BZOJ3134 [Baltic2013]numbers+BZOJ3679数字之积-数位dp

http://blog.fizzmy.club/2018/01/18/BZOJ3134%20[Baltic2013]numbers-%E6%95%B0%E4%BD%8Ddp/

作者

Fizzmy

发布于

2018-01-18

更新于

2020-09-24

许可协议

评论