蓝桥杯4届真题-带分数（全排列枚举、递归）

文章目录

• 前言
• 题目
• 题解
• 思路
• 解法：递归、全排列枚举

前言

个人算法精简汇总：个人算法题精简导航整理(精炼汇总，含知识点、模板题、题单)

所有博客文件目录索引：博客目录索引(持续更新)

本题为蓝桥杯第4届省赛真题。

标签：全排列、递归

蓝桥杯第4届省赛真题及题解可见个人博客：暂无

本题在线OJ平台：蓝桥杯官网在线OJ-带分数、acwing OJ平台-带分数

题目

题解

思路

我们令：n=a+b/c，根据题目要求说一组带分数里数字 1∼9分别出现且只出现一次，那么我们可以实际将这三个部分a、b、c连接起来形成一个数，对这一个数进行排列型枚举。

• 若是纯暴力，也就是对三个数分别进行排列型枚举，那么这个时间复杂度为O(9!*9!*9!)，尽管中间加一些剪枝也会直接tle。

确定优化方案就是对一组数进行排列型枚举，那么此时时间复杂度为O(9!)，为36万，可以进行AC。

这里的难点就是将一组数全排列来进行拆分写法，还有中间的一些小细节。

解法：递归、全排列枚举

复杂度分析：时间复杂度O()

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

public class Main {

    static final Scanner cin = new Scanner(System.in);
    static int[] state = new int[10];
    static boolean[] v = new boolean[10];
    //读入目标值及结果集
    static int n, ans;

    //检测a、b、c是否符合条件
    public static boolean check (int a, int c) {
        //根据a、c推出b（b可能是负数）
        int b = n * c - a * c;
        if (b <= 0) return false;
        boolean[] temp = v.clone();
        while (b != 0) {
            int x = b % 10;
            if (x == 0 || temp[x]) return false;
            temp[x] = true;
            b /= 10;
        }
        //遍历一遍访问数组
        for (int i = 1; i <= 9; i ++) {
            if (!temp[i]) return false;
        }
        return true;
    }

    //枚举c
    public static void dfs_c (int u, int a, int c) {
        //全排列终止情况（枚举到最后的话，此时b肯定无任何数则是有问题的）
        if (u == 9) return;
        //有了a与c，那么此时就可以推出b
        if (c != 0 && check(a, c)) ans ++;
        //全排列模板
        for (int i = 1; i <= 9; i ++) {
            if (!v[i]) {
                v[i] = true;
                dfs_c (u + 1, a, c * 10 + i);
                v[i] = false;
            }
        } 
    }

    //枚举a
    public static void dfs_a (int u, int a) {
        //剪枝（由于a是单独的一个值，那么若是a>=n此时就直接结束）
        if (a >= n) return;
        //若是非0，起始第一个情况
        if (a != 0) {
            //枚举c
            dfs_c (u, a, 0);
        }
        //全排列模板
        for (int i = 1; i <= 9; i ++) {
            if (!v[i]) {
                v[i] = true;
                dfs_a (u + 1, a * 10 + i);
                v[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        n = cin.nextInt();
        //递归枚举a
        //a + b / c
        dfs_a (0, 0);
        System.out.println(ans);
    }
}