侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【DFS, 剪枝】数字替换

GabrielxD
2023-03-05 / 0 评论 / 0 点赞 / 111 阅读 / 903 字
温馨提示:
本文最后更新于 2023-03-05,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

4868. 数字替换 - AcWing题库


给定两个整数 n,xn,x

你可以对 xx 进行任意次以下操作:

  • 选择 xx 的一位数字 yy ,将 xx 替换为 x×yx \times y

请你计算通过使用上述操作,将 xx 变为一个 nn 位数字(不含前导 00 ),所需要的最少操作次数。

例如,当 n=3,x=2n=3,x=2 时,对 22 进行如下 44 次操作,即可使其变为 33 位数字:

  1. 22 替换为 2×2=42 \times 2 = 4
  2. 44 替换为 4×4=164 \times 4 = 16
  3. 1616 替换为 16×6=9616 \times 6 = 96
  4. 9696 替换为 96×9=86496 \times 9 = 864

输入格式

共一行,包含两个整数 n,xn,x

输出格式

一个整数,表示将 xx 变为一个 nn 位数字,所需要的最少操作次数。

如果无解,则输出 -1

数据范围

所有测试点满足 2n192 \le n \le 191x<10n11 \le x < 10^{n-1}

输入样例1:

2 1

输出样例1:

-1

输入样例2:

3 2

输出样例2:

4

输入样例3:

13 42

输出样例3:

12

解题

方法一:DFS 剪枝

思路

本题中 xx 最大有 1818 位数,肯定会爆 int ,所以用 long 来存,而最多需要该数变为 1919 位,也就是说该数最大会变为 999999999999999999×9=89999999999999999919×10192631(9.2×1019)999999999999999999 \times 9 = 8999999999999999991 \approx 9\times 10^{19} \le 2^{63} - 1 (\approx 9.2 \times 10^{19}) 不会爆 long ,刚刚好能存下。

暴搜:dfs(x,step)dfs(x, step)xx 表示当前数字, stepstep 表示当前已进行了多少步操作 )

  • 枚举 xx 的每一位并计数。
  • 出口:当 xx 的位数等于 nn 时,已达到要求,更新最少操作步数,退出。
  • 枚举 xx 所有位上有的数字,递归下一步操作 dfs(x×d,step+1)dfs(x \times d, step + 1)

剪枝:

  1. 优化搜索顺序:xx 乘以越大的数越容易使 xx 的位数增加,所以枚举位数的时候应按照 929 \to 2 的顺序来枚举。
  2. 最优性剪枝:如果 操作步数 ++ 距离目标相差的位数 \ge 最少操作步数,就应该直接剪枝。

注意:本题时间复杂度比较极限,且输入数字大过 101410^{14} ,所以使用StringTokenizer输入。

代码

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

public class Main {
    static final int INF = 100;
    static int n, ans = INF;
    
    static void dfs(long x, int step) {
        boolean[] has = new boolean[10];
        int cnt = 0;
        for (long t = x; t > 0; t /= 10) {
            has[(int) (t % 10)] = true;
            ++cnt;
        }
        if (step + n - cnt >= ans) return;
        if (cnt == n) {
            ans = step;
            return;
        }
        for (int d = 9; d >= 2; --d) {
            if (has[d]) dfs(x * d, step + 1);
        }
    }
    
    public static void main(String[] args) {
        Kattio io = new Kattio();
        n = io.nextInt();
        long x = io.nextLong();
        dfs(x, 0);
        io.println(ans == INF ? -1 : ans);
        io.flush();
    }

    static class Kattio extends PrintWriter {
        private BufferedReader r;
        private StringTokenizer st;
        public Kattio() { this(System.in, System.out); }
        public Kattio(InputStream i, OutputStream o) {
            super(o);
            r = new BufferedReader(new InputStreamReader(i));
        }
        public Kattio(String intput, String output) throws IOException {
            super(output);
            r = new BufferedReader(new FileReader(intput));
        }
        public String next() {
            try {
                while (st == null || !st.hasMoreTokens())
                    st = new StringTokenizer(r.readLine());
                return st.nextToken();
            } catch (Exception e) { }
            return null;
        }
        public int nextInt() { return Integer.parseInt(next()); }
        public double nextDouble() { return Double.parseDouble(next()); }
        public long nextLong() { return Long.parseLong(next()); }
    }
}
0

评论区