[蓝桥杯 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

1
100

样例输出 #1

1
11

样例 #2

样例输入 #2

1
105

样例输出 #2

1
6

提示

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

题解

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 10;

int n,ans,used[N],cpy[N];

bool check(int a,int c){
    int b = c*(n-a);
    memcpy(cpy,used,sizeof used);
    if(!a || !b || !c || b<0) return false;
    while(b){
        int x = b%10;
        b /= 10;
        if(!x || cpy[x]) return false;
        cpy[x] = 1;
    }
    for(int i=1;i<=9;i++){
        if(!cpy[i]) return false;
    }
    return true;
}

void dfs_c(int u,int a,int c){
    if(u >= 10) return;
    if(check(a,c)) ans++;
    for(int i=1;i<=9;i++){
        if(!used[i]){
            used[i] = 1;
            dfs_c(u+1,a,c*10+i);
            used[i] = 0;
        }
    }
}

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(!used[i]){
            used[i] = 1;
            dfs_a(u+1,a*10+i);
            used[i] = 0;
        }
    }
}

int main(){
    cin >> n;
    dfs_a(0,0);
    cout << ans << endl;
    return 0;
}

概述

  • 这个题的考点主要是DFS的运用，此题是DFS嵌套DFS。
  • 坑点：在check代码中，b可能越int界成负数，用负数去跑数组是 Undefined Behaviour (UB) 的，所以要特判一下。这个实在坑了我好长时间。