[蓝桥杯][2013年第四届真题]带分数

题目

题目链接

题解

全排暴力。

规定一下：n = sum1 + sum2/sum3

使用next_permutation()函数对保存着1、2、……、9的数组进行全排列，对于每一种全排列，我们对其进行分段，分成三段，第一段构成sum1第二段构成sum2第三段构成sum3 。算出三段的大小,判断是否满足上面等式即可。

我裂开，我想了好久，心想暴力肯定不行时间必超，觉得一定是个思维题，结果我想多了，扫了一眼网上题解的第一句话“全排”，我就试着算了一下9!=362880，妈的，我居然觉得9!会特别大，结果才不到4e5。

这说明几个问题：

• 我是《小可爱》
• 蓝桥杯是暴力杯
• 蓝桥杯也是《小可爱》

时间上限且是无法触及的上限，大概是9! * 7 * 7 < 2e7。 算的不准确，反正肯定比这个小。

代码

#include
using namespace std;

int a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int n, ans;

// 9! = 362880
int main()
{
	cin>>n;
	int x = n, sn = 0;
	while(x) sn ++, x/=10; // sn保存n的size，即n的位数 
	
	while(next_permutation(a+1, a+10)) { // 全排 
		for(int s1 = 1;s1 0的必要条件，用这个开始相当于避免一些无用的判断 
				int sum2 = 0, sum3 = 0;
				for(int j = s1+1;j