AcWing 1209. 带分数
原题链接
简单
作者:
LaoHiu
,
2024-03-04 17:40:14
,
所有人可见
,
阅读 21
#include <bits/stdc++.h>
using namespace std;
const int N = 15;
int target; // 题目给出的目标数
int num[N]; // 保存全排列的结果
bool used[N]; // 生成全排列过程中标记是否使用过
int cnt; // 计数,最后输出的结果
// 计算num数组中一段的数是多少
int calc(int l,int r)
{
int res = 0;
for(int i = l;i<=r;i++)
{
res = res*10+num[i];
}
return res;
}
// 生成全排列
// 当全排列生成后进行分段
void dfs(int u)
{
// 用两层循环分成三段
if(u > 9)
{
for(int i = 1;i <= 7;i++)
{
for(int j = i + 1;j <= 8; j++)
{
int a = calc(1,i);
int b = calc(i + 1, j);
int c = calc(j + 1, 9);
// 注意判断条件,因为C++中除法是整除,所以要转化为加减乘来计算
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);
used[i] = false;
}
}
}
int main()
{
scanf("%d",&target);
dfs(1);
printf("%d",cnt);
return 0;
}