[C++知识库]1209. 带分数

ACwing的链接为https://www.acwing.com/problem/content/description/1211/https://www.acwing.com/problem/content/description/1211/

100 可以表示为带分数的形式：100=3+69258714100=3+69258714

还可以表示为：100=82+3546197100=82+3546197

注意特征：带分数中，数字 1～91～9 分别出现且只出现一次（不包含 00）。

类似这样的带分数，100 有 11 种表示法。

输入格式

一个正整数。

输出格式

输出输入数字用数码 1～9不重复不遗漏地组成带分数表示的全部种数。

数据范围

1≤N<1061≤N<106

输入样例1：

100

输出样例1：

11

输入样例2：

105

输出样例2：

6

代码为：

#include <bits/stdc++.h>

using namespace std;

const int N = 10;

int target;
int num[N];

int calc(int l, int r) {
  int res = 0;
  for (int i = l; i <= r; i++) {
    res = res * 10 + num[i];
  }
  return res;
}

int main() {
  cin >> target;
  for (int i = 0; i < 9; i++) {
    num[i] = i + 1;
  }
  int res = 0;
  do {
    for (int i = 0; i < 7; i++) {
      for (int j = i + 1; j < 8; j++) {
        int a = calc(0, i);
        int b = calc(i + 1, j);
        int c = calc(j + 1, 8);
        if (a * c + b == c * target) {
          ++res;
        }
      }
    }
  } while (next_permutation(num, num + 9));
  cout << res << '\n';
  return 0;
}

用了暴力破解，分成三段，依次列举，找到符合题意的。

res=res*10+num[i];

?这个是相当于加法进位，数组中每个元素都是单独一个个位数，然后比如说num[2]…num[3]num[2]…num[3]，就看作是num[2]…num[3]num[2]…num[3]之间的这22个个位数连接成一个两位数对吧，组成的这个两位数应该是num[2]×10+num[3]num[2]×10+num[3]。

do {
    for (int i = 0; i < 7; i++) {
      for (int j = i + 1; j < 8; j++) {
        int a = calc(0, i);
        int b = calc(i + 1, j);
        int c = calc(j + 1, 8);
        if (a * c + b == c * target) {
          ++res;
        }
      }
    }
    // 调用函数生成全排列
  } while (next_permutation(num, num + 9));

你可以想象在num这9个数中间画两条线，这样就把这9个数分成三段了对吧，而且是一定要分成三段的，要保证每一段都至少有一个数。所以第一段最多只能选到第七个，如果第一段就选了八个数的话，只剩下一个数，这样就不够分了呀。第二段同理，如果第二段选到了第九个数，那第三段就没数可以选了。

用DFS:

#include<bits/stdc++.h>
using namespace std;
const int N = 9;
int t;  // 题目给出的目标数
int num[N];  // 保存全排列的结果
bool used[N];  // 生成全排列过程中标记是否使用过
int cnt;  // 计数，最后输出的结果

// 计算num数组中一段的数是多少
int calc(int l, int r) {
  int res = 0;
  for (int i = l; i <= r; i++) {
    res = res * 10 + num[i];
  }
  return res;
}

// 生成全排列
// 当全排列生成后进行分段
void dfs(int u) {
  // 用两层循环分成三段
  if (u == 9) {
      for (int i = 0; i < 7; i++) {
        for (int j = i + 1; j < 8; j++) {
          int a = calc(0, i);
          int b = calc(i + 1, j);
          int c = calc(j + 1, 8);
          // 注意判断条件，因为C++中除法是整除，所以要转化为加减乘来计算
          if (a * c + b == c * t) {
            cnt++;
          }
        }
      }
      return;
  }
  // 搜索模板
  for (int i = 1; i <= 9; i++) {
    if (!used[i]) {
      used[i] = true; // 标记使用
      num[u] = i;
      dfs(u + 1);
      used[i] = false; // 还原现场
    }
  }
}

int main() {
  cin>>t;
  dfs(0);
  cout<<cnt;
  return 0;
}