题解思路与方法

整除条件拆分

因为 $495=5\times9\times11$，故需同时满足：

1. 整除 5：末位为 $0$ 或 $5$；
2. 整除 9：所有位数字和 $\equiv0\pmod9$；
3. 整除 11：交错位和（从最低位开始奇数位减、偶数位加）$\equiv0\pmod{11}$。

动态规划算法

1. 预处理符号

   • 将输入的数字看作一个长度为 L 的字符数组，从左到右编号为 0…L-1。
   • 为了判断整除 11，需要对每一位乘以 +1 或 –1：最高位对应符号根据它从右边数过来的位置是偶数还是奇数来决定。简而言之，最右边第一位用 +1，第二位用 –1，第三位用 +1，以此类推。

2. 定义状态

   • 用三维数组 dp[i][r9][r11] 表示：当我们已经处理完前 i 位（也就是下标 0 到 i-1），并且到目前为止所有已选数字之和对 9 的余数是 r9、对 11 的“交错和”余数是 r11 时，最少要做多少次修改。
   • 一开始（i=0），还没填任何数字，两个余数都算作 0，修改次数为 0；其余状态都初始化为“极大值”。

3. 状态转移 对于第 i 位（0 ≤ i < L），我们尝试把它改成每一个可能的数字 d：

   • 如果 i=0，就不能选 0，避免前导零；
   • 如果 i=L-1（最后一位），只能选 0 或 5，以保证整除 5；
   • 其它位置可以选 0 到 9。

   每次尝试后：

   • 新的“和 mod 9”是多少，就把旧的 r9 加上 d 再对 9 取余；
   • 新的“交错和 mod 11”是多少，就把旧的 r11 加上 当前位置的符号乘以 d，再对 11 取余；
   • 如果 d 和原来这一位不同，就要多算一次修改；
   • 用新的修改次数去更新 dp[i+1][新r9][新r11]。

4. 答案与路径重构

   • 最终看 dp[L][0][0]，那就是把整个数字改成 495 的倍数所需的最少修改次数。
   • 同时我们在每一步记录“前驱”选择的数字和旧的 r9、r11，就能从尾到头把具体修改后得到的新数字串找出来。

复杂度分析

• 状态数 $\approx L\times9\times11\le19\times99\approx1881$；
• 每状态枚举至多 $10$ 个 $d$，总转移 $\lesssim18810$；
• 路径重构 $O(L)$。 总体 $O(L\times9\times11\times10)$，$L\le18$ 时远小于时间限制。

代码实现

Python 版本

import sys

def solve():
    s = sys.stdin.readline().strip()
    L = len(s)
    # 交错和符号
    sign = [1 if ((L-1-i)%2==0) else -1 for i in range(L)]
    INF = 10**9
    # dp[i][r9][r11]
    dp = [[[INF]*11 for _ in range(9)] for __ in range(L+1)]
    pre = [[[None]*11 for _ in range(9)] for __ in range(L+1)]
    dp[0][0][0] = 0

    for i in range(L):
        orig = int(s[i])
        for r9 in range(9):
            for r11 in range(11):
                if dp[i][r9][r11] == INF: continue
                for d in range(0, 10):
                    if i==0 and d==0: continue
                    if i==L-1 and d not in (0,5): continue
                    nr9 = (r9 + d) % 9
                    nr11 = (r11 + sign[i]*d) % 11
                    cost = dp[i][r9][r11] + (d != orig)
                    if cost < dp[i+1][nr9][nr11]:
                        dp[i+1][nr9][nr11] = cost
                        pre[i+1][nr9][nr11] = (r9, r11, d)

    # 输出结果
    ans = dp[L][0][0]
    print(ans)
    # 重构
    res = ['0']*L
    r9, r11 = 0, 0
    for i in range(L, 0, -1):
        pr = pre[i][r9][r11]
        res[i-1] = str(pr[2])
        r9, r11 = pr[0], pr[1]
    print("".join(res))

if __name__ == "__main__":
    solve()

Java 版本

import java.io.*;
import java.util.*;

public class Main {
    static final int INF = 1_000_000_000;
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String s = in.readLine().trim();
        int L = s.length();
        int[] sign = new int[L];
        for (int i = 0; i < L; i++) {
            int pos = L-1-i;
            sign[i] = (pos%2==0 ? 1 : -1);
        }

        int[][][] dp = new int[L+1][9][11];
        Pre[][][] pre = new Pre[L+1][9][11];
        for (int i = 0; i <= L; i++)
            for (int r9 = 0; r9 < 9; r9++)
                for (int r11 = 0; r11 < 11; r11++)
                    dp[i][r9][r11] = INF;
        dp[0][0][0] = 0;

        for (int i = 0; i < L; i++) {
            int orig = s.charAt(i) - '0';
            for (int r9 = 0; r9 < 9; r9++) {
                for (int r11 = 0; r11 < 11; r11++) {
                    if (dp[i][r9][r11] == INF) continue;
                    for (int d = 0; d <= 9; d++) {
                        if (i==0 && d==0) continue;
                        if (i==L-1 && d!=0 && d!=5) continue;
                        int nr9 = (r9 + d) % 9;
                        int nr11 = (r11 + sign[i]*d % 11 + 11) % 11;
                        int cost = dp[i][r9][r11] + (d != orig ? 1 : 0);
                        if (cost < dp[i+1][nr9][nr11]) {
                            dp[i+1][nr9][nr11] = cost;
                            pre[i+1][nr9][nr11] = new Pre(r9, r11, d);
                        }
                    }
                }
            }
        }

        int ans = dp[L][0][0];
        System.out.println(ans);

        char[] res = new char[L];
        int cr9 = 0, cr11 = 0;
        for (int i = L; i > 0; i--) {
            Pre p = pre[i][cr9][cr11];
            res[i-1] = (char)('0' + p.d);
            cr9 = p.r9; cr11 = p.r11;
        }
        System.out.println(new String(res));
    }

    static class Pre {
        int r9, r11, d;
        Pre(int _r9, int _r11, int _d) { r9=_r9; r11=_r11; d=_d; }
    }
}

C++ 版本

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
struct Pre { int r9, r11, d; };

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    int L = s.size();
    vector<int> sign(L);
    for(int i=0; i<L; i++){
        int pos = L-1-i;
        sign[i] = (pos%2==0 ? +1 : -1);
    }

    static int dp[20][9][11];
    static Pre pre[20][9][11];
    for(int i=0; i<=L; i++)
        for(int a=0; a<9; a++)
            for(int b=0; b<11; b++)
                dp[i][a][b] = INF;
    dp[0][0][0] = 0;

    for(int i=0; i<L; i++){
        int orig = s[i]-'0';
        for(int r9=0; r9<9; r9++){
            for(int r11=0; r11<11; r11++){
                if(dp[i][r9][r11]==INF) continue;
                for(int d=0; d<=9; d++){
                    if(i==0 && d==0) continue;
                    if(i==L-1 && d!=0 && d!=5) continue;
                    int nr9  = (r9 + d) % 9;
                    int nr11 = (r11 + sign[i]*d % 11 + 11) % 11;
                    int cost = dp[i][r9][r11] + (d!=orig);
                    if(cost < dp[i+1][nr9][nr11]){
                        dp[i+1][nr9][nr11] = cost;
                        pre[i+1][nr9][nr11] = {r9, r11, d};
                    }
                }
            }
        }
    }

    int ans = dp[L][0][0];
    cout << ans << "\n";
    string t(L,'0');
    int cr9=0, cr11=0;
    for(int i=L; i>0; i--){
        auto &p = pre[i][cr9][cr11];
        t[i-1] = char('0'+p.d);
        cr9  = p.r9;
        cr11 = p.r11;
    }
    cout << t << "\n";
    return 0;
}

题目内容

小红来到了红魔馆。众所周知，红魔馆的馆主是一只$495$岁的吸血鬼，所以她非常喜欢$495$这个数。现在，小红拿到了一个正整数$n$，她想选择$n$的某几位,然后依次将每一位数字改变成'$0$'到'$9$',中的一个,但是不允许出现前导零。

她想要使得该数字变成$495$的倍数,请你计算最少需要改变的位数(可以不改变),并给出改变后的数.

输入描述

在一行上输入一个正整数$n(100≤n≤10^{18})$，表示原始数字

输出描述

一行输出一个整数，代表需要改变的最少位数。

第二行输出改变后的数。

样例1

输入

195

输出

1
495

样例2

输入

1145

输出

2
1485

样例3

输入

495

输出

0
495