算法学习记录：[NOIP2016]回文日期-526互联

题目链接

https://ac.nowcoder.com/acm/contest/20960/1015

TLE代码

#include <iostream>

using namespace std;

const int N = 10;
int n, x, y;
int X[N], Y[N];
int get_day[] = { -1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

// 拆分数字
void num_to_arr(int num, int a[])
{
	int bit = 8;
	while (bit -- )
	{
		// cout << bit << ' ';
		a[bit] = num % 10, num /= 10;
	}
}

int qmi(int a, int b)
{
	int res = 1;
	for (; b; b >>= 1)
	{
		if ((b & 1)) res *= a;
		a = a * a; 
	}
	return res;
}

int arr_to_num(int a[], int bit, int beg)
{
	int res = 0, d = qmi(10, bit);
	for (int i = beg; i <= beg + bit; ++ i)
		res += a[i] * d, d /= 10;
	return res;
}

// 判断日期是否合法
bool is_right(int year, int mou, int day)
{ 	
	int flag = false; 
	int r_mou = get_day[mou];
	if ((!(year % 4) && (year % 100)) || !(year % 400))	// 闰年，29天
		r_mou += 1;

	if (mou >= 1 && mou <= 12 && day >= 1 && day <= r_mou) flag = true;
	return flag;
}

bool is_w(int a[])
{
	for (int i = 0, j = 7; i < j; ++ i, -- j)
		if (a[i] != a[j]) return false;
	return true;
}

int main()
{
	cin >> x >> y;
	int cnt = 0;
	
	// 20110101
	// 20111231
	
	// 判断回文数，先判断日期是否和法再取年的相反
	for (int i = x; i <= y; ++ i)
	{
		num_to_arr(i, X);
		int year = arr_to_num(X, 3, 0),  mou = arr_to_num(X, 1, 4), day = arr_to_num(X, 1, 6);
		if (!is_right(year, mou, day)) continue;
		if (is_w(X)) cnt ++ ;
	}	

	cout << cnt << endl;
	return 0;
}

暂时没有的AC代码，明天再找bug

TLE代码会枚举所有的年月日，然后就爆炸了。
减少枚举次数，枚举所有的年，构造一个对于年来说的月、日的回文，再判断月、日是否合法。

#include <iostream>

using namespace std;

const int N = 10;
int n, x, y;
int X[N], Y[N];
int get_day[] = { -1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

// 拆分数字
void num_to_arr(int num, int a[])
{
	int bit = 8;
	while (bit -- )
		a[bit] = num % 10, num /= 10;
}

int qmi(int a, int b)
{
	int res = 1;
	for (; b; b >>= 1)
	{
		if ((b & 1)) res *= a;
		a = a * a; 
	}
	return res;
}

int arr_to_num(int a[], int bit, int beg)
{
	int res = 0, d = qmi(10, bit);
	for (int i = beg; i <= beg + bit; ++ i)
		res += a[i] * d, d /= 10;
	return res;
}

// 判断日期是否合法
bool is_right(int year, int mou, int day)
{ 	
	int flag = false; 
	int r_mou = get_day[mou];
	if ((!(year % 4) && (year % 100)) || !(year % 400))	// 闰年，29天
		r_mou += 1;

	if (mou >= 1 && mou <= 12 && day >= 1 && day <= r_mou) flag = true;
	return flag;
}

// 构造回文
void generate_year_day(int year)
{
	int bit = 4;
	while (bit -- )
		X[bit] = year % 10, year /= 10;

	for (int i = 0, j = 7; i < j; ++ i, -- j)
		X[j] = X[i];
}

int main()
{
	cin >> x >> y;
	int cnt = 0;	

	num_to_arr(x, X), num_to_arr(y, Y);
	
	// 20000101
	// 01234567
	// 20101231

	// 提出年，枚举所有年
	int st_year = arr_to_num(X, 3, 0), ed_year = arr_to_num(Y, 3, 0);
	
	for (int i = st_year; i <= ed_year; ++ i)
	{
		// 对年构造回文
		generate_year_day(i);
		int year = arr_to_num(X, 3, 0), mou = arr_to_num(X, 1, 4), day = arr_to_num(X, 1, 6);
		if (is_right(year, mou, day)) cnt ++ ;
	}
	
	cout << cnt << endl;
	return 0;
}