Codeforces 1513C 加一：题解｜刷题打卡

本文正在参与掘金团队号上线活动，点击 查看大厂春招职位

一、题目描述：

今天要写的题来自 Codeforces，也是一道比较有意思的题。
Codeforces 1513C 加一：

题目大意：
给你一个数字串 $n$，每次操作都需要对其中的每一位数字加一，数字 $1$ 变成 $2$,…, 数字 $9$ 变成 $10$，比如 $1912$ 会变成 $21023$，后面的操作也要遵循这个规则。

输入：
第一行是测试样例数 $t$。

之后的 $t$ 行，每一行都包括一个初始数字 $n$ 和一个操作步数 $m$。

输出：
你需要对每一个样例输出进行 $m$ 次操作后数字串的长度 $mod\,(1e9 + 7)$ 后的结果。

二、思路分析：

经过简单的分析可以发现 $[0…9]$ 的数字只要经过足够的步数后都会变为 $10$，而后的问题就变成了两个规模更小的问题：$1$ 和 $0$ 在经过剩下的步数后会变成多少位。

我们可以用 $f(i, m)$，$i \in [0, 9]$ 表示 $i$ 在 $m$ 步后的长度，很容易可以看出 $i$ 在 $10 – i$ 步后会变成 $10$，所以之后的情形可以简单地等效于 $1$ 和 $0$ 在经过 $m – (10 – i)$ 步后的总长度是多少。

所以有
$f(i, m) = \begin{cases} 1,\quad m < 10 – i\\ f(1, m – 10 + i) + f(0, m – 10 + i), \quad m \geq 10 – i \end{cases}$

看到这里，想必你已经知道怎么写了吧，预处理出一个二维数组记录可能会用到的 $f(i, m)$ 值，这就是二维 DP。但是做到这里我们还可以将其优化成一维。

设 $dp[j]$ 表示 $0$ 在 $j$ 步后的长度，由于 $\forall k \in [0, 9]$ 都可以看作 $j$ 经过 $k$ 步后产生的，所以 $f(i, m) = dp[i + m]$。

令 $j = m + i$，再结合上面的推导，我们就可以得到：
$dp[i] = \begin{cases} 1, \quad i < 10\\ dp[i – 9] + dp[i – 10], \quad i \geq 10 \end{cases}$

三、AC 代码：

#include <iostream>
using namespace std;
using ll = long long;

const int maxn = 2e5 + 50;
const int mod = 1e9 + 7;

int dp[maxn];

void getDp() {
    for (int i = 0; i < 10; ++i) {
        dp[i] = 1;
    }
    for (int i = 10; i < maxn; ++i) {
        dp[i] = (dp[i - 10] + dp[i - 9]) % mod;
    }
}

void solve() {

    int n, m;
    cin >> n >> m;
    int ans = 0;
    while (n) {
        ans = ((ll)ans + dp[n % 10 + m]) % mod;
        n /= 10;
    }

    printf("%d\n", ans);
}

int main() {
    
    // 一定要关闭同步流，不然 cin 会超时
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    getDp();
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}
复制代码

四、总结：

在写这道题的时候我首先想到的是倒推的递归写法，和 DP 写法的区别在于一个是从终点开始往前推，一个是从 $0$ 开始往后推。这两种写法的思想都是将大问题分解成小问题来解决，也就是分治，再一次说明了基本思想的重要性。简单的递归可能会导致栈溢出，感兴趣的同学可以尝试使用记忆化搜索优化来写递归，但那就是另外一个故事了。