题解：P10985 [蓝桥杯 2023 国 Python A] 整数变换

喵仔牛奶 · 2024-11-13 13:40:31 · 题解

Description

给你一个 n，每次减去数位和，求几次减完。

对于所有数据，n\le 10^{9}。

Solution

我看了一眼题，很快啊，啪地一下粘了个 CF331C3 的代码，直接跑到了最优解。

考虑 DP，想一想怎么设状态。考虑把一个数 n 分成除最高位的部分 x 和 n-x。但是这样 n 的最高位会产生影响，于是我们把最高也设进去。但是有了前面位的影响，可能会把 n 减到 <0，于是再开一个 DP 数组存最后的 n。

设 f_{x,n} 为前面的数位和为 x 时使 n=0 的最小步数，g_{x,n} 为减完后的 n。

转移时，取出最大的 v 使得 10^v\le n，记 t=10^v，我们分成 n\bmod t 和 n-(n\bmod t) 两部分。于是我们分成了两个子问题。

但是如果 n\bmod t=0，那么就会无限循环。所以对于这种情况，我们手动操作一次，这样 n\bmod t 就不为 0 了。我们成功把原问题分成了 n 更小的问题。

转移：

• 若 n\bmod t=0：
  • 记 p=f_{x,n-x-\lfloor n/t\rfloor},q=g_{x,n-x-\lfloor n/t\rfloor}；
• 否则：
  • 记 p=f_{x+\lfloor n/t\rfloor,n\bmod t},q=g_{x+\lfloor n/t\rfloor,n\bmod t}；

还有边界情况：

• 若 n=0，f_{x,n}=g_{x,n}=0。
• 记 w(n) 是 n 的数位和，若 n\le x+w(n)，f_{x,n}=1，g_{x,n}=n-x-w(n)。

记搜实现即可。分析一下复杂度：

• 每次的 n，要么是原来的 n 的后缀，要么是 \overline{999\dots99xy}（若干个 9 加上最后 \mathcal{O}(\log(\lvert\Sigma\rvert\log n))\approx 2 位）。所以 n 只有 \mathcal{O}(\lvert\Sigma\rvert\log^2 n) 种（其中 \Sigma 是字符集，本题中是 0\sim 9）。
• 而 x 只有 \max w(n)\approx\mathcal{O}(\lvert\Sigma\rvert\log n) 种，故总状态数为 \mathcal{O}(\lvert\Sigma\rvert^2\log^3 n)。
• 每次求出 t 与 w(n) 需要 \mathcal{O}(\log n)，不过这玩意可以轻松做到 \mathcal{O}(1)。
• 总复杂度为 \mathcal{O}(\lvert\Sigma\rvert^2\log^4 n)，精细实现可以做到 \mathcal{O}(\lvert\Sigma\rvert^2\log^3 n)。

Code

#define REP(i, l, r) for (int i = (l); i <= (r); ++ i)
#define DEP(i, r, l) for (int i = (r); i >= (l); -- i)
#define fi first
#define se second
#define pb emplace_back
#define mems(x, v) memset((x), (v), sizeof(x))
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
using namespace std;
namespace Milkcat {
    typedef long long LL;
    typedef pair<LL, LL> pii;
    const int N = 1e6 + 5;
    LL n; unordered_map<LL, pii> f[101];
    LL calc(LL n) {
        LL x = 0;
        while (n) x += n % 10, n /= 10;
        return x;
    }
    pii dfs(LL x, LL n) {
        if (!n) return {0, 0};
        if (n <= x + calc(n)) return {1, n - x - calc(n)};
        if (f[x].count(n)) return f[x][n];
        LL t = 1; while (t <= n / 10) t *= 10;
        if (n % t == 0) {
            auto [p, q] = dfs(x, n - x - calc(n));
            return {p + 1, q};
        }
        auto [p, q] = dfs(x + n / t, n % t);
        auto [A, B] = dfs(x, n / t * t + q);
        return f[x][n] = {p + A, B};
    }
    int main() {
        cin >> n;
        cout << dfs(0, n).fi << '\n';
        return 0;
    }
}