AcWing 1209. 带分数
原题链接
简单
作者:
不知名的fE
,
2024-11-20 18:27:25
,
所有人可见
,
阅读 1
import java.util.*;
public class Main {
static int n, ans;
static int[] a = new int[10];
static boolean[] st = new boolean[10];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
dfs(0);
System.out.println(ans);
}
/**
* u从0开始
* i隔板要从1开始到7结束:隔板不能重合i隔板要在j隔板前面
* j隔板从i隔板后一个位置开始,到8结束,不有有数为null
*/
static void dfs(int u) {
if (u == 9) {
for (int i = 1; i < 8; i++) {
//采用两个隔板的方式将全排列分为三个数
int a = getNum(0, i);
if (a > n) break;
for (int j = i + 1; j < 9; j++) {
int b = getNum(i, j), c = getNum(j, 9);
if (a * c + b == c * n) ans ++;//a + b / c == n转为惩罚
}
}
return;
}
//求解全排列
for (int i = 1; i <= 9; i++)
if (!st[i]) {
a[u] = i;
st[i] = true;
dfs(u + 1);
st[i] = false;
}
}
/**
* 返回a[l, r - 1]的数值,满足高低位,对于本题也可以直接从高位开始算
* 因为全排列会枚举每一个状态
*/
static int getNum(int l, int r) {
int res = 0, cur = 1;
for (int i = r - 1; i >= l; i--) {
res += cur * a[i];
cur *= 10;
}
return res;
}
}