题解 U534161 【开学酒局】
题目链接：开学酒局。
关于题目：作为 Day2T1，一道不怎么用思考的半裸题。
应用算法：数位dp。
首先说一句，虽然这道题的时间限制为 \(200ms\)，但是亲测暴力完全可过 \(60\%\) 的测试点。
出题人并没有毒瘤卡常！明明可以卡到
10ms，还是标程最大点时间的三倍以上。
下面进入正题：
- 一、分析题意：
\(\qquad\!\!\)对于一个满足条件的数字 \(c\)，假设其数位总数为 \(l\)，从低到高第 \(i\) 个数位上的数字为 \(c_i\)，则应满足 \(\forall i\in[3,l],||c_i-c_{i-1}|-c_{i-2}|<k\)。
\(\qquad\!\!\)题目要求就是求 \([l,r]\) 区间内，满足条件的数字 \(c\) 的总数量。
- 二、dp过程：
\(\qquad\!\!\)因为是数位dp，很自然能想到以下的状态、初始化和转移方程。
\(\qquad\!\!\)状态：\(f_{i,a,b}\) 表示从小到大的第 \(i\) 个数位上的数字为 \(a\)，第 \(i-1\) 个数位上的数字为 \(b\) 的数字中，所有满足条件的数字的个数。
\(\qquad\!\!\)初始化：由题面及数据范围 \(100\leqslant l \leqslant r \leqslant 2\times10^9\) 可知，最小的能够为答案进行贡献的数字为三位数，由此可知，应将所有 \(f_{2,a,b}\) 初始化为 \(1\)，以便进行转移。
\(\qquad\!\!\)转移方程：易知从较小的数位往较大的数位转移，加上判断条件，易得以下的转移方程：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22for(re int i=3;i<=10;i++)
//从小到大的第三个数位到第十个数位
{
for(re int a=0;a<=9;a++)
//a 为第 i 个数位上的数
{
for(re int b=0;b<=9;b++)
//b 为第 i-1 个数位上的数
{
for(re int c=0;c<=9;c++)
//c 为第 i-2 个数位上的数
{
if(abs(abs(a-b)-c)<k)
//如果满足条件
{
f[i][a][b]+=f[i-1][b][c];
//累计，转移
}
}
}
}
}
\(\qquad\!\!\)由于直接统计 \([l,r]\) 中满足条件的数字的总数量比较麻烦，我们规定 \(js(x)\) 表示 \([100,x)\) 中满足条件的数字的总数量，则易知 \(ans=js(r+1)-js(l)\)。
\(\qquad\!\!\)下面，我们考虑如何计算得到 \(js(x)\)。为了便于理解，我们同时举一个例子 \(x=98219,k=5\)。
$!!$1.将数字 \(x\)
拆成各个数位： 1
2
3
4
5while(x)
{
c[++l]=x%10;
x/=10;
}
$!!\(2.**统计其数量级以下的满足条件的数字的总数量**：
1
2
3
4
5
6
7
8
9
10for(re int i=3;i<l;i++)
{
for(re int a=1;a<=9;a++)
{
for(re int b=0;b<=9;b++)
{
ans+=f[i][a][b];
}
}
}
$!!$3.统计该数量级下第 \(l\)
位小于 \(x_l\)
的满足条件的数字的总数量： 1
2
3
4
5
6
7for(re int a=1;a<c[l];a++)
{
for(re int b=0;b<=9;b++)
{
ans+=f[l][a][b];
}
}
$!!$4.统计该数量级下第 \(l\)
位等于 \(x_l\) 且第 \(l-1\) 位小于 \(x_{l-1}\)
的满足条件的数字的总数量： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20if(l==3)
{
for(re int b=0;b<c[2];b++)
{
ans+=f[3][c[3]][b];
}
}
else
{
for(re int a=0;a<c[l-1];a++)
{
for(re int b=0;b<=9;b++)
{
if(abs(abs(c[l]-a)-b)<k)
{
ans+=f[l-1][a][b];
}
}
}
}
\(e.g.\) 统计了 \([90000,98000)\) 中满足条件的数字的总数量。
$!!\(5.**统计剩余答案**：
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
36for(re int i=l-2;i;i--)
{
switch(i)
{
case 1:
for(re int b=0;b<c[1];b++)
{
if(abs(abs(c[3]-c[2])-b)<k)
{
ans++;
}
}
break;
case 2:
for(re int b=0;b<c[2];b++)
{
if(abs(abs(c[4]-c[3])-b)<k)
{
ans+=f[3][c[3]][b];
}
}
break;
default:
for(re int b=0;b<c[i];b++)
{
if(abs(abs(c[i+2]-c[i+1])-b)<k)
{
ans+=f[i+1][c[i+1]][b];
}
}
}
if(abs(abs(c[i+2]-c[i+1])-c[i])>=k)
{
break;
}
}
\(\qquad\!\!\)（1）、因为这次统计是顺着 \(x\) 的数位从高往低循环的，所以如果前面的数位已经不符合条件了，后面就没有必要继续循环了：
\(\qquad\!\!\)（2）、如 4 中所说：“因为这是一个相邻的三个数位存在限制条件的数位dp，所以需要特殊处理最高的两个数位和最低的两个数位。”所以对于 \(i=1\) 和 \(i=2\) 的情况需要特殊处理。
\(\qquad\!\!\)其余的（default:
后的）就是正常的判断+统计答案。
\(e.g.\)
\(\qquad\!\! i=3\)，统计了 \([98000,98200)\)
中满足条件的数字的总数量，不满足 break 的条件继续循环。
\(\qquad\!\! i=2\)，统计了 \([98200,98210)\)
中满足条件的数字的总数量，满足了 break 的条件结束循环。
$!!$6.至此，只要 return ans 即可返回 \(js(x)\) 的值。
- 四、代码（码风不喜勿喷）：
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
using namespace std;
int l,r,k,f[20][20][20],c[20];
//每个数组或变量的含义详见处理过程。
in int qread()
//快读
{
int x=0,y=1;
int ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
{
y=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*y;
}
in void qwrite(re int x)
//快写
{
if(x<0)
{
putchar('-');
x=-x;
qwrite(x);
}
else
{
if(x>9)
{
qwrite(x/10);
}
putchar(x%10+'0');
}
return ;
}
in int js(re int x)
//计算 [100,x) 中满足条件的数字的总数量
{
memset(c,0,sizeof(c));
int l=0;
int ans=0;
while(x)
{
c[++l]=x%10;
x/=10;
}
//将数字 x 拆成各个数位
for(re int i=3;i<l;i++)
{
for(re int a=1;a<=9;a++)
{
for(re int b=0;b<=9;b++)
{
ans+=f[i][a][b];
}
}
}
//统计其数量级以下的满足条件的数字的总数量
for(re int a=1;a<c[l];a++)
{
for(re int b=0;b<=9;b++)
{
ans+=f[l][a][b];
}
}
//统计该数量级下第l位的数字小于x的第l位的数字的满足条件的数字的总数量
if(l==3)
{
for(re int b=0;b<c[2];b++)
{
ans+=f[3][c[3]][b];
}
}
else
{
for(re int a=0;a<c[l-1];a++)
{
for(re int b=0;b<=9;b++)
{
if(abs(abs(c[l]-a)-b)<k)
{
ans+=f[l-1][a][b];
}
}
}
}
//统计该数量级下第l位的数字等于x的第l位的数字且第l-1位的数字小于x的第l-1位的数字的满足条件的数字的总数量
for(re int i=l-2;i;i--)
{
switch(i)
{
case 1:
for(re int b=0;b<c[1];b++)
{
if(abs(abs(c[3]-c[2])-b)<k)
{
ans++;
}
}
break;
case 2:
for(re int b=0;b<c[2];b++)
{
if(abs(abs(c[4]-c[3])-b)<k)
{
ans+=f[3][c[3]][b];
}
}
break;
default:
for(re int b=0;b<c[i];b++)
{
if(abs(abs(c[i+2]-c[i+1])-b)<k)
{
ans+=f[i+1][c[i+1]][b];
}
}
}
if(abs(abs(c[i+2]-c[i+1])-c[i])>=k)
{
break;
}
}
//统计剩余答案
return ans;
//返回计算结果
}
int main()
{
l=qread();
r=qread();
k=qread();
//读入
for(re int a=0;a<=9;a++)
{
for(re int b=0;b<=9;b++)
{
f[2][a][b]=1;
}
}
//初始化
for(re int i=3;i<=10;i++)
//从小到大的第三个数位到第十个数位
{
for(re int a=0;a<=9;a++)
//a 为第 i 个数位上的数
{
for(re int b=0;b<=9;b++)
//b 为第 i-1 个数位上的数
{
for(re int c=0;c<=9;c++)
//c 为第 i-2 个数位上的数
{
if(abs(abs(a-b)-c)<k)
//如果满足条件
{
f[i][a][b]+=f[i-1][b][c];
//累计，转移
}
}
}
}
}
qwrite(js(r+1)-js(l));
putchar('\n');
//输出
return 0;
}
\(\qquad\!\!\)最后，再放一份验题人用记忆化搜索写的代码，比我的代码量少好多：
\(\qquad\!\!\)（尊重验题人的代码习惯，这里就不对他的缩进进行改动了。）
1 |
|
