AcWing 1209. 带分数
原题链接
简单
作者:
Nmoek
,
2021-02-01 20:27:58
,
所有人可见
,
阅读 323
#include <iostream>
#include <stdio.h>
using namespace std;
int num[9];
bool flag[9];
int n;
int ans;
//将拆分的数位 组装为整数
inline int work(int l, int r)
{
int sum = 0;
for(int i = l;i <= r;i++)
{
sum *= 10;
sum += num[i];
}
return sum;
}
//dfs 暴搜出 1~9的全排列 将全排列 分割组装 去判断是否满足题意
void dfs(int a)
{
if(a == 9)
{
for(int i = 0;i < 7;i++)
{
for(int k = i + 1;k < 8;k++)
{
if(k - i < 9 - i - k - 1)
continue;
int a = work(0, i);
if(a >= n)
continue;
int b = work(i + 1, k);
int c = work(k + 1, 8);
if((n - a) * c == b)
{
ans++;
}
}
}
}
for(int i = 0;i < 9;i++)
{
if(!flag[i])
{
num[a] = i + 1;
flag[i] = true;
dfs(a + 1);
flag[i] = false;
}
}
}
int main()
{
scanf("%d", &n);
dfs(0);
printf("%d\n", ans);
return 0;
}