1209. 带分数
题目链接
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
next_permutation() 函数做法
蓝桥杯2013年第四届真题-带分数
dfs() 递归做法
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>using namespace std;
typedef long long ll;
const int N=15;int n;
bool flag[N]; // 标记数字是否使用过
int res[N]; // 存储数字的全排列
int cnt; // 记录有多少个符合的算式 int sum(int st, int ed)
{
int ans = 0;for(int i = st; i < ed; i ++ )ans = ans * 10 + res[i];return ans;
}void dfs(int u)
{
if(u == 9){
// 第一个数字最多是7位for(int i = 0; i < 7; i ++ ){
// 第二个数字在第一个数字的基础上最多只能是8位，因为第三个数字至少要是1位 for(int j = i + 1; j < 8; j ++ ){
int a = sum(0, i + 1);int b = sum(i + 1, j + 1);int c = sum(j + 1, 9);if(a * c + b == c * n)cnt ++ ;}}return; }for(int i = 1; i <= 9; i ++ ){
if(!flag[i]){
flag[i] = true;res[u] = i;dfs(u + 1);flag[i] = false;}}
}int main()
{
cin >> n;dfs(0);cout << cnt << endl;return 0;
}
dfs() + 剪支
求 b 的时候注意之下转成 ll ，题目的数据范围可能会爆 int
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>using namespace std;
typedef long long ll;
const int N=15;int n;
bool st[N], backup[N];
int ans;bool check(int a, int c)
{
ll b = n * (ll)c - a * c;if(!a || !b || !c) return false;memcpy(backup, st, sizeof st);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;
}void dfs_c(int u, int a, int c)
{
if(u == n) return;if(check(a, c)) ans ++ ;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)
{
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);st[i] = false;}
} int main()
{
cin >> n;// 当前已经用了多少个数 dfs_a(0, 0);cout << ans << endl;return 0;
}