acwing1209.带分数暴力与优化(java版)

//n = a + b / c     n是确定的,只需找到其中两个。判断剩下一个数是否满足条件即可
//由题目条件可知,每个数不能重复使用,需要一个st全局数组判断每个数是否使用过
//递归实现排列型枚举,cn = ac + b
//对于枚举出来的每一个a,再去枚举每一个c,再在c的枚举里判断b是否满足条件
//dfs_a() 需要传入一个u,和a,u代表已经用了多少个数,枚举出来的a要作为dfs_c的参数
//在通过ac判断b是否满足条件时,会使用到st数组,需要对st数组进行备份
import java.util.*;
public class Main
{
    static int N = 10;
    static int target;
    static int ans; //表示最终结果
    static boolean[] st = new boolean[10];
    static boolean[] backup = new boolean[N];
    
    //得到a的组合排列,得到的数需要通过 a * 10 + i 来进入下一次循环
    //a的值由循环里的i决定,首次调用要在main函数里调用dfs_a(1,0)
    
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        target = sc.nextInt();
        dfs_a(1,0);
        System.out.print(ans);
    }
    
    public static void dfs_a(int u,int a)
    {
        
        if(a > target) return;
        
        if(a > 0) dfs_c(u,a,0);
        
        for(int i = 1;i <= 9;i ++)
        {
            if(!st[i])
            {
                st[i] = true;
                dfs_a(u + 1, a * 10 + i);
                st[i] = false;
            }
        }
    }
    
    //对于传进来的每一个a,取枚举c,再判断b是否满足条件
    public static void dfs_c(int u, int a, int c)
    {
        
        //a 和 c一共最多用8位
        if(u == 9) return;
        
        //每次调用c,看看传入的c是否满足条件
        if(check(a,c)) ans++;
        
        for(int i = 1;i <= 9;i ++)
        {
            if(!st[i])
            {
                st[i] = true;
                dfs_c(u + 1,a,c * 10 + i);
                st[i] = false;
            }
        }
    }
    
    public static boolean check(int a,int c)
    {
        long b = target * (long) c - a * c;
        if(b == 0 || c == 0) return false;
        //判断b之前,先对st数组进行备份
        backup = st.clone();
        //因为a,c通过同一个st数组枚举出来,因此ac不会重复
        while(b > 0)
        {
            //从最后一位开始,每次取出来判断
            //x是long,需要转成int
            int x = (int)(b % 10);
            b /= 10;
            if(x == 0 || backup[x]) return false;
            backup[x] = true;
        }
        
        //现在所有数已经不重复了,再判断是否所有数都用过
        for(int i = 1;i <= 9;i ++)
        {
            if(!backup[i]) return false;
        }
        return true;
    }
}

更改:check函数里要多判断 b < 0

法二:暴力枚举

//枚举9个数的全排列
//再拆分判断

import java.util.*;
public class Main
{
    static int target;  //输入样例
    static int N = 10;
    static int[] data = new int[N]; //存储全排列结果
    static boolean[] used = new boolean[N];
    static int cnt;    //输出结果

    public static int cal(int l ,int r)
    {
        int sum = 0;
        for(int i = l;i <= r;i++)
        {
            sum = sum * 10 + data[i];
        }
        return sum;
    }

    public static void dfs(int u)
    {

        if(u > 9)
        {
            for(int i = 1;i <= 7;i++)
            {
                for(int j = i + 1;j <= 8;j ++)
                {
                    int a = cal(1,i);
                    int b = cal(i + 1,j);
                    int c = cal(j + 1,9);
                    if(a * c + b == c * target) cnt++;
                }
            }
        }

        for(int i = 1;i <= 9;i++)
        {
            if(!used[i])
            {
                used[i] = true;
                data[u] = i;
                dfs(u + 1);
                used[i] = false;
            }
        }
    }
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        target = sc.nextInt();
        dfs(1);
        System.out.print(cnt);
    }
}