给你\(A-J\)的字母组成的日期,形式为\(yyyy/mm/dd\)。现给你\(n\)个这样的串\((n<=1e5)\),问你把字母映射成数字,并且使得所有日期合法且为星期五的最小字典序为什么。
判断星期几可以直接用吉姆拉尔森公式解决。
inline int weekday(int y, int m, int d){
\(\qquad\)if(m <= 2){m += 12, y--;}
\(\qquad\)return (d + 2 * m + 3 * (m + 1) / 5 + y + y / 4 - y / 100 + y / 400) % 7 + 1;
}
因为合法的日期其实很少,就只有几万种,但是\(n\)太大了,但是由于合法日期其实远远比n小,那么这里面其实有很多重复的日期,那么我们先除重,这样就能减少很多判断的地方。
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<ctime>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 100000 + 5;
const int INF = 0x3f3f3f3f;
const ull seed = 131;
const ll MOD = 1e9 + 7;
using namespace std;
inline int weekday(int y, int m, int d){
if(m <= 2){m += 12, y--;}
return (d + 2 * m + 3 * (m + 1) / 5 + y + y / 4 - y / 100 + y / 400) % 7 + 1;
}
int day[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
char ye[maxn][4], mo[maxn][2], da[maxn][2];
string s[maxn];
int n, vis[maxn], mean[20];
int tot, choose[maxn][20], ok;
bool check(int n, int *mean){
for(int i = 1; i <= n; i++){
int y = 0;
for(int j = 0; j < 4; j++) y = y * 10 + mean[ye[i][j] - 'A'];
if(y < 1600 || y > 9999) return false;
int m = 0;
for(int j = 0; j < 2; j++) m = m * 10 + mean[mo[i][j] - 'A'];
if(m < 1 || m > 12) return false;
int d = 0;
for(int j = 0; j < 2; j++) d = d * 10 + mean[da[i][j] - 'A'];
if(d < 1 || d > 31) return false;
if(y % 400 == 0 || (y % 100 != 0 && y % 4 == 0)){
if(m == 2 && d > 29) return false;
if(m != 2 && d > day[m]) return false;
}
else if(d > day[m]) return false;
if(weekday(y, m, d) != 5) return false;
}
return true;
}
void dfs(int cnt){
if(cnt + 'A' > 'J'){
if(check(min(n, 100), mean)){
ok = 1;
for(int i = 0; i <= 9; i++)
choose[tot][i] = mean[i];
tot++;
}
return;
}
for(int i = 0; i <= 9; i++){
if(!vis[i]){
vis[i] = 1;
mean[cnt] = i;
dfs(cnt + 1);
vis[i] = 0;
}
}
}
int main(){
int T, ca = 1;
scanf("%d", &T);
while(T--){
scanf("%d", &n);
for(int i = 1; i <= n; i++) cin >> s[i];
sort(s + 1, s + n + 1);
n = unique(s + 1, s + n + 1) - s - 1;
for(int i = 1; i <= n; i++){
for(int j = 0; j < 4; j++) ye[i][j] = s[i][j];
for(int j = 5; j < 7; j++) mo[i][j - 5] = s[i][j];
for(int j = 8; j < 10; j++) da[i][j - 8] = s[i][j];
}
memset(vis, 0, sizeof(vis));
tot = 0;
dfs(0);
ok = -1;
for(int i = 0; i < tot; i++){
if(check(n, choose[i])){
ok = i;
break;
}
}
printf("Case #%d: ", ca++);
if(ok != -1){
for(int i = 0; i <= 9; i++) printf("%d", choose[ok][i]);
puts("");
}
else{
printf("Impossible\n");
}
}
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章