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

[蓝桥杯 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 
#include 
#include 
#include 
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 
#include 
#include 
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，不能return
    
    for (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;
}