题目


分析

参考文献 qingdujun的博客

先说一下自己的思路，数字1-9只能出现一次，所以可以先将1-9进行全排列，然后划分整数，分子和分母。

然后问题就来了，之前写过一道全排列，当时是用了N重for循环嵌套，想想都觉得恶心。后来在网上看大神的解法，可以用字典序或递归，觉得字典序比较复杂，就只看了递归的方法，下面贴上代码。

全排列

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
int list[9]={1,2,3,4,5,6,7,8,9};
inline void Swap(int &a,int &b)
{
  int c=a;
  a=b;
  b=c;
}
void Perm(int list[],int k,int m)
{
  if(k==m-1)
  {
    for(int i=0;i<m;i++)
      printf("%d",list[i]); //当前找出一种全排列
    printf("\n");
  }
  else
  {
    for(int i=k;i<m;i++)
    {
       //第k层递归，排列第k位可能的值
      Swap(list[k],list[i]);
      Perm(list,k+1,m);
       //排列结束后换回，继续上一位排列，嘿嘿，有点像dfs
      Swap(list[k],list[i]);
    }
  }
}

划分

设d为整数部分，up为分母，down为分子，
整数部分肯定要小于你给定的待求值N，所以要先算出N的位数。
然后在范围内，再一步一步试探up，down能否满足条件N=d+up/down，
但要是遍历，肯定会超时，所以需要剪枝。这个点我就想不来了。

下面是从大神那里看到的方案
d的头部就是list[0],down的尾部是list[9]。
N=d+up/down<=>up=(N-d)down。
设up的尾部数字为 upLast, upLast = ((N-d)list[8])%10。
接着判断条件就出来了 : up%down == 0 &&
upLast == ((N-d)*list[8])%10 && N-d == up/down

完整代码

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
57
58
59
60
61
62
63
64
65
66
67
68
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#define ll long long
#define INF 100000000
using namespace std;
int x=0,number=0,Count=0;
inline void Swap(int &a,int &b)
{
    int temp=a;
    a=b;
    b=temp;
}
int getNum(int list[],int f,int r)
{
    int i=0,num=0;
    for(i=f;i<=r;i++)
        num=list[i]+num*10;
    return num;
}

void Perm(int list[],int k,int m)
{
    //全排列结束
    if(k==m-1)
    {
        int a=0,b=0,c=0,bLast=0;
        for(int i=0;i<x;i++){
            a=getNum(list,0,i);
            bLast=((number-a)*list[8])%10;
            for(int j=i+(8-i)/2;j<8;j++)
                if(list[j]==bLast){
                    b=getNum(list,i+1,j);
                    c=getNum(list,j+1,8);
                    if(b%c==0 && a+b/c==number)
                    {
                        Count++;
                    }
                    break;
                }
        }
    }
    else{
        for(int i=k;i<m;i++){
            //第k层递归，排列第k位可能的值
            Swap(list[k],list[i]);
            Perm(list,k+1,m);
            //排列结束后换回，继续上一位排列
            Swap(list[k],list[i]);
        }
    }
}
int main()
{
    int temp=0;
    int list[]={1,2,3,4,5,6,7,8,9};
    cin>>number;
    temp=number;
    while(temp!=0)
    {
        x++;
        temp/=10;
    }
    Perm(list,0,9);
    cout<<Count<<endl;
    return 0;
}