本文主要是介绍P5440 【XR-2】奇迹 (大模拟dfs+欧拉筛板子+闰年)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门
https://www.luogu.com.cn/problem/P5440
相信奇迹的人，本身就和奇迹一样了不起。——笛亚 《星游记》
思路历程：很离谱的一题，在理论上并不困难，只要简单dfs+欧拉筛就能过。在一开始，我采用了倒着模拟的思路，用stoi函数，强转字符串，发现样例能跑，但是仍旧RE（现在仍未理解这样的原因），于是，我选择了另一种做法，反过来遍历。
下面是代码：
#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层,数字为numint sum;//记录每一层要加多少if(x==8&&check(num)&&!nums[num]&&!nums[num%10000]&&!nums[num%100]){//100和10000ans++;//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+欧拉筛板子+闰年)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
