题解 P5440 【【XR-2】奇迹】

StudyingFather

2019-06-29 20:58:21

Solution

搜索题好毒瘤啊QAQ 我们从日期第一位开始扫描,没有数字的位置枚举该填的数字填上。 填完所有数字后,先判断日期是否合法,再判断该日期是否满足题意要求即可。 这里为了方便,先使用线性筛在 $ O(n) $ 的时间内筛出了所有的质数。从而可以在 $ O(1) $ 的时间内判断任意一个数字是否是质数。 当然,在搜索中途就排除无效日期可以加快搜索效率。 ~~比赛时候代码有些丑,不要介意~~ ```cpp #include <cstdio> #include <algorithm> using namespace std; const int daynum[]={0,31,28,31,30,31,30,31,31,30,31,30,31}; int f[100000005],res[6000005],cnt,date[15],num,ans; char s[15]; inline bool is_run(int y) { if(y%4==0) { if(y%100==0) { if(y%400==0)return true; return false; } return true; } return false; } inline bool legal(int y,int m,int d) { if(m>12||m==0||d==0||y==0)return false; if(m==2) { if(is_run(y)) { if(d>29)return false; return true; } else { if(d>28)return false; return true; } } else { if(d>daynum[m])return false; return true; } } void dfs(int d) { if(d==8) { int y=num/10000,m=(num%10000)/100,d=num%100; if(legal(y,m,d)) if((!f[d])&&(!f[m*100+d])&&(!f[y*10000+m*100+d]))ans++; return; } if(date[d]!=-1) { num=num*10+date[d]; dfs(d+1); num/=10; return; } for(int i=0;i<=9;i++) { if(d==4&&i==2)break; if(d==5&&i==0&&date[d-1]==0)continue; if(d==5&&date[4]*10+i>12)break; if(d==6&&i==4)break; date[d]=i; num=num*10+i; dfs(d+1); date[d]=-1; num/=10; } } int main() { int t; scanf("%d",&t); f[0]=f[1]=1; for(long long i=2;i<=99991231;i++) { if(!f[i])res[++cnt]=i; for(long long j=1;j<=cnt&&i*res[j]<=99991231;j++) { f[i*res[j]]=1; if(i%res[j]==0)break; } } while(t--) { ans=0; scanf("%s",s); for(int i=0;i<8;i++) { if(s[i]=='-')date[i]=-1; else date[i]=s[i]-'0'; } dfs(0); printf("%d\n",ans); } return 0; } ```