AcWing 1209.带分数(代码 + 思路详解)

发布时间:2024年01月19日

[题目概述]

100可以表示为带分数的形式: 100 = 3 + 69258 / 714 100 = 3 + 69258/714 100=3+69258/714还可以表示为: 100 = 82 + 3546 / 197 100=82+3546/197 100=82+3546/197
注意特征:带分数中,数字 1~9分别出现且只出现一次(不包含 0)。
类似这样的带分数,100有 11 种表示法。

输入格式

一个正整数。

输出格式

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

数据范围

1 ≤ N < 1 0 6 10^6 106

输入样例1:
100
输出样例1:
11
输入样例2:
105
输出样例2:
6
  • 分析问题
    • 在我们读完题后,感觉找不到切入点,这很正常。我们再思考一下,可以将等式右边的三个数命名为a, b, c;题目说在这三个数中1 ~ 9 这九个数字必须出现并且只能出现一次,分析到这里感觉有点排列型枚举的意思。那我们如果将这三个数合起来看是不是就是在一个数中1 ~ 9 必须出现且仅出现一次。那这样就将题目转化为:将1 ~ 9 进行全排列,再将结果分成三个数,这三个数满足题目所给条件的情况有几种。

    • 部分代码解析
      1.首先我们需要给这九个数进行全排列(就是递归的排列型枚举)

      int st[N], used[N];// st数组是保存每一位上放的数,used数组是看每个数是否被使用过
      for (int i = 1; i <= 9; i ++) {
      	if (!used[i]) {
      		st[u] = i;
      		used[i] = true;
      		dfs(u + 1);
      		
      		st[u] = 0;
      		used[i] = false;
      	}
      }
      

      2.当到达临界时,需要将其分成三个部分

      // 临界情况
      if (u > 9) {
      	// 开始将数分成a,b,c三个部分
      	//因为 n < 10^6,所以第一个数最多有六位,而第三个数至少有一位,所以j 最多枚举到8
      	for (int i = 1; i <= 6; i ++) {
      		for (int j = i + 1; j <= 8; j ++) {
      			int a = number(1, i);
      			int b = number(i + 1, j);
      			int c = number(j + 1, 9);
      			if (n * c == a * c + b)
      				cnt ++;
      		}
      	}
      }
      
      // l,r分别表示起始和终止索引
      int number(int l, int r) {
      	int res = 0;
      	for (int i = l; i <= r; i ++) {
      		res = res * 10 + st[i];
      	}
      	return res;
      }
      
  • 完整代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;
const int N = 10;
int n, cnt;
int st[N], used[N];// st数组是保存每一位上放的数,used数组是看每个数是否被使用过

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

void dfs(int u) {
	// 临界情况
	if (u > 9) {
		// 开始将数分成a,b,c三个部分
		for (int i = 1; i <= 6; i ++) {
			for (int j = i + 1; j <= 8; j ++) {
				int a = number(1, i);
				int b = number(i + 1, j);
				int c = number(j + 1, 9);
				if (n * c == a * c + b)
					cnt ++;
			}
		}
	}

	for (int i = 1; i <= 9; i ++) {
		if (!used[i]) {
			st[u] = i;
			used[i] = true;
			dfs(u + 1);

			st[u] = 0;
			used[i] = false;
		}
	}
}

int main () {
	cin >> n;
	dfs(1);
	cout << cnt;
	return 0;
}
  • 本题讲解完毕,有问题的小伙伴可以在评论区留言,别忘了点赞收藏!
文章来源:https://blog.csdn.net/nuc_ghp/article/details/135556390
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。