蓝桥杯算法提高VIP-排列式 （C++代码）

解题思路:
先分析问题，不要盲目暴力。

如果直接搜索，使用先求全排列，然后逐位选取数字，再组合的方法，复杂度在P(9,4)*P(5,2)*3! = 362880 > 3*10^5上下，可能在1s的时间里是无法承受的。

实际上，题目已经给出了暗示，四位数 = 两位数 * 三位数 是一种可行的方案。一共9个数字，如果是 四位数 = 四位数 * 一位数 应当也可能存在解。那么其他情况呢？

五位数 = 两位数 * 两位数——显然不可以，因为即便是最大的两位数99乘以99，积也是四位数。除此之外的一位数 * 三位数等其他方案同样也是显然不行的。

三位数的方案显然是不可以的，因为剩下的6个数字，无论怎么分，位数就大于等于三位，显然都太大了。

往两边的试探性搜索都以失败而告终，专心枚举 四位数 = 两位数 * 三位数 和 四位数 = 四位数 * 一位数 两种方案即可。

注意事项:

1.注意适当地剪枝，将出现重复数字和0的数字，以及乘积位数超过4位的情况及时剔除。

2.不要漏掉  四位数 = 四位数 * 一位数 的方案

3.题目要求按照第一标尺乘积大小，第二标尺较小乘数的大小由小到大输出，自行实现cmp比较函数，调用stl库的sort函数，详见代码

4.耗时在40ms上下

PS：如果超时，可以在本地把答案全部算出来，然后直接输出，附赠直接输出答案的代码：

#include<iostream>
using namespace std;
int main()
{
    cout << "4396 = 28 x 157" << endl
    << "5346 = 18 x 297" << endl
    << "5346 = 27 x 198" << endl
    << "5796 = 12 x 483" << endl
    << "5796 = 42 x 138" << endl
    << "6952 = 4 x 1738" << endl
    << "7254 = 39 x 186" << endl
    << "7632 = 48 x 159" << endl
    << "7852 = 4 x 1963" << endl;
    return 0;
}

参考代码:

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <stdio.h>

using namespace std;

typedef struct Expression {
	int c;//乘积
	int a;//较小的乘数
	int b;//较大的乘数
};

vector<Expression> ans;

bool cmp(Expression a, Expression b)
{
	if (a.c < b.c)
		return true;
	else if (a.c == b.c)
	{
		if (a.a < b.a)//次级条件
			return true;
		else
			return false;
	}
	else
		return false;
}

bool check(int n)
{
	bool ret = true;
	bool vis[10] = { false };
	while (n)
	{
		int curNum = n % 10;
		if (vis[curNum] || curNum == 0)
		{
			ret = false;
			break;
		}
		vis[curNum] = true;
		n /= 10;
	}
	return ret;
}

void pushNumToSet(int n, set<int>& s)
{
	while (n)
	{
		int curNum = n % 10;
		s.insert(curNum);
		n /= 10;
	}
}

void solve()
{
	//1位乘以4位
	for (int a = 1; a <= 9; a++)
	{
		for (int b = 1000; b <= 9999; b++)
		{
			if (!check(b))
				continue;
			int c = a*b;
			if (c > 9999)
				break;
			set<int> numSet;
			pushNumToSet(a, numSet);
			pushNumToSet(b, numSet);
			pushNumToSet(c, numSet);
			if (numSet.size() == 9)
			{
				if (find(numSet.begin(), numSet.end(), 0) == numSet.end())
				{
					Expression expr;
					expr.a = a;
					expr.b = b;
					expr.c = c;
					ans.push_back(expr);
				}
			}
		}
	}

	//2位乘以3位
	for (int a = 10; a <= 99; a++)
	{
		if (!check(a))
			continue;
		for (int b = 100; b <= 999; b++)
		{
			if (!check(b))
				continue;
			int c = a*b;
			if (c > 9999) 
				break;
			set<int> numSet;
			pushNumToSet(a, numSet);
			pushNumToSet(b, numSet);
			pushNumToSet(c, numSet);
			if (numSet.size() == 9)
			{
				if (find(numSet.begin(), numSet.end(), 0) == numSet.end())
				{
					Expression expr;
					expr.a = a;
					expr.b = b;
					expr.c = c;
					ans.push_back(expr);
				}
			}
		}
	}
}

int main(int argc, char** argv)
{
	solve();
	sort(ans.begin(), ans.end(), cmp);
	for (vector<Expression>::iterator it = ans.begin(); it < ans.end(); it++)
		cout << it->c << " = " << it->a << " x " << it->b << endl;
 	return 0;
}