2019牛客第六场G题 (Is Today Friday) 暴力

题意：给你一串日期，这些日期都是星期五。但是每个字符都被加密了，以一种简单的映射（根据题意，是一个双射）规则比如A映射到0，B映射到1。要求一个合法的字典序最小的映射。日期的数量不超过100000

题解：这题就是个暴力。虽然看上去复杂度会很大()，但是直觉上（不知道能否证明这个结论）对于一个加密后的日期，满足这个日期在解密后是星期五的日期非常少（随机举了几个例子后发现最大的就是样例中的CABJ/AI/AC有56760种合法排列）。因此在记录所有的合法排列时候遍历所有日期然后删除其中的不合法元素，实际上在遍历过程中会删去非常多的点（同样，我还是不会证）

btw，比赛的时候写的代码判断2月29号的时候搞错了，补题的时候（蔡队一听我wa了就说肯定这个地方搞错了，clsnb！） 才发现。。。

#include <algorithm>
#include <array>
#include <cstdio>
#include <set>
#include <string>
#include <unordered_set>
#include <vector>
using namespace std;
// const int maxn = 1e5 + 10;
int cal1(int y, int m, int d)
{
    if (m == 1 || m == 2)
        m += 12, y--;
    int w = (d + 2 * m + 3 * (m + 1) / 5 + y + y / 4 - y / 100 + y / 400) % 7;
    return ++w;
}

int mo[20] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int leap(int x)
{
    if (x % 400 == 0)
        return 1;
    if (x % 100 == 0)
        return 0;
    if (x % 4 == 0)
        return 1;
    return 0;
}

bool judge(int y, int m, int d)
{
    if (y < 1600)
        return false;
    if (m <= 0 || m > 12)
        return false;
    int l = leap(y);
    mo[2] += l;
    if (d > mo[m] || d == 0)
    {
        mo[2] -= l;
        return false;
    }
    mo[2] -= l;
    return cal1(y, m, d) == 5;
}

array<int, 10> per;
auto change = [](char ch, array<int, 10> p) { return p[ch - 'A']; };
bool go(string str, array<int, 10> p)
{
    int y = change(str[0], p) * 1000 + change(str[1], p) * 100 + change(str[2], p) * 10 + change(str[3], p);
    int m = change(str[5], p) * 10 + change(str[6], p);
    int d = change(str[8], p) * 10 + change(str[9], p);
    return judge(y, m, d);
}

int main()
{
    int round;
    scanf("%d", &round);
    for (int ca = 1; ca <= round; ca++)
    {
        int n;
        scanf("%d", &n);
        for (int i = 0; i < 10; i++)
        {
            per[i] = i;
        }
        unordered_set<string> se;
        for (int i = 0; i < n; i++)
        {
            static char s[12];
            scanf("%s", s);
            se.emplace(s);
        }
        set<array<int, 10>> possible;
        do
        {
            if (go(*se.begin(), per))
            {
                possible.insert(per);
            }
        } while (next_permutation(per.begin(), per.end()));
        for (auto &s : se)
        {
            if (possible.empty())
                break;
            for (auto it = possible.begin(); it != possible.end();)
            {
                auto tmp = it;
                tmp++;
                if (!go(s, *it))
                {
                    possible.erase(it);
                }
                it = tmp;
            }
        }
        printf("Case #%d: ", ca);
        if (possible.empty())
        {
            puts("Impossible");
        }
        else
        {
            for (int i = 0; i < 10; i++)
            {
                printf("%d", (*possible.begin())[i]);
            }
            puts("");
        }
    }
}