【DFS, 枚举】带分数

题目

1209. 带分数 - AcWing题库

---

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

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

注意特征：带分数中，数字 $1 \sim 9$ 分别出现且只出现一次（不包含 $0$ ）。

类似这样的带分数， $100$ 有 $11$ 种表示法。

输入格式

一个正整数。

输出格式

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

数据范围

$1 \le N < 10^6$

输入样例1：

100

输出样例1：

11

输入样例2：

105

输出样例2：

6

解题

方法一：DFS 枚举

思路

朴素思路

带分数的形式为：$n = a + \frac{b}{c}$ 。

1. 首先深搜 $1 \sim 9$ 的全排列。
2. 枚举三个数的两个分割线（每个数至少要有一位）。
3. 判断分出的 $a, 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 + \frac{b}{c} \Longrightarrow b = c(a - n)$ 。

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

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);
    }
}