2019牛客暑假多校訓練賽第六場G題 Is Today Friday? （全排列）

題目連結：https://ac.nowcoder.com/acm/contest/886/G

題意：給定由A到J組成的字元串，A到J唯一代表0到9中的數字（雙射），問是否存在一個合法的雙射使得所有的給定的字元串都是星期五（現實中的星期五），并且要使得A到J對應的0到9的字典序最小

思路：運用蔡勒公式，然後從字典序最小的開始全排列一個一個判斷

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,t,cas=1;
string s[N];
int a[10];
int days[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
inline bool check(int year, int mon, int day){
    if(year<1600)return false;
    if(mon==0||mon>12)return false;
    int tmp=days[mon];
    if(mon==2)if((year%4==0&&year%100!=0)||year%400==0)tmp=29;
    if(day==0||day>tmp)return false;
    ///蔡勒公式
    if(mon<=2)mon+=12,year--;
    int c=year/100;
    year%=100;
    int w=((year+year/4+c/4-2*c+(26*(mon+1))/10+day-1)%7+7)%7;
    return w==5;
}
int main(){
    scanf("%d",&t);
    while(t--){
        printf("Case #%d: ", cas++);
        for(int i=0;i<=9;i++)a[i]=i;
        scanf("%d",&n);
        for(int i=0;i<n;i++)cin>>s[i];
        sort(s,s+n);
        int realn=unique(s,s+n)-s;
        bool flag=false;
        do{
            bool test=true;
            for(int i=0;i<realn;i++){
                int year=a[s[i][0]-'A']*1000+a[s[i][1]-'A']*100+a[s[i][2]-'A']*10+a[s[i][3]-'A'];
                int mon=a[s[i][5]-'A']*10+a[s[i][6]-'A'];
                int day=a[s[i][8]-'A']*10+a[s[i][9]-'A'];
                if (!check(year,mon,day)){
                    test=false;break;
                }
            }
            if(test){
                flag=true;
                for(int i=0;i<10;i++)printf("%d",a[i]);
                printf("\n");
                break;
            }
        }while(next_permutation(a,a+9+1));
        if(!flag)printf("Impossible\n");
    }
    return 0;
}