0%

蓝桥杯PREV03-带分数

发表于

题目链接

题目概述

一个数 n 可表示为 n = a + c / b ，其中a、b、c中数字1-9分别出现且只出现一次，统计输入值 n 的全部表示方式的数量。

题目分析

由于要求1-9每个数字都要出现一次，那很容易想到采用全排列。关键在于，对于每一种排列，该如何从中选取 a、b、c 三个数。

首先可以确定的是 a<n ，那 a>=n的情况可以一并排除，其次由于 a、b、c、n都是整数，那么 c/a 也要是整数，及 c%b=0 （在这一条件中，已经隐含了 c>=b），这样一来结合剪枝，就能很容易得到答案。

完整代码

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
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int nums[10];
int n;
int ans;

int main(){
    for(int i=1; i<10; i++)
        nums[i]=i;
    cin>>n;

    do{
        int a=0;
        for(int i=1; i<8; i++){ // a
            a=a*10+nums[i];
            if(a>=n)
                break;
            int c=0;
            for(int j=i+1; j<9; j++){ // c
                c=c*10+nums[j];
                int b=0; // b
                for(int k=j+1; k<10; k++)
                    b=b*10+nums[k];
                if(c%b!=0)
                    continue;
                if(a+c/b==n)
                    ans++;
            }
            
        }
    }while(next_permutation(nums+1, nums+10));

    cout<<ans<<endl;
    return 0;
}

自我总结

碰到好几个坑，能反应出不少知识体系和做题思路的问题：

  • 原本把 a=a*10+nums[i] 写成了 a*=10+nums[i] ，以为这两者没有区别，但实际上后者等同于 a=a*(10+nums[i]) ， *= 的优先级比较低。
  • 由于 c>b 的一个充分条件是 c 的长度大于 b ，所以一开始直接在迭代 c 的代码中直接让 c 的长度大于 b ，及写成了 for(int j=i+ceil((9+i)/2.0); j<9; j++) ，但过多的条件使得结果出现了错误。在能选择简单明了的情况下应当避免选择复杂。