AcWing 1209. 带分数
原题链接
简单
作者:
满眼星辰_06
,
2024-02-28 10:12:15
,
所有人可见
,
阅读 26
#include<stdio.h>
#include<stdbool.h>
#include<string.h>
#define N 20
//n = a + b / c,可以转换成 b = c * n - c * a
int n,count;
int st[N],backup[N];//backup 是备份数组,因为在check环节如果用原st数组的话,万一b不满足条件,那么对原st数组的破坏是不可逆的,
/*st数组里面的内容是影响着接下来的递归,会对结果造成影响,所以就又用了backup数组做备份*/
bool check(int a,int c)
{
long long b = n * (long long)c - c * a;
if(!a || !b || !c) return false;
memcpy(backup,st,sizeof st);//memcpy(a,b,c),将b数组里面的c个字节长度的内容赋值到a数组里面
while(b)
{
int x = b % 10;//这两步是取出b的每一位
b = b / 10;
if(!x ||backup[x]) return false;
backup[x] = true;
}
for(int i = 1;i <= 9;i++)//遍历一次看看有没有哪个数没有用到
{
if(!backup[i]) return false;
}
return true;
}
void dfs_c(int u,int a,int c)
{
if(u >= 9) return;//由题目知n是最多七位的,那么a也最多七位,如果c占两位的话,b/c一定是个小数,肯定不符合题目定义,所以
//这时候返回
if(check(a,c))
{
count ++;
return;
}
for(int i = 1;i <= 9;i++)
{
if(!st[i])
{
st[i] = true;
dfs_c(u + 1,a,c * 10 + i);
st[i] = false;
}
}
}
void dfs_a(int u,int a)
{
if(a >= n) return;
if(a) dfs_c(u,a,0);
for(int i = 1;i <= 9;i++)
{
if(!st[i])
{
st[i] = true;
dfs_a(u + 1,a * 10 + i);
st[i] = false;
}
}
}
int main()
{
scanf("%d",&n);
dfs_a(0,0);
printf("%d",count);
return 0;
}