第四届蓝桥杯省赛C++B/C组----带分数
思路:
1.先枚举全排列
2.枚举位数
3.判断是否满足要求
这道题也就是n=a+b/c,求出符合要求的abc的方案数。进行优化时,可以对等式进行改写,改写成:b=cn-ca。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 30;
int target,ans = 0;
bool had_use[N],ever[N];
bool check(int a, int c)
{
int b = c*target - c*a; //写出式子,算出b
if (!a || !b || !c) return false;
memcpy(ever, had_use, sizeof had_use); //拷贝had_use数组给ever,这样能不改变原来的数组
while (b)
{
int t = b % 10;
if (!t || ever[t]) return false;
ever[t] = true;
b /= 10;
}
for (int i = 1; i <= 9; i++)//判断1-9每个数字有没有都被用到
if (!ever[i]) return false;
return true;
}
void dfs_c(int x, int a, int c)//x表示用了多少个数字,a表示枚举的a的大小,c表示c的大小
{
if (x >= 10) return;//如果1-9全部都已经被枚举了,则退出
if (check(a,c)) ans++; //检验a和c是否满足要求,满足则方案书+1
for (int i = 1; i <= 9; i++)
{
if (!had_use[i])
{
had_use[i] = true;
dfs_c(x+1, a, c*10+i);
had_use[i] = false;
}
}
}
void dfs_a(int u, int a)//u表示枚举到第几个位置,也就是用了多少个数字,t表示当前的a是多少
{
if (a >= target) return;
if (a) dfs_c(u, a, 0); //如果a满足要求,则对c进行枚举
for (int i = 1; i <= 9; i++)
{
if (!had_use[i])
{
had_use[i] = true;
dfs_a(u+1, a * 10 + i);//将i加在a的各位
had_use[i] = false; //回溯,恢复现场
}
}
}
int main()
{
scanf("%d", &target);
dfs_a(0,0); //先枚举a
printf("%d", ans);
return 0;
}