[蓝桥杯][2013年第四届真题]带分数

题目链接：带分数

解题思路：要使得$n=a\ast \frac{b}{c}$ 先搜索a，在当前a的情况下搜索c，$b=n\ast c-a\ast c$，然后检查一下是否合法，合法则答案++。

#include<bits/stdc++.h> #define x first #define y second #define mem(h) memset(h,-1,sizeof h) #define mcp(a,b) memcpy(a,b,sizeof b) using namespace std; typedef long long LL; typedef unsigned long long ull; typedef pair<int,int>PII; typedef pair<double,double>PDD; namespace IO{ inline LL read(){ LL o=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){o=o*10+c-'0';c=getchar();} return o*f; } }using namespace IO; //#############以上是自定义技巧（可忽略）########## const int N=1e3+7,M=2e3+7,INF=0x3f3f3f3f,mod=1e9+7,P=131; bool st[11],bk[11]; int n,ans; int check(int a,int c){ LL b= n*(LL)c-a*c;//把当前a，c的情况的b求出 if(!a||!b||!c)return false;//如果有一个为0，则不合法 mcp(bk,st);//拷贝之前已经用过的数 while(b){//拆分b的每一位 int x=b%10; b/=10; if(!x||bk[x])return false;//如果有一位为0或者已经有过这个数字，则不合法 bk[x]=1; } for(int i=1;i<=9;i++){ if(!bk[i])return false;//如果有一个数字没有来过，也不合法 } return true; } void dfs_c(int a,int c){ if(check(a,c))ans++;//检查当前为a，c的情况下是否合法 for(int i=1;i<=9;i++){如果这个数字没有被用过，则可以加在c上 if(!st[i]){ st[i]=1; dfs_c(a,c*10+i); st[i]=0; } } } void dfs_a(int a){ if(a>=n)return ;//剪枝：如果a已经大于答案，那么不合法 if(a)dfs_c(a,0);//在当前a的情况下，搜索c for(int i=1;i<=9;i++){//枚举一个数字 if(!st[i]){//如果这个数字没有被用过，则可以加在a上 st[i]=1; dfs_a(a*10+i); st[i]=0; } } } int main(){ cin>>n; dfs_a(0);//搜索a cout<<ans<<endl; return 0; }