1209. 带分数

题目：

1209. 带分数 - AcWing题库 

 

思路： 

1.target=a+b/c，由题意a,b,c会包含1~9 且每个数出现且只能出现一次。我们可以抽象化为9个坑位分成3份分别给a,b,c。

2.先采用递归搜索树写出9个坑位的全排列，再分成3个区，分别分给a,b,c。最后对target=a+b/c进行判断，若成立，数量cnt加一。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;const int N = 10;static int target; //题目给出的目标数int kenway[N];//保存全排列的结果bool used[N];//生成全排列过程中标记是否使用过int cnt;//计数，最后输出的结果//计算某一段区间的数
int calc(int l, int r) {int res = 0;for (int i = l; i <= r; i++) {res = res * 10 + kenway[i];}return res;
}//全排列进行分段
static void dfs(int u) {if (u == 10) {//一条分支到了尽头--->对该分支9个坑位分成3个区分别给a,b,cfor (int i = 1; i <=7; i++) {for (int j = i + 1; j <=8; j++) {//分成三个区间(i,j相当于两个隔板)int a = calc(1, i);int b = calc(i + 1, j);int c = calc(j + 1, 9);//判定的话 是对n=a+b/c进行变换得到cn=ac+bif (a * c + b == c * target) cnt++;}}return;}//全排列模板 for (int i = 1; i <= 9; i++) {if (!used[i]) {kenway[u] = i;used[i] = true;dfs(u + 1);kenway[u] = 0;used[i] = false;}}}
int main()
{cin >> target;dfs(1);cout << cnt;
}