P5440 【XR-2】奇迹

暴力模拟即可，开始我尝试记录每个‘-’的位置，然后遍历pos数组，枚举0-9，然而这种写法很恶心。那么自然想到了搜索，每次访问到‘-’枚举0-9即可，进入下一次搜索，注意终止条件是当index==9时，因为使用的是1-base。然后剔除一些非法日期即可符合题意，这样能过 。

#include<iostream>
#include<string>

int month[] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };

bool is_prime(int x)
{
	if (x == 0 || x == 1)
		return false;
	if (x == 2)
		return true;
	for (int i = 2; i * i <= x; i++)
	{
		if (x % i == 0)
			return false;
	}
	return true;
}

bool valid_date(int y, int m, int d)
{
	int flag = ((y % 4 == 0 && y % 100 != 0) || (y % 400 == 0) ? 1 : 0);
	if (y < 1 || y>9999)
		return false;
	if (m < 1 || m>12)
		return false;
	if (d<1 || d >month[m]+(m==2&&flag?1:0))
		return false;
	return true;
}

void dfs(int index, std::string& s,int& res)
{
	if (index == 9)
	{
		int y = (s[1] - 48) * 1000 + (s[2] - 48) * 100 + (s[3] - 48) * 10 + (s[4] - 48);
		int m = (s[5] - 48) * 10 + (s[6] - 48);
		int d = (s[7] - 48) * 10 + (s[8] - 48);
		if (valid_date(y, m, d))
		{
			if (is_prime(d) && is_prime(m * 100 + d) && is_prime(y * 10000 + m * 100 + d))
				res++;
		}
		return;
	}
	if (s[index] == '-')
	{
		for (char c = '0'; c <= '9'; c++)
		{
			s[index] = c;
			dfs(index + 1, s,res);
		}
		s[index] = '-';
	}
	else
		dfs(index + 1, s,res);
}

int main()
{
	int n;
	std::cin >> n;
	std::string s;
	while (n--)
	{
		std::cin >> s;
		s = '0' + s;
		int res = 0;
		dfs(1, s, res);
		std::cout << res<<std::endl;
	}
}

显然，程序的性能瓶颈，一部分在于试除法判别素数，一部分在一些非法日期作了过多的递归，比如当月份的十位大于1时，于是考虑剪枝

#include<iostream>
#include<string>
#include<unordered_map>

int month[] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
std::unordered_map<int, int> cache;

bool is_prime(int x)
{
	if (x < 2)
		return false;
	if (cache.count(x))
		return cache[x];
	if (x == 2)
		return cache[x]=1;
	for (int i = 2; i * i <= x; i++)
	{
		if (x % i == 0)
			return cache[x]=0;
	}
	return cache[x]=1;
}

bool valid_date(int y, int m, int d)
{
	int flag = ((y % 4 == 0 && y % 100 != 0) || (y % 400 == 0) ? 1 : 0);
	if (y < 1 || y>9999)
		return false;
	if (m < 1 || m>12)
		return false;
	if (d<1 || d >month[m]+(m==2&&flag?1:0))
		return false;
	return true;
}

void dfs(int index, std::string& s,int& res)
{
	if (s[5] >= '2')
		return;
	if (s[5]=='1' && s[6] > '2')
		return;
	if (s[7] > '3')
		return;
	if (index == 9)
	{
		int y = (s[1] - 48) * 1000 + (s[2] - 48) * 100 + (s[3] - 48) * 10 + (s[4] - 48);
		int m = (s[5] - 48) * 10 + (s[6] - 48);
		int d = (s[7] - 48) * 10 + (s[8] - 48);
		if (valid_date(y, m, d))
		{
			if (is_prime(d) && is_prime(m * 100 + d) && is_prime(y * 10000 + m * 100 + d))
				res++;
		}
		return;
	}
	if (s[index] == '-')
	{
		for (char c = '0'; c <= '9'; c++)
		{
			s[index] = c;
			dfs(index + 1, s,res);
		}
		s[index] = '-';
	}
	else
		dfs(index + 1, s,res);
}

int main()
{
	int n;
	std::cin >> n;
	std::string s;
	while (n--)
	{
		std::cin >> s;
		s = '0' + s;
		int res = 0;
		dfs(1, s, res);
		std::cout << res<<std::endl;
	}
}