题目链接
1209. 带分数 - AcWing题库
一些话
流程
1.由“带分数中，数字 1∼91∼9 分别出现且只出现一次（不包含 00）。”知，需要枚举的数是1-9
9作为时间复杂度中的n，n <=30，可以用dfs，dp
2.”输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。“
根据这句话得知此题是要枚举情况然后判断情况合不合题意，合则加种数，由于是求种类数 而不是最优解，此题更适合用dfs递归
3.带分数形式是
100=3+69258 / 714，通过枚举其中两个数就可以求出第三个数，通过判断第三个数用到的数字有没有出现过或者有没有0，还要判断算上第三个数中用到的数字，所有数字是否都用过了就可以知道是否符合题意
4.通过两个dfs的嵌套可以实现同时枚举两个数字，但时间复杂度非常高，最好要进行剪枝（dfs参数符合某种情况时直接return）
套路
1.同时枚举两个数
void dfs_c(int u,int a,int c){ for(int i = 1;i <= 9;i++){ …… dfs(u+1,a,c * 10 + 1 ); } } void dfs_a(int u,int a){ dfs_c(u ,a,0); }
2.数组的回溯
设置一个backup数组，
在操作前 memcpy(backup,f,sizeof f);备份f数据
回溯时再反过来
memcpy(f,backup,sizeof f); 恢复现场
ac代码
//dfs的参数可以写上需要回溯的内容,一些回溯操作复杂的可以直接写上 //17:25~47已经对了，但没认真看样例，导致一直在找不存在的bug // 19：35~44 accepted //19:44~52 #include <iostream> #include <algorithm> #include <cstring> #include <cstdio> using namespace std; const int N = 10; int f[N],n,ans; bool st[N],backup[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 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 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; for(int i = 1;i <= 9;i++){ if(!st[i]) { st[i] = true; dfs_a(u+1,a * 10 + i); st[i] = false; } } if(a)dfs_c(u,a,0); } int main(){ cin >> n; dfs_a(0,0); cout << ans << endl; return 0; }
