Is Today Friday? - 题解

标签与难度

标签: 暴力枚举, 全排列, 字符串处理, 日期处理, 实现难度: 1600

题目大意喵~

一位叫做 TangTang 的朋友特别喜欢星期五，他收集了一份列表，里面全是星期五的日期，喵~。这些日期都写成了 yyyy/mm/dd 的格式，比如 2019/08/03。

为了安全起见，TangTang 用一种简单的替换密码加密了这份列表。他把数字 0 到 9 一一对应地换成了大写字母 A 到 J。同一个数字总是被同一个字母替换，不同的数字会被不同的字母替换。

糟糕的是，TangTang 忘记了哪个字母对应哪个数字了！(｡•́︿•̀｡)

我们的任务就是，根据这份加密后的日期列表，帮他找出从 A 到 J 到 0 到 9 的正确映射关系。如果找不到，就说明这是不可能的，呐。

输入格式:

首先是一个整数 T，表示有 T 组测试数据。
每组数据第一行是一个整数 n，表示列表里有 n 个加密后的日期。
接下来 n 行，每行一个加密后的日期字符串。

输出格式:

对于每组数据，输出 "Case #x: "。
如果找到了解，就输出一个10位数的字符串，代表 A 到 J 依次对应的数字。
如果找不到，就输出 "Impossible"。

解题思路分析

喵哈~！看到这道题，我的猫猫直觉告诉我，这一定是个有趣的密码破解游戏！题目的核心是要我们找到一个从字母 A-J到数字 0-9 的一一对应关系。

这种一一对应的关系，不就是数学里的 排列 (Permutation) 嘛！我们有10个字母和10个数字，所以我们要找的其实就是数字 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 的一个排列组合。

那么，总共有多少种可能的排列呢？是 $10!$ (10的阶乘) 种。

10! = 10 \times 9 \times 8 \times \dots \times 1 = 3,628,800

这个数字看起来很大，但对于现在的计算机来说，三百多万次的计算简直是小菜一碟，喵~ 所以，我们可以大胆地采用 暴力枚举 的方法！

我们的策略就是：

生成所有可能的映射：我们生成数字 0 到 9 的所有排列。每一种排列都代表一种可能的密码本。比如，排列 {2, 0, 1, 9, ...} 就代表 A 映射到 2，B 映射到 0，C 映射到 1，D 映射到 9，以此类推。
逐一验证：对于每一种可能的密码本，我们用它来解密题目给出的所有日期。
检查有效性：解密出来的日期必须同时满足两个条件：
- 它是一个 合法的日期 (比如，月份不能是13月，2月最多29天等)。
- 它必须是 星期五！

如果一个密码本能让列表里所有的日期都满足这两个条件，那它就是我们要找的答案啦！如果试完了所有 $10!$ 种可能都找不到，那就说明 TangTang 可能记错了，这个任务是 "Impossible" 的说。

如何实现呢？

生成排列: C++ 的 <algorithm> 库里有一个超级方便的函数 std::next_permutation，它可以帮我们不重不漏地生成下一个排列。我们只需要一个初始有序的数组 {0, 1, ..., 9}，然后在一个 do-while 循环里调用它，就能遍历所有情况啦！
日期合法性检查:
1. 年份 y 必须在 [1600, 9999] 之间。
2. 月份 m 必须在 [1, 12] 之间。
3. 天数 d 必须在 [1, 当月的最大天数] 之间。这里要特别注意闰年的2月有29天哦！
  - 闰年规则: 年份能被4整除但不能被100整除，或者能被400整除。
星期几的计算: 这是一个经典问题，我们可以用 蔡勒公式 (Zeller's Congruence) 来解决。这是一个神奇的数学公式，可以直接算出任何一个公历日期是星期几。公式有很多变体，这里我们用一个比较常见的版本：
$w = (y' + \lfloor \frac{y'}{4} \rfloor + \lfloor \frac{c}{4} \rfloor - 2c + \lfloor \frac{26(m+1)}{10} \rfloor + d - 1) \pmod 7$
其中：
- $d$ 是天数。
- $m$ 是月份。注意：如果月份是1月或2月，要当成上一年的13月和14月来计算。
- $y$ 是年份。同样，如果月份是1月或2月，年份要减1。
- $c$ 是世纪数，即 $\lfloor y/100 \rfloor$ 。
- $y'$ 是世纪内的年份，即 $y \pmod{100}$ 。
- 计算出的 $w$ 可能是负数，所以最后要 (w % 7 + 7) % 7 来保证结果在 [0, 6] 之间。通常 0 代表星期日，1 代表星期一，...，6 代表星期六。题目要求是星期五，所以我们要找的结果是 $w=5$ 。

小优化: 题目给的 n 个日期里可能有重复的，我们只需要对不重复的日期进行验证就行了。可以用 std::set 或者 std::unordered_set 来自动去重，让我们的程序跑得更快一点点，喵~

总结一下我们的算法步骤：

读入所有加密日期，并存入一个 set 中去重。
初始化一个数组 p = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}。
使用 do-while(next_permutation(p.begin(), p.end())) 循环遍历所有排列。
在循环中，对 set 里的每一个加密日期： a. 使用当前的排列 p 解码出 year, month, day。 b. 调用一个 check 函数，该函数内部实现日期合法性验证和蔡勒公式计算，判断该日期是否为合法的星期五。 c. 如果有一个日期验证失败，说明当前排列是错的，立刻跳出内层循环，继续尝试下一个排列。
如果所有日期都验证通过，恭喜！我们找到了答案。打印当前的排列 p，然后结束程序。
如果循环结束了还没找到答案，就输出 "Impossible"。

就是这样，一步一步来，肯定能解决的！加油，喵~！

代码实现

cpp

#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <unordered_set>

// 每月的天数，非闰年
const int days_in_month[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

// 判断是否是闰年，喵~
bool is_leap(int year) {
    return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}

// 检查给定的年月日是否是一个合法的星期五
// 返回 true 如果是，否则返回 false
bool is_valid_friday(int y, int m, int d) {
    // 1. 年份范围检查
    if (y < 1600 || y > 9999) return false;
    
    // 2. 月份范围检查
    if (m < 1 || m > 12) return false;

    // 3. 日期范围检查
    int max_days = days_in_month[m];
    if (m == 2 && is_leap(y)) {
        max_days = 29; // 闰年的二月有29天
    }
    if (d < 1 || d > max_days) return false;

    // 4. 使用蔡勒公式计算星期几
    int temp_y = y;
    int temp_m = m;
    if (temp_m < 3) {
        temp_y--;
        temp_m += 12;
    }

    int c = temp_y / 100;
    int year_in_century = temp_y % 100;
    
    int w = year_in_century + (year_in_century / 4) + (c / 4) - (2 * c) + (26 * (temp_m + 1) / 10) + d - 1;
    
    // 保证结果在 [0, 6] 之间，0是周日，5是周五
    int weekday = (w % 7 + 7) % 7;

    return weekday == 5; // 5 代表星期五
}

// 解决单个测试用例的核心函数
void solve() {
    int n;
    std::cin >> n;
    std::unordered_set<std::string> unique_dates;
    for (int i = 0; i < n; ++i) {
        std::string s;
        std::cin >> s;
        unique_dates.insert(s);
    }

    std::vector<int> p(10);
    // 初始化排列为 0, 1, 2, ..., 9
    std::iota(p.begin(), p.end(), 0);

    do {
        bool is_permutation_valid = true;
        for (const auto& s : unique_dates) {
            // 根据当前排列 p 解码日期
            int year = p[s[0] - 'A'] * 1000 + p[s[1] - 'A'] * 100 + p[s[2] - 'A'] * 10 + p[s[3] - 'A'];
            int month = p[s[5] - 'A'] * 10 + p[s[6] - 'A'];
            int day = p[s[8] - 'A'] * 10 + p[s[9] - 'A'];
            
            // 检查解码后的日期是否为合法的星期五
            if (!is_valid_friday(year, month, day)) {
                is_permutation_valid = false;
                break; // 这个排列不行，赶紧试试下一个！
            }
        }

        if (is_permutation_valid) {
            for (int i = 0; i < 10; ++i) {
                std::cout << p[i];
            }
            std::cout << "\n";
            return; // 找到答案啦，任务完成！
        }

    } while (std::next_permutation(p.begin(), p.end()));

    // 遍历完所有排列都没找到答案
    std::cout << "Impossible\n";
}

int main() {
    // 优化cin和cout的性能，让猫猫跑得更快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    for (int i = 1; i <= t; ++i) {
        std::cout << "Case #" << i << ": ";
        solve();
    }
    return 0;
}

复杂度分析

时间复杂度: $O(T \cdot (10! \cdot N_{unique} \cdot C))$
- $T$ 是测试数据的组数。
- $10!$ 是我们需要检查的总排列数，这是一个常数，约为 $3.6 \times 10^6$ 。
- $N_{unique}$ 是输入中不重复的加密日期数量，最坏情况下等于 $n$ 。
- $C$ 是验证单个日期的常数时间开销，包括解码、日期合法性检查和蔡勒公式计算。
- 因为 $10!$ 是固定的，所以对于单组数据，复杂度可以看作是 $O(N_{unique})$ ，但这个常数因子非常大。不过，由于 $N_{unique}$ 通常不会很大，并且一旦某个日期验证失败就会提前终止内层循环，实际运行速度比最坏情况要快得多。
空间复杂度: $O(N_{unique} \cdot L)$
- 我们使用了一个 unordered_set 来存储所有不重复的加密日期。 $N_{unique}$ 是不重复日期的数量，而 $L$ 是每个日期字符串的长度（这里是常数10）。所以空间开销主要取决于不重复日期的数量。

知识点总结

全排列 (Permutation): 当需要对一组元素的所有可能顺序进行尝试时，全排列是一个核心思想。C++的 std::next_permutation 是实现这一点的强大工具。
暴力枚举 (Brute Force): 当解空间不大时（比如本题的 $10!$ ），暴力枚举所有可能性是一种直接且有效的策略。关键在于正确评估解空间的大小是否在可接受范围内。
日期处理: 这类题目考验的是细心和对细节的把握。
- 闰年判断: 是一个基础但容易出错的知识点。
- 蔡勒公式 (Zeller's Congruence): 计算星期几的标准算法，值得记忆和理解。在编程竞赛中偶尔会出现。
代码结构: 将复杂的逻辑拆分成小的、功能单一的函数（如 is_leap, is_valid_friday）能让主逻辑更清晰，也更容易调试和维护，是个好习惯哦，喵~
STL容器使用: 合理使用 std::vector, std::unordered_set 等容器可以大大简化代码并提高效率。比如用 set 去重就是一个很好的例子。

希望这篇题解能帮到你，喵~！如果还有不懂的地方，随时可以再来问我哦！(ฅ'ω'ฅ)

Is Today Friday? - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​