问题描述
100 可以表示为带分数的形式：100=3+69258/714
还可以表示为：100=82+3546/197
注意特征：带分数中，数字 1∼9 分别出现且只出现一次（不包含 0）。
类似这样的带分数，100 有 11 种表示法。
输入格式
一个正整数。
输出格式
输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。
数据范围
1≤N<106
输入样例1：
100
输出样例1：
11
输入样例2：
105
输出样例2：
6
暴力法
#include <bits/stdc++.h> using namespace std; int n; const int N = 10; int res[N]; //存储结果 bool st[N]; //表示元素是否用过 int cnt = 0; //计算每一段的总数 int calc(int l, int r) { int num = 0; for (int i = l; i <= r; i++) { num = num * 10 + res[i]; } return num; } //将全排列的数组分成三段进行判断 void dfs(int k) { if (k == 9) { for (int i = 0; i < 7; i++) { for (int j = i + 1; j < 8; j++) { int a = calc(0, i); int b = calc(i + 1, j); int c = calc(j + 1, 8); if (a * c + b == n * c) //c++中除法是整除，所以要转换为乘法 cnt++; } } return; } //进行全排列 for (int i = 1; i <= 9; i++) { if (!st[i]) { st[i] = true; res[k] = i; dfs(k + 1); st[i] = false; } } } int main() { cin >> n; dfs(0); cout << cnt << endl; return 0; }
暴力法（内置函数）
next_permutation() 蓝桥杯允许使用
#include<bits/stdc++.h> using namespace std; int n; const int N=10; int res[N]; //存储结果 int cnt=0; //计算每一段的总数 int calc(int l,int r) { int num=0; for(int i=l;i<=r;i++) { num=num*10+res[i]; } return num; } int main() { cin>>n; for(int i=0;i<9;i++) res[i]=i+1; do{ for(int i=0;i<7;i++) { for(int j=i+1;j<8;j++) { int a=calc(0,i); int b=calc(i+1,j); int c=calc(j+1,8); if(a*c+b==n*c) cnt++; } } }while(next_permutation(res,res+9)); //调用函数进行全排列 cout<<cnt<<endl; return 0; }
优化
先枚举 a ，再枚举 c ，直接通过 a 和 c 求出 b ，就不用再枚举 b 了。然后判断 b 是否满足要求，如果 b 中的每一位都没有被 a 和 c 所用过并且 1 到 9 都被已经用过了，则满足要求，答案总数加 1。
举个例子，假设 a 枚举到了 82，然后枚举 c，而 c 枚举到了 3456，则去计算 b，根据公式推导，b 等于 n*c-a*c，从而算出 197。接下来就进行判断，首先 abc 都不能为 0 这是肯定的，然后需要判断 b 是否用了剩下没有用过的数字，如果出现了 a 和 c 中的数字则不满足条件，并且 b 要将剩下没用过的数字全部用上才满足条件。
#include <bits/stdc++.h> using namespace std; const int N = 10; int n, ans = 0; bool st[N], backup[N]; //判断是否满足条件 bool check(int a, int c) { //计算b //这里需要long long是因为防止n为10的6次方时与c相乘后爆int，导致b为负数，x也会为负数 //x为负数的话，backup就会数组越界，所以要加long long long long b = n * (long long)c - a * c; //a,b,c都不能为0 if (!b || !a || !c) return false; //因为原状态数组不能改变，为了后续判断，就新建一个状态数组用于判断 memcpy(backup, st, sizeof(st)); //判断b中的每一位数字 while (b) { int x = b % 10; if (!x || backup[x]) return false; b /= 10; backup[x] = true; } //判断是否1-9都使用过 for (int i = 1; i <= 9; i++) { if (!backup[i]) return false; } return true; } //枚举c void dfs_c(int x, int a, int c) { if (x > 9) return; if (check(a, c)) ans++; for (int i = 1; i <= 9; i++) { if (!st[i]) { st[i] = true; dfs_c(x + 1, a, c * 10 + i); st[i] = false; } } } //枚举a void dfs_a(int x, int a) { if (a >= n) return; if (a) dfs_c(x, a, 0); for (int i = 1; i <= 9; i++) { if (!st[i]) { st[i] = true; dfs_a(x + 1, a * 10 + i); st[i] = false; } } } int main() { cin >> n; dfs_a(0, 0); cout << ans << endl; return 0; }
