AcWing 1209. 带分数——大白话
原题链接
简单
作者:
xyAC
,
2024-03-14 22:13:35
,
所有人可见
,
阅读 13
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 20;
int n;
bool st[N],backup[N];
int res;
bool check(int a,int c) {
int b = n * c - a * c;
if(!a || !b || !c) return false;
// 先将st数组备份一下 然后遍历
memcpy(backup,st,sizeof st);
// 这里是分解b的步骤 判断分解出来的数是否已经被用过
while(b) {
int x = b % 10;
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;
}
// 递归遍历查找c 如果c满足条件的时候,检查a和c 这种情况是否满足
void dfs_c(int u,int a,int c) {
if(u == n) return;
if(check(a,c)) res++; // 如果c满足条件那么可以检查a、c这种情况是否满足条件
for(int i = 1;i <= 9;i++) {
if(!st[i]) {
st[i] = true;
dfs_c(u+1,a,c * 10 + i);
st[i] = false;
}
}
}
// 递归遍历所有的a 如果a满足条件,查找c
void dfs_a(int u,int a) {
if(a >= n) return ;
if(a) dfs_c(u,a,0); // 如果a满足要求 找c
// 便利数字判断是否已经用过
for(int i = 1;i <= 9;i++) {
if(!st[i]) { // 如果还没有有过的话,标记一下,然后将该值加到a上
st[i] = true;
dfs_a(u+1,a*10+i);
st[i] = false; // 用完后记得还回去
}
}
}
int main() {
cin>>n;
dfs_a(0,0);
cout<<res<<endl;
return 0;
}