Dreamer(全排列)

Bash just woke up from his sweetest dream ever. In his dream, he became the best Pokenom trainer — like no one ever was. It was on the date …

Unfortunately, Bash forgot the exact date. He only remembered that the date was written in format ‘DD MM YYYY’ with exactly 8 digits. He also remembers these 8 digits (but he does not remember their order). Of course, the date must be a valid date.

Since Bash was born on Jan 1st, 2000, he knows that the date was on or after Jan 1st, 2000. (Note that the date can be Jan 1st, 2000 — it means Bash is destined to be the best Pokenom trainer since he was born!).

Bash really wants to know the date when he become the best Pokenom trainer. How many possible valid dates could there be? What is the earliest valid date that Bash could become the best Pokenom trainer?

Notes
On a leap year, February has 29 days. Following are the rules for determining leap years:

A year divisible by 400 is a leap year,

A year divisible by 100 but not by 400 is NOT a leap year,

A year divisible by 4 but not by 100 is a leap year,

A year not divisible by 4 is NOT a leap year.

Input
The first line contains one integer t (1≤t≤50) — the number of test cases.

Each of the next t lines describes one test case, contains eight digits in the format ‘XX XX XXXX’ (eight digits, separated by two blank spaces). Note that the input might not represent a valid date.

Note that the first month of the year is represented by 01, and the first day of the month by 01.

Output
For each test case, output a single line containing the number of possible dates and the earliest date which Bash could become the best Pokenom trainer, in the format ‘DD MM YYYY’. If there are no valid dates, print a single line containing ‘0’ (zero) instead.

Sample Input 1

3
04 11 2018
23 45 6789
01 01 0002

Sample Output 1

524 18 11 2004
0
4 01 01 2000

介绍本题思路之前，先介绍C++中STL带的一个函数操作 next_permutation（全排列）。
顾名思义，就是将数组中的元素，进行全排列，前提是该数组中的元素必须是有序的，然后，使用next_permutation可以从小到大除去重复对其进行全排列。
具体使用过程与详解，可以百度或者在CSDN中搜索。
这里给一个传送门：https://blog.csdn.net/bengshakalakaka/article/details/78515480

本题解决了全排列问题，思路就很简单了。首先，存入这8个数字，对它进行排序后，进行循环全排列。
接着对排列的数字进行判断：

1. 先判断年份的第一个数字是否大于等于2。（因为题目要求，必须在他出生之后，也就是说，要在2000年以后）
2. 判断该年份是否为闰年。（是否为闰年决定了2月份的日期为28还是29）
3. 判断该月份是否满足在1-12这个范围内。
4. 判断该日期是否在对应月份的长度中，即大月对应31号，小月对应30号，2月对应着28或29号。
5. 如果都满足，则将第一次的年月日记录下来，并每次满足，将计数器加一。

这样，当全排列完成时，所有数据也就都查找完毕，按要求输出即可。
具体代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
char str1[10], str2[10], str3[10];
int mark[10];
int mon[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 };
int main()
{
	int t;
	scanf("%d", &t);
	int data[50];
	while (t--)
	{
		scanf("%s%s%s", str1, str2, str3);
		for (int i = 0; i < 2; i++)
			data[i] = str1[i] - '0';
		for (int i = 0; i < 2; i++)
			data[i + 2] = str2[i] - '0';
		for (int i = 0; i < 4; i++)
			data[i + 4] = str3[i] - '0';
		int ans = 0, flag = 0;
		sort(data, data + 8);
		do
		{
			if (data[0] >= 2)
			{
				int year = data[0] * 1000 + data[1] * 100 + data[2] * 10 + data[3];
				if ((year % 400 == 0) || (year % 4 == 0 && year % 100 != 0))
					mon[1] = 29;
				else mon[1] = 28;
				int month = data[4] * 10 + data[5];
				if (month >= 1 && month <= 12)
				{
					int day = data[6] * 10 + data[7];
					if (day >= 1 && day <= mon[month - 1])
					{
						ans++;
						if (flag == 0)
						{
							for (int i = 0; i < 8; i++)
								mark[i] = data[i];
							flag = 1;
						}
						
					}
				}
			}
		} while (next_permutation(data, data + 8));
		if (ans == 0)
			printf("0n");
		else
		{
			printf("%d", ans);
			printf(" %d%d %d%d %d%d%d%d", mark[6], mark[7], mark[4], mark[5], mark[0], mark[1], mark[2], mark[3]);
			printf("n");
		}
	}
	return 0;
}