P8599题解

wangif424 · 2022-11-03 00:34:00 · 题解

应该不止我背不下来全排列的STL吧......

来个手动搜索全排列的做法。

思路：

由题意知，需要保证 a+\dfrac{b}{c} 中，a,b,c 的每一位 x_i 都保证 1 \le x_i \le 9 且 x_i 之间互不相同。

于是可以想到对 1 ~ 9 全排列，再枚举出两个分割点分成 a,b,c 三个数，并判断 a+\dfrac{b}{c}=n 成立即可。

流程:

DFS 搜出每种排列。
for 循环遍历两个"分段点"的位置。
判断是否相等和是否整除。

AC代码：

#include<bits/stdc++.h>
using namespace std;
int a[21],n,book[21],cnt;
int atoi(int l,int r){//array to int
    int re=0;
    for(int i=l;i<=r;i++){
        re=re*10+a[i];
    }
    return re;
}
void pd(){//处理每种组合
    for(int r=1;r<=9;r++){
        if(r>7)break;
        int f=atoi(1,r);
        if(f>n)break;
        for(int r2=r+1;r2<9;r2++){
            int f1=atoi(r+1,r2);
            int f2=atoi(r2+1,9);
            if(f+f1/f2==n && f1%f2==0){
                cnt++;
            }
        }
    }
    return;
}
void c(int i){
    if(i==10){
        pd();
        return;
    }
    for(int j=1;j<=9;j++){
        if(!book[j]){
            book[j]=1;
            a[i]=j;
            c(i+1);
            book[j]=0;
        }
    }
    return;
}
signed main(){
    cin >> n;
    c(1);
    cout << cnt;
    return 0;
}

补充一种更暴力的方法：

首先这是一道入门题，打开标签，只有枚举。

故此题可以用枚举法解决。~~有亿点费命~~

代码：

代码比较长，就放剪切板里了：代码。