一道题写了有三天……
Add One
题意
定义一次“操作”为：将一个数的每一位的数值加 $1$ ，进位了就多占一位，如 $1912$ 操作一次后就是 $21023$
$T(T \le 2 \times 10^5)$ 组数据，每次给定 $n (1 \le n \le 10^9), m (1 \le m \le 2 \times 10^5)$ ，求 $n$ 操作 $m$ 次以后的长度
思考
考虑将 $n$ 的每一位分开计算
对于当前数 $x(x \in [1, 9])$ ，先用 $9 - x$ 次操作将其统一化成 $9$
问题化为对于数 $9$ ，进行 $m’$ 次操作后数字的位数
打表找规律，打表程序如下：
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
| #include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
list<int> a;
void work()
{
for (auto it = a.begin(); it != a.end(); ++it)
{
*it += 1;
if (*it == 10)
{
*it = 0;
auto t = it;
a.insert(++t, 1);
++it;
}
}
}
int main()
{
freopen("t.out", "w", stdout);
a.push_back(9);
for (int i = 1, j = 1; i < N; ++i)
{
work();
if (a.size() > j)
{
j = a.size();
cout << i << " - " << j << endl;
}
}
return 0;
}
|
差点把电脑挂了都没找到规律，估计是dp了
仔细一想，可以化成 $9$ 也就是可以化成 $10$ 嘛，然后每次进位时也是 $10$
通过题解发现dp方程如下：
设 f[i][j] 表示数 $i$ 加了 $j$ 次以后的方案数
$$
\begin{aligned}
f[i][j] =
\begin{cases}
1 & i + j < 10 \\
f[0][i + j - 10] + f[1][i + j - 10] & i + j > 10
\end{cases}
\end{aligned}
$$
两个细节：
- 开
long long
- 先枚举 $j$ 再枚举 $i$ ，否则转移时
f[0][i + j - 10] 和 f[1][i + j - 10] 可能没初始化
代码
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
| #include <bits/stdc++.h>
#define LL long long
using namespace std;
const int M = 2e5 + 5, P = 1e9 + 7;
LL f[10][M];
int main()
{
for (int j = 0; j < M; ++j)
for (int i = 0; i < 10; ++i)
{
f[i][j] = (i + j < 10 ? 1 : f[0][i + j - 10] + f[1][i + j - 10]) % P;
}
int T, n, m;
LL ans;
scanf("%d", &T);
while (T--)
{
scanf("%d %d", &n, &m);
ans = 0;
while (n)
{
ans = (ans + f[n % 10][m]) % P;
n /= 10;
}
printf("%lld\n", ans);
}
return 0;
}
|
我dp还是太弱了