AcWing 1209. 带分数_dfs全排列(Java)
原题链接
简单
作者:
差一点睡死了
,
2021-02-10 15:13:20
,
所有人可见
,
阅读 1367
带分数_dfs全排列
package lanqiao;
import java.util.Scanner;
public class _1209_带分数_dfs全排列 {
static int N=10;
static int target; //题目给出的目标数
static int num[]=new int[N]; //保存全排列的结果
static boolean[] used=new boolean[N];//生成全排列过程中标记是否使用过
static int cnt;//计数,最后输出的结果
//计算某一段区间的数
static int calc(int l,int r) {
int res=0;
for(int i=l;i<=r;i++) {
res=res*10+num[i];
}
return res;
}
//全排列进行分段
static void dfs(int u) {
if(u==9) {
for (int i = 0; i <7; i++) {
for (int j =i+1; j <8; j++) {
//分成三个区间
int a=calc(0,i);
int b=calc(i+1,j);
int c=calc(j+1,8);
//判定的话 是对n=a+b/c进行变换得到cn=ac+b
if(a*c+b==c*target) cnt++;
}
}
}
//全排列模板
for (int i =1; i <=9; i++) {
if(!used[i]) {
used[i]=true;
num[u]=i;
dfs(u+1);
num[u]=0;
used[i]=false;
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
target = sc.nextInt();
dfs(0);
System.out.println(cnt);
}
}