acwing1209. 带分数

题目

题解

• 暴力思路：
  列举所有的全排列，大概有9位数字，然后将九位数字分成三个a,b,c，如果满足nc=ac+b,那么就是答案。

#include<iostream>
using namespace std;
const int N=20;
int ans=0;
bool st[N];
int path[N];
int n;
int cal(int l,int r){
    int t=0;
    for(int i=l;i<=r;i++){
        t=t*10+path[i];
    }
    return t;
}
void dfs(int u){
    if(u==9){
        for(int i=0;i<7;i++){
            for(int j=i+1;j<9;j++){
                int a=cal(0,i);
                int b=cal(i+1,j);
                int c=cal(j+1,8);
                if(a*c+b==n*c)ans++;
            }
        }
        return ;
    }
    for(int i=1;i<=9;i++){
        if(!st[i]){
            st[i]=true;
            path[u]=i;
            dfs(u+1);
            st[i]=false;
        }
    }
}
int main(){
    cin>>n;
    dfs(0);
    cout<<ans<<endl;
    return 0;
}

• 优化：
  先枚举a,再枚举c,然后通过ac得到b，最后去查看等式是否成立。

#include<iostream>
#include<cstring>
using namespace std;
const int N=20;
int ans=0;
bool st[N],backup[N];
int path[N];
int n;
bool check(int a,int c){
    long long b=n*(long long)c-c*a;
    if(!(a&&b&&c))return false;
    memcpy(backup,st,sizeof st);
    while(b){
        int t=b%10;
        if(!t||backup[t])return false;
        b/=10;
        backup[t]=true;
    }
    for(int i=1;i<=9;i++){
        if(!backup[i])return false ;
    }
    return true;
    
}
void dfs_c(int u,int a,int c){
    if(u>9)return;
    if(check(a,c))ans++;
    for(int i=1;i<=9;i++){
        if(!st[i]){
            st[i]=true;
            dfs_c(u+1,a,c*10+i);
            st[i]=false;
        }
    }
}
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(!st[i]){
            st[i]=true;
            dfs_a(u+1,a*10+i);
            st[i]=false;
        }
    }
}
int main(){
    cin>>n;
    dfs_a(0,0);
    cout<<ans<<endl;
    return 0;
}