算法1
思路:
这个题真的做了好久,看闫总讲完之后,懵逼状态,重新看了一遍才明白是什么意思
看到这个题,第一反应是难,写的时候感觉更难,不过弄懂之后,就没有那么可怕了,首先代数表达上面式子是n=a+b/c,题目需要我们输入n,另外还有三个未知数,我们枚举其中a,c,然后用n,a,c,求出的b,看是否满足题目条件
整体
1.枚举全排列
2.枚举位数(这里是变量a,c)
3.判断等式是否相等
局部
1.需要两个dfs来枚举,一个枚举a,一个枚举c
2.判断是否成立
C++ 代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=10;
int n;//输入的数字
bool st[N];
int ans;//答案
bool backup[N];
bool check(int a,int c){
long long b=n*(long long)c-a*c;//这里注意long long,因为n*c超过了int类型
if(!a || !b ||!c) return false;//a,b,c都不满足要求,直接返回
memcpy(backup ,st,sizeof st);//由于我们需要更改b,把b中每一个元素抽取出来,将b copy到backup数组里面
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])//如果数字不满足条件,false
return false;
}
return true;
}
void dfs_c (int u,int a,int c){
if(u>9) return ;
if(check(a,c)) ans++;//这里把a,c枚举的结果放到check()中,判断b是否满足条件
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 ){//u表示当前已经用了几个数字
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);//a*10+i比较难理解,相当于a=12,下一步如果a全排列为123,则需要a*10+3
st[i]=false;//返回上一步
}
}
}
int main(){
scanf("%d",&n);
dfs_a(0,0);// u表示当前数字,0表示当前a还没有值
printf("%d\n",ans);
return 0;
}