AcWing 1209. 带分数

题目条件:

1. 枚举全排列，是9个数
   

2. a，b，c的位数都还不知道
   枚举a,b，c的位数，枚举a和b的位数 ,c=9-a-b

3. 判断等式是否成立

//  暴力dfs
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int cnt; //输出方案
long long a,b,c;
int path[9];  // 路径
bool st[9];  // 状态
//  条件 n= a+ b/c;  转换为: n*c =a*c +b



// 数组path元素拼接在一起构成整数
int array_to_nums(int l,int r){
  int res=0;
  for(int i=l;i<=r;i++){
    res=res*10+path[i];
  }
  return res;
}

// 全排列9个数
void dfs(int u){
  //  输出组合的一种情况
  if(u>9){  
    for(int i=1;i<=7;i++){          // i的范围 1——7
      for(int j=i+1;j<=8;j++){      // j的范围 i+1 ——8
        int a=array_to_nums(1,i);  // 数组元素拼接在一起构成整数a
        int b=array_to_nums(i+1,j);  //数组元素拼接在一起构成整数a
        int c=array_to_nums(j+1,9); 
        // 满足题目条件时，输出
        if(c*n == a*c+b){
          cnt++;  // 表示方法加1
        }
      }
    }
    return ;
  }
  for(int i=1;i<=9;i++){
    if(!st[i]){
      st[i]=true;
      path[u]=i;
      dfs(u+1);
      st[i]=false;
      path[u]=0;
    }
  }

  
}

int main(){
  cin>>n; // 读入一个整数
  dfs(1);
  cout<<cnt;
  return 0;
}

补充: 计算程序的空间复杂度

int 占4个Byte
char 占 1个Byte
long long 占8 Byte
float 占4 Byte

1 Byte =8 bit
简写: 1B =8位

1MB =2^10KB
1KB =2^10B
64MB = 64 * 2^ 20B

2^20 约等于 10的6次方
2^10 约等于10 的3次方