1209. 带分数 - AcWing题库
yxc题解AcWing 1209. 带分数 - AcWing
题意:
给定一个数,将它写成带分数的形式,每个数字不重复,计算有多少种方案
思路:对于方程n=a+b/c,将它变为n*c=a*c+b,所以b=n*c-a*c;
我们现在只需要枚举a和c,将枚举转化为全排列问题,对于每次枚举完a后,接着枚举c,再通过判断方程是否成立。
参考代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=10;
int n;
bool st[N],backup[N];//backup数组用来备份st数组,因为要对backup进行修改
int ans;
bool check(int a,int c)
{LL b=n*(LL)c-a*c;//这里定义LL是为了防止爆int,因为c的位数可以达到8位,乘上n后可能会爆int
//从而导致b为负数,数组越界if(!a||!b||!c) return false;memcpy(backup,st,sizeof(st));while(b){int x=b%10;b/=10;if(!x||backup[x]) return false;backup[x]=true;}for(int i=1;i<=9;i++){if(!backup[i])return false;}return true;
}
void dfs_c(int a,int c)
{if(check(a,c)) ans++;//每次枚举到c的时候判断方程是否合法for(int i=1;i<=9;i++){if(!st[i]){st[i]=true;dfs_c(a,c*10+i);st[i]=false;}}
}
void dfs_a(int a)
{if(a>=n) return;//剪枝if(a) dfs_c(a,0);for(int i=1;i<=9;i++){if(!st[i]){st[i]=true;dfs_a(a*10+i);//让a加入一位数字st[i]=false;//状态回溯}}
}
int main()
{cin>>n;dfs_a(0);cout<<ans<<endl;return 0;
}
法二:求出1~9的全排列情况,并把区间分为三段,枚举所有可能情况
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n;
int path[N];
bool st[N];
int res;
int check(int i,int j)
{int ans=0;for(int z=i;z<=j;z++){ans=ans*10+path[z];}return ans;
}
void dfs(int u)
{if(u>9){int a,b,c;for(int i=1;i<=7;i++){for(int j=i+1;j<=9;j++){a=check(1,i);b=check(i+1,j);c=check(j+1,9);if(n*c==a*c+b) res++;}}return;}for(int i=1;i<=9;i++){if(st[i]==false){path[u]=i;st[i]=true;dfs(u+1);st[i]=false;}}
}
int main()
{cin>>n;dfs(1);cout<<res<<endl;return 0;
}