蓝桥杯算法提高VIP-排列式

题目

题目链接

题解

全排列。

这种题一般就是全排列，9! < 4e5。 这里有点小技巧，就是结果必然是个四位数，第一个乘数要么是一位数要么是两位数。

为什么这么说呢？ 我们知道假设第一个乘数a位，第二个乘数b``位，那么他们乘积的位数要么是a+b位，要么是a+b-1位 如果结果是个三位数，那么还剩六位数，无论将这六位数怎么分配给两个乘数都无法满足乘积为三位，同理结果为一位和两位也都不可能； 如果结果是个五位数，那么还剩四位，四位数分配给两个乘数最多乘出来个四位数，因此还是不行，同理大于五位更不行；

很显然只有结果为四位数可行。当结果为四位数时，乘数可能是多少位呢？ 题目要求乘数互换属于一个式子，同时要求乘数小的先输出，因此我们只需考虑第一个乘数的位数，无非是一位或两位嘛。当第一个乘数为一位时，第二个乘数为四位；当第一个乘数为两位时，第二个乘数为三位；如果也输出第一个乘数为三位的情况的话，那么第二个乘数就是两位了，这必然会出现重复输出。因此，我们只用输出第一个乘数是一位和两位的情况就行了。

如何保证使用next_permutation就能按要求的大小输出？ 首先我们要明白next_permutation的实现原理，正如其名，这个函数就是让一个元素递增排序的数组不断变大，每次后出现的都会大于先出现的。据说它也是通过递归实现的，因此不允许排序的个数太多。如果还是不能理解可以完整的输出一个序列的全部全排列模拟一下。 对于每一种全排列，就对应着一种乘积，我们先输出第一个是取一位的情况，再输出第一个乘数为两位的情况就行了。

代码

#include
using namespace std;
const int N = 1e3;

int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int num1, num2, num3;

int main()
{
	do { 
		// xxxx = x * xxxx
		num1 = num2 = num3 = 0;
		for(int i = 0;i