P5440 【XR-2】奇迹 (大模拟dfs+欧拉筛板子+闰年)-Toy模板网

这篇具有很好参考价值的文章主要介绍了P5440 【XR-2】奇迹 (大模拟dfs+欧拉筛板子+闰年)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

传送门https://www.luogu.com.cn/problem/P5440

相信奇迹的人，本身就和奇迹一样了不起。——笛亚《星游记》

思路历程：很离谱的一题，在理论上并不困难，只要简单dfs+欧拉筛就能过。在一开始，我采用了倒着模拟的思路，用stoi函数，强转字符串，发现样例能跑，但是仍旧RE（现在仍未理解这样的原因），于是，我选择了另一种做法，反过来遍历。

下面是代码：文章来源地址https://www.toymoban.com/news/detail-826883.html

#include<iostream>
#include<algorithm>
#include<cmath>
#include<set>
#include<string>
using namespace std;
const int N=1e8+5;
int _;
string s;
int ans;
bool nums[N];//这两行
long long f[10000001],cot=0;//这两行是欧拉筛的板子
int months[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};//减少代码量，开一个月份数组
bool check(int num){//检查年份符不符合逻辑
	int day=num%100;
	int month=(num/100)%100;
	int year=num/10000;
	if((year%4==0&&year%100!=0)||year%400==0){
		months[2]=29;
	}
	else months[2]=28; 
	return year>=1&&year<=9999&&month>=1&&month<=12&&day>=1&&day<=months[month];
}

void dfs(int x,int num){//第x层,数字为num
    int sum;//记录每一层要加多少
    if(x==8&&check(num)&&!nums[num]&&!nums[num%10000]&&!nums[num%100]){//100和10000
    	ans++;//2 4 8都要是素数
    }
    else if(x==8) return;//只要是8就返回
	else if(s[x]!='-'){
		sum=(s[x]-'0')*pow(10,7-x);//字符串转数字  要注意减去‘0’
		dfs(x+1,num+sum);
	}
	else{
		if(x==4){//特判优化，减少for的遍历（月份）
			for(int i=0;i<2;++i){
				sum=i*pow(10,7-x);
				dfs(x+1,sum+num);
			}
		}
		else if(x==6){//特判优化（日子）
			for(int i=0;i<4;++i){
				sum=i*pow(10,7-x);
				dfs(x+1,sum+num);
			}
		}
		else{
			for(int i=0;i<=9;++i){
				sum=i*pow(10,7-x);
				dfs(x+1,sum+num);
			}
		}
	}
	
}

void solve(){
	ans=0;
	cin>>s;
	dfs(0,0);（从第0层开始）
	cout<<ans<<endl;
}

int main(){
	nums[1]=true;//1不是素数  true就不是素数 
	long long n=1e8;
    for(long long i=2;i<=n;i++)
    {
        if(!nums[i])
            f[cot++]=i;
        for(long long j=0;j<cot&&i*f[j]<=n;j++)
        {
            nums[f[j]*i]=true;
            if(i%f[j]==0)
                break;
        }
    }//从开头到这里就是一个欧拉筛的板子
	cin>>_;
	while(_--){
	    solve();	
	}
	return 0;
}

到了这里，关于P5440 【XR-2】奇迹 (大模拟dfs+欧拉筛板子+闰年)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！