[蓝桥杯 2013 省 B] 带分数
题目描述
100 100 100 可以表示为带分数的形式: 100 = 3 + 69258 714 100 = 3 + \frac{69258}{714} 100=3+71469258。
还可以表示为: 100 = 82 + 3546 197 100 = 82 + \frac{3546}{197} 100=82+1973546。
注意特征:带分数中,数字 1 1 1 ~ 9 9 9 分别出现且只出现一次(不包含 0 0 0)。
类似这样的带分数, 100 100 100 有 11 11 11 种表示法。
输入格式
从标准输入读入一个正整数 N ( N < 1 0 6 ) N(N<10^6) N(N<106)。
输出格式
程序输出数字 N N N 用数码 1 1 1 ~ 9 9 9 不重复不遗漏地组成带分数表示的全部种数。
注意:不要求输出每个表示,只统计有多少表示法!
样例 #1
样例输入 #1
100
样例输出 #1
11
样例 #2
样例输入 #2
105
样例输出 #2
6
提示
原题时限 3 秒, 64M。蓝桥杯 2013 年第四届省赛
暴力做法
要保证1~9这每个数都要出现,且仅出现一次,可以联想到AcWing 842. 排列数字该暴力解法,就是在排列数字的基础上,将9个数的自由排列先求出来,然后根据式子
n = a + b c n = a + \frac{b}{c} n=a+cb
的基础上,枚举每一个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 O_2 O2优化,不然超过1s了TLE
嵌套dfs
首先通过传入参数的形式将a, c的值求出来,减少了多次求的运算过程,通过先dfs_a, 中嵌套dfs_c,枚举所有结果,用check进行剪枝,来加快处理速度。
b = n( 1 0 6 10^6 106) * c(10^6) 爆int( 1 0 10 10^{10} 1010)了,所以要用 l o n g l o n g long long 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;
}