奇迹
题目 奇迹
思路分析
非常好的题目 虽然有几个tle 但是没关系 锻炼dfs思路
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using Pll = pair<ll,ll>;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
const int inf = 0x3f3f3f3f;
int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool is_leap(int y){
return (y%4==0 && y%100!=0) || (y%400==0);
}
int get_days(int y,int m){
return days[m]+(m==2 && is_leap(y));
}
void next_day(int &y,int &m,int &d){
d++;
if(d>get_days(y,m)){
d=1;
m++;
if(m>12){
m=1;
y++;
}
}
}
bool check_date(int y,int m,int d){
if(y<1 || y>9999) return false;
if(d<1 || d>get_days(y,m)) return false;
if(m<1 || m>12) return false;
return true;
}
bool is_prime(int n){
if(n<2) return false;
for(int i=2;i<=n/i;i++){
if(n%i==0){
return false;
}
}
return true;
}
int ans=0;
void dfs(string &s,int pos){
if(pos==8){
int year=stoi(s.substr(0,4));
int month=stoi(s.substr(4,2));
int day=stoi(s.substr(6,2));
if(!check_date(year,month,day)) return;
int day2=stoi(s.substr(6,2));
int md4=stoi(s.substr(4,4));
int ymd8=stoi(s);
if(is_prime(day2) && is_prime(md4) && is_prime(ymd8)){
ans++;
}
return;
}
if(s[pos]!='-'){
dfs(s,pos+1);
}else{
for(char c='0';c<='9';c++){
s[pos]=c;
dfs(s,pos+1);
s[pos]='-';
}
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T;cin>>T;
while(T--){
string s;cin>>s;
ans=0;
dfs(s,0);
cout<<ans<<endl;
}
return 0;
}
💬 评论