蓝桥杯-带分数
100 可以表示为带分数的形式：100 = 3 + 69258/714
还可以表示为：100 = 82 + 3546 / 197
注意特征：带分数中，数字 1∼9 分别出现且只出现一次（不包含 0）。
类似这样的带分数，100 有 11 种表示法。
输入格式
一个正整数。
输出格式
输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。
数据范围
1≤N<1e6
输入样例1：
100
输出样例1：
11
输入样例2：
105
输出样例2：
6
题解:
- 枚举所有 a 的情况, 在每种 a 的前提下, 再枚举所有 c 的情况
- 根据 a, c, n 计算出 b
- 判断是否满足 [1, 9] 仅出现过一次, 且 a, b, c中不含有0
代码并不是很长, 去除空行大概有五十行, 大家耐心看, 代码中有很多注释, 如果有不理解的地方可以再问~
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int n, ans;
bool st[N], back[N];
bool check(int a, int c)
{
int b = n * c - a * c; // 公式: n = a + b / c ==> b = n * c - a * c
if (!a || !b || !c) return false; // 会把 a b c 任意一个等于 0 的情况给筛掉
memcpy(back, st, sizeof st); // 赋值st的状态, 用于判断 [1, 9] 是否全出现过
while (b)
{
int x = b % 10; // 取个位
b /= 10; // 个位删掉
if (!x || back[x]) return false; // 保证 b 中不含 0, 同时 保证 [1, 9] 只出现过一次
back[x] = true;
}
for (int i = 1; i <= 9; i ++) if (back[i] == false) return false;
return true;
}
void dfs_c(int u, int a, int c)
{
if (check(a, c)) ans ++; // 这里同样可以不用管 c 是否为 0, check函数中有 处理 c 等于 0 的情况
for (int i = 1; i <= 9; i ++)
{
if (st[i]) continue;
st[i] = true;
dfs_c(u + 1, a, c * 10 + i);
st[i] = false;
}
}
void dfs_a(int u, int a) // 枚举 a 的所有可以能 (1, 12, 123, ... 987654321)
{
if (a > n) return; // 剪枝, a > n的时候 b,c没有满足条件的值 (没有这个也不会死循环, 有这个可以减少代码运行的时间)
if(a != 0) dfs_c(u, a, 0); // 这和判断可以写, 也可以不写, 写的话运行时间会快一些, 不写的话在check函数中对 等于 0 进行的处理
for (int i = 1; i <= 9; i ++)
{
if (st[i]) continue;
st[i] = true;
dfs_a(u + 1, a * 10 + i);
st[i] = false;
}
}
int main()
{
cin >> n;
dfs_a(0, 0);
cout << ans << endl;
return 0;
}
觉得写的不错的话, 点个赞吧~