洛谷P8599 [蓝桥杯 2013 省 B] 带分数

[蓝桥杯 2013 省 B] 带分数

题目描述

$100$ 可以表示为带分数的形式：$100=3+\frac{69258}{714}$。

还可以表示为：$100=82+\frac{3546}{197}$。

注意特征：带分数中，数字 $1$ ~ $9$ 分别出现且只出现一次（不包含 $0$）。

类似这样的带分数，$100$ 有 $11$ 种表示法。

输入格式

从标准输入读入一个正整数 $N(N<10^6)$。

输出格式

程序输出数字 $N$ 用数码 $1$ ~ $9$ 不重复不遗漏地组成带分数表示的全部种数。

注意：不要求输出每个表示，只统计有多少表示法！

样例 #1

样例输入 #1

100

样例输出 #1

11

样例 #2

样例输入 #2

105

样例输出 #2

6

提示

原题时限 3 秒, 64M。蓝桥杯 2013 年第四届省赛

暴力做法

要保证1~9这每个数都要出现，且仅出现一次，可以联想到AcWing 842. 排列数字该暴力解法，就是在排列数字的基础上，将9个数的自由排列先求出来，然后根据式子
$$n=a+\frac{b}{c}$$
的基础上，枚举每一个a, b的位数，双重循环，c的位数可以由9 - a - b求出，通过get_value函数将每个求出来，再验证式子是否正确，由于c++中的除法是取整后的结果，所以要转换成乘法在进行验证。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <math.h>
using namespace std;const int N = 15;int path[N];//九个数的自由排列结果
bool st[N];
int n, res = 0;int get_value(int k, int c){// k为起始下标，c为总位数int res = 0;for (int i = 0; i < c; i ++){res += path[k + i] * pow(10, c - i - 1);}return res;
}void dfs(int k){if (k == 9){for (int i = 1; i < 9; i ++){int a = get_value(0, i);if (a > n) break;//a如果大于n就一定等式不成立，提前剪枝for (int j = 1; j < 9 - i; j ++){int k = 9 - i - j;if (k <= 0) break;else{int b = get_value(i, j);int c = get_value(i + j, k);if (n * c == a * c + b ){//这里必须要变形成乘法形式，因为除法是取整除法会导致答案过多res ++;}}}}return;}for (int i = 1; i <= 9; i ++){if (!st[i]){st[i] = true;path[k] = i;dfs(k + 1);st[i] = false;}}
}int main(){scanf("%d", &n);dfs(0);printf("%d", res);return 0;
}

要开$O_2$优化，不然超过1s了TLE

嵌套dfs

首先通过传入参数的形式将a, c的值求出来，减少了多次求的运算过程，通过先dfs_a, 中嵌套dfs_c，枚举所有结果，用check进行剪枝，来加快处理速度。
b = n($10^6$) * c(10^6) 爆int($10^{10}$)了，所以要用$longlong$来存b

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 20;
typedef long long LL;bool st[N], backup[N];
int n, res = 0;bool check(int a, int c){//判断当前a, c是否满足题目的要求LL b = n * (LL)c - a * c;if (!a || !b || !c) return false; //当a, b, c为零时不满足，边界特判memcpy(backup, st, sizeof st);//由于b中的数字可能重复，所以需要改变st中的值判断重复，但这影响了st，所以要先复制while (b){//将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 k, int a, int c){if(k == n) return;if (check(a, c)) res ++;//当前c不满足，也要接着后面代码找下一个c，不能returnfor (int i = 1; i <= 9; i ++){if (!st[i]){st[i] = true;dfs_c(k + 1, a, c * 10 + i);st[i] = false;}}
}void dfs_a(int k, int a){if (a > n) return;dfs_c(k, a, 0);for (int i = 1; i <= 9; i ++){if (!st[i]){st[i] = true;dfs_a(k + 1, a * 10 + i);st[i] = false;}}
}int main(){scanf("%d", &n);dfs_a(0, 0);//枚举到第几位，a的值为多少printf("%d\n", res);return 0;
}