AcWing 1209. 带分数
原题链接
简单
作者:
光之梦SSS
,
2024-03-04 15:30:42
,
所有人可见
,
阅读 16
代码注释超详细版
import java.io.*;
public class Main {
//in 是用于读取输入的 BufferedReader 对象。
//out 是用于输出的 PrintWriter 对象。
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
//target:存储输入的目标值 ans:存储结果。
static int target, ans;
//path:用于存储当前DFS路径中的数字
static int[] path = new int[10];
//st:用于标记数字是否已经被使用过
//ture:已被使用 false:并未使用
static boolean[] st = new boolean[10];
public static void main(String[] args) throws IOException {
//输入读取目标值 target。
target = Integer.parseInt(in.readLine());
//调用 dfs(1) 开始深度优先搜索
dfs(1);
//输出结果 ans
out.println(ans);
//刷新输出缓冲区
out.flush();
}
//cal 函数用于将数组 path 中的一部分数字拼接成一个整数,并返回这个整数。
//cal(int l, int r) 函数用于计算从路径数组 path 的索引 l 到 r 的数字序列所表示的整数。
public static int cal(int l, int r) {
int res = 0;
//通过循环依次将数字相连
for (int i = l; i <= r; i ++){
//每次将之前的结果乘以10再加上当前数字
//例子: a:12 a——》123 a * 10 + 3
res = res * 10 + path[i];
}
//返回计算结果
return res;
}
//dfs(int u) 是一个递归函数,用于生成数字序列
//参数 u:表示当前处理的数字序列的位置
public static void dfs(int u) {
//在 dfs 函数中 首先判断 u 是否大于9,如果大于9说明已经生成了一个完整的数字序列(长度为9)
if (u > 9) {
//内层循环遍历所有可能的分割点,计算满足条件的情况并更新 ans
//使用两个嵌套的循环来生成所有可能的三个部分的分割点:i 和 j
for (int i = 1; i <= 7; i ++)
for (int j = i + 1; j <= 8; j ++) {
////分别计算出从1到 i、从 i+1 到 j 和从 j+1 到9的三个子序列所表示的整数。
int a = cal(1, i);
int b = cal(i + 1, j);
int c = cal(j + 1, 9);
//如果满足等式 (a * c) + b = c * target,则答案加1。
if ((long)a * c + b == (long)c * target){
ans ++;
}
}
return;
}
//这个部分是回溯算法的核心,通过回溯的方式遍历所有可能性。
//在每个位置处,使用一个 for 循环来遍历可能的数字
//并通过递归的方式继续生成下一个位置的数字,直到生成完整的数字序列。
//当遍历完所有可能的数字时,回退到上一个位置,继续尝试其他可能的数字。
// 该循环用于生成数字序列的所有可能的排列组合
// 递归调用 dfs 函数处理下一个位置 u+1,直到处理完所有的位置
for (int i = 1; i <= 9; i ++) {
//循环变量 i 从1到9遍历每个数字
//如果当前数字 i 在标记数组 st 中为 false,则表示该数字还未被使用过
if (!st[i]) {
//在循环体中首先将标记数组的对应位置 st[i] 设置为 true,表示数字 i 已被使用。
st[i] = true;
//将当前数字 i 存入路径数组的第 u 个位置,表示将当前位置填充为数字 i
path[u] = i;
//递归调用 dfs(u+1),生成下一个位置 u+1 的数字。
dfs(u + 1);
//在递归调用返回之后,将当前数字 i 的标记重新设置为 false
//将路径数组的第 u 个位置重置为0,以便后续的数字填充
st[i] = false;
path[u] = 0;
}
}
}
}
JAVA代码