LibreOJ 2044.「CQOI2016」手机号码

这题其实不难,是数位 DP 里边状态相对码农的类型。

DP 时除了模板以外,记录上上位,是否出现过 4/84/8,是否出现过连续的三个同号。
然后按照套路走。

代码:

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
#include <cstdio>
#include <cstring>
using namespace std;
const int LEN = 11;
long long l,r;
int d[LEN + 5],tot;
long long f[LEN + 5][10][10][2][2][2][2];
long long dfs(int x,int num,int pre,int lead,int yes,int _4,int _8,int top)
{
if(!x)
return yes;
if(!top && ~f[x][num][pre][lead][yes][_4][_8])
return f[x][num][pre][lead][yes][_4][_8];
long long ret = 0;
int bound = top ? d[x] : 9;
for(register int i = 0;i <= bound;++i)
{
if((_4 && i == 8) || (_8 && i == 4))
continue;
ret += dfs(x - 1,i,num,lead && !i,yes || (!lead && num == pre && i == num),_4 || (i == 4),_8 || (i == 8),top && i == bound);
}
if(!top)
f[x][num][pre][lead][yes][_4][_8] = ret;
return ret;
}
long long solve(long long x)
{
memset(f,-1,sizeof f) ;
tot = 0;
while(x)
{
d[++tot] = x % 10;
x /= 10;
}
return dfs(tot,0,0,1,0,0,0,1);
}
int main()
{
scanf("%lld%lld",&l,&r);
printf("%lld\n",solve(r) - solve(l - 1));
}

arknights