自动搬运

查看原文

来自洛谷，原作者为

	pxb0801 平行世界，多元生活，既可以朝九晚五，又能够浪迹天涯

搬运于2025-08-24 22:40:33，当前版本为作者最后更新于2022-11-03 23:17:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

1.题目大意：

题目很简单：给你一个 $n$，问有多少种表示为 $a+\frac{b}{c}$ 的形式，且 $a,b,c$ 中的数字正好不重复不遗漏的包含数字 $1$ ~ $9$。

2.分析：

如果这道题去枚举 $a$，再去一个一个枚举 $b$，算出 $c$，最后再验证，会极其的麻烦。

我们不如这样想：将 $a,b,c$ 中的所有数字连在一起，是不是就是一个 $1$ ~ $9$ 的全排列？

我们以样例为例：对于 $82+\frac{3546}{197}$ 而言，这个全排列就是 823546197。这样，我们去枚举 $1$ ~ $9$ 的全排列会轻松许多，时间上也会快很多。

写代码时，可以选择手打深搜，也可以用一下 next_permutation 这个函数（非常的好用）。

当我们生成一个排列时，只需要枚举两个断点 $i$ 和 $j$，此时下标 $1$ ~ $i$ 的就是 $a$；$i+1$ ~ $j$ 的就是 $b$；$j+1$ 到 $9$ 的就是 $c$。最后判断一下即可。

3.正确代码：

#include<bits/stdc++.h>
using namespace std;
int t,n,a[10]={0,1,2,3,4,5,6,7,8,9},ans;
int main(){
	cin>>n;
	while(1){
		int x=0;
		for(int i=1;i<=7;i++){
			x=x*10+a[i];
			int y=0;
			for(int j=i+1;j<=8;j++){//枚举断点 
				y=y*10+a[j];
				int z=0;
				for(int k=j+1;k<=9;k++){
					z=z*10+a[k];
				} 
				if(y%z==0&&x+y/z==n){//判断是否满足条件 
					ans++;//满足则答案+1 
				}
			}
		}
		next_permutation(a+1,a+9+1);
		//检查，如果此时的全排列又回到第一次的，则跳出循环 
		bool ok=0;
		for(int i=1;i<=9;i++){
			if(a[i]!=i){
				ok=1;
				break;
			}
		}
		if(!ok) break;
	}
	cout<<ans;
	return 0;
}