AcWing 1209. 带分数
原题链接
简单
作者:
cyb-包子
,
2020-10-10 17:21:10
,
所有人可见
,
阅读 332
import java.util.Scanner;
/**
*
*
* 带分数
* @author vccyb
*
*/
/**
* 100 可以表示为带分数的形式:100=3+69258/714
还可以表示为:100=82+3546/197
注意特征:带分数中,数字 1∼9 分别出现且只出现一次(不包含 0)。
类似这样的带分数,100 有 11 种表示法。
*
*
* @author vccyb
*
*/
public class Main {
static final 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){
//分成三段
// a b c
//
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);
if(a*c+b == c * target){cnt++;}
}
}
return;
}
//继续搜索
for(int i=1;i<=9;i++){
if(!used[i]){
used[i] = true; //标记使用了
num[u] = i;
dfs(u+1);
used[i] = false; //还原
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
target = sc.nextInt();
dfs(0);
System.out.println(cnt);
}
}
static int[] num = new int[N];
static boolean[] used = new boolean[N];
static void dfs(int u){
if(u>n){
xxx // check 或者是别的代码
}
for(int i=1;i<=n;i++){
if(!used[i]){
used[i] = true; //标记使用了
num[u] = i;
dfs(u+1);
used[i] = false; //还原
}
}
}