侧边栏壁纸
博主头像
GabrielxD

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

  • 累计撰写 628 篇文章
  • 累计创建 127 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【DFS, 枚举】带分数

GabrielxD
2023-02-20 / 0 评论 / 0 点赞 / 16 阅读 / 769 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2023-02-20,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

1209. 带分数 - AcWing题库


100100 可以表示为带分数的形式: 100=3+69258714100 = 3 + \frac{69258}{714}

还可以表示为: 100=82+3546197100 = 82 + \frac{3546}{197}

注意特征:带分数中,数字 191 \sim 9 分别出现且只出现一次(不包含 00 )。

类似这样的带分数, 1001001111 种表示法。

输入格式

一个正整数。

输出格式

输出输入数字用数码 191 \sim 9 不重复不遗漏地组成带分数表示的全部种数。

数据范围

1N<1061 \le N < 10^6

输入样例1:

100

输出样例1:

11

输入样例2:

105

输出样例2:

6

解题

方法一:DFS 枚举

思路

朴素思路

带分数的形式为:n=a+bcn = a + \frac{b}{c}

  1. 首先深搜 191 \sim 9 的全排列。
  2. 枚举三个数的两个分割线(每个数至少要有一位)。
  3. 判断分出的 a,b,ca, b , c 三个数是否为合法的带分数形式,如果是就增加计数,否则继续下一个排列。

代码

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

public class Main {
    static int N = 9, n;
    static int[] a = new int[N];
    static boolean[] used = new boolean[N + 1];
    static int ans = 0;
    
    // 全排列
    static void dfs(int curr) {
        if (curr == N) {
            clac();
            return;
        }
        for (int i = 1; i <= N; ++i) {
            if (!used[i]) {
                a[curr] = i;
                used[i] = true;
                dfs(curr + 1);
                used[i] = false;
            }
        }
    }
    
    static int build(int l, int r) {
        int res = 0;
        for (int i = l; i < r; ++i) res = res * 10 + a[i];
        return res;
    }
    
    // 枚举两个分割线并分割出数字、检查带分数是否合法
    static void clac() {
        for (int i = 1; i < N - 1; ++i) {
            for (int j = i + 1; j < N; ++j) {
                int a = build(0, i);
                if (a > n) continue;
                int b = build(i, j), c = build(j, N);
                if (b % c != 0) continue;
                if (a + b / c == n) ++ans;
            }
        }
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        n = (int) in.nval;
        dfs(0);
        System.out.println(ans);
    }
}

优化:

n=a+bcb=c(an)n = a + \frac{b}{c} \Longrightarrow b = c(a - n)

我们只需要枚举 a,ca, c ,然后求出 bb 并验证等式是否成立即可。

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

public class Main {
    static final int N = 9;
    static int n, ans;
    static boolean[] used = new boolean[N + 1];
    
    static boolean check(int a, int c) {
        int b = c * (n - a);
        if (a <= 0 || b <= 0 || c <= 0) return false;
        boolean[] has = used.clone();
        int tmp = b;
        while (b > 0) {
            int x = b % 10;
            b /= 10;
            if (x == 0 || has[x]) return false;
            has[x] = true;
        }
        for (int i = 1; i <= N; ++i) {
            if (!has[i]) return false;
        }
        return true;
    }
    
    static void dfsC(int a, int c) {
        if (check(a, c)) ++ans;
        for (int i = 1; i <= N; ++i) {
            if (!used[i]) {
                used[i] = true;
                dfsC(a, c * 10 + i);
                used[i] = false;
            }
        }
    }
    
    static void dfsA(int a) {
        if (a >= n) return;
        dfsC(a, 0);
        for (int i = 1; i <= N; ++i) {
            if (!used[i]) {
                used[i] = true;
                dfsA(a * 10 + i);
                used[i] = false;
            }
        }
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        n = (int) in.nval;
        dfsA(0);
        System.out.println(ans);
    }
}
0

评论区