P1104 生日 · 习题解析｜信息学奥赛算法练功房

0题目原文（本地存了一份）

为什么要在这儿抄一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库。

转录自洛谷 P1104，日期见页头。两边不一致时信原站。

题目描述

cjf 君想调查学校 OI 组每个同学的生日，并按照年龄从大到小的顺序排序。但 cjf 君最近作业很多，没有时间，所以请你帮她排序。

输入格式

输入共有 n + 1 行，第 1 行为 OI 组总人数 n；第 2 行至第 n+1 行分别是每人的姓名 s、出生年 y、月 m、日 d。

输出格式

输出共有 n 行，即 n 个年龄从大到小同学的姓名（如果有两个同学年龄相同，输入靠后的同学先输出）。

说明 / 提示

数据保证，1 < n < 100，1 ≤ |s| < 20。保证年月日实际存在，且年份 ∈ [1960, 2020]。

输入输出样例

输入

3
Yangchu 1992 4 23
Qiujingya 1993 10 13
Luowen 1991 8 1

输出

Luowen
Yangchu
Qiujingya

三个人生日各不相同，所以按生日从早到晚排：1991 → 1992 → 1993。

⚠ 样例里没有同生日的人 —— 也就是说，这道题真正的坑，样例一个字都没提到。

1★★★ 难点只有题面最后那半句

★★★ 「输入靠后的先输出」—— 和 stable_sort 正好反过来

「年龄从大到小」= 生日从早到晚，这没什么好说的。难的是括号里那句：

如果有两个同学年龄相同，输入靠后的同学先输出。

而 std::stable_sort 的保证是「相等的元素保持原有相对顺序」—— 也就是「输入靠前的先」。正好反过来。

⇒ 一看到「相同的按输入顺序」就写 stable_sort，在这道题上是错的。

★ 正解的做法是把输入序号当第四关键字，降序：

if (a.y != b.y) return a.y < b.y;
if (a.m != b.m) return a.m < b.m;
if (a.d != b.d) return a.d < b.d;
return a.idx > b.idx;          // ★ 同一天：输入靠后的先

★★ 这样一来就根本不需要稳定排序 —— cmp 已经能把任意两个人分出先后，排出来的顺序是唯一的。⇒ 少依赖一个前提，就少一个会被换掉的东西。

p1104.cpp★ 这一版就能 AC

// P1104 生日 —— ★ 这一版就能 AC
//
// 按年龄从大到小排 = 按生日**从早到晚**排（生得早的年龄大）。
// ⚠ 而题面最后那半句才是这道题的全部难点：
//
//     「如果有两个同学年龄相同，**输入靠后的同学先输出**」
//
// ★★★ 注意它要的是「**靠后**的先」—— 而 `stable_sort` 保证的是
//   「相等的元素保持原有相对顺序」，也就是「**靠前**的先」。**正好反过来。**
//   ⇒ 一看到「相同的按输入顺序」就写 `stable_sort`，在这道题上是错的（见 p1104Stable.cpp）。
//
// 这里的写法是把**输入序号当第四关键字，降序**：
//   生日相同 ⇒ 序号大的（输入靠后的）排在前面。
// ★ 这样一来就**不需要**稳定排序了 —— cmp 已经能把任意两个人分出先后。

#include <bits/stdc++.h>
using namespace std;

struct Kid { string name; int y, m, d, idx; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<Kid> v(n);
    for (int i = 0; i < n; i++) { cin >> v[i].name >> v[i].y >> v[i].m >> v[i].d; v[i].idx = i; }

    sort(v.begin(), v.end(), [](const Kid& a, const Kid& b) {
        if (a.y != b.y) return a.y < b.y;                 // 年份小 = 生得早 = 年龄大
        if (a.m != b.m) return a.m < b.m;
        if (a.d != b.d) return a.d < b.d;
        return a.idx > b.idx;                             // ★ 同一天：输入靠后的先输出
    });

    for (int i = 0; i < n; i++) cout << v[i].name << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

2另一条也对的路：把输入倒过来

p1104Rev.cpp也能 AC

// 另一种也能 AC 的写法：**把输入倒过来**，再用 stable_sort
//
// 想法：`stable_sort` 保「输入靠前的先」，而题目要「输入靠后的先」——
// 那就先把序列整个反过来，「靠后」就变成了「靠前」。
//
// ★ 它和 p1104.cpp（写第四关键字）是**两条完全不同的路**，
//   放在一起对拍，比自己和自己比有意义得多。
// ⚠ 但要注意：这一版**依赖 stable_sort 的稳定性**，把 `stable_sort` 换成 `sort` 就错。
//   而 p1104.cpp 那一版换成 `stable_sort` 也照样对 —— 它根本不依赖稳定性。
//   ⇒ **「不依赖稳定性」比「依赖它」更稳**：少一个前提，就少一个会被换掉的东西。

#include <bits/stdc++.h>
using namespace std;
struct Kid { string name; int y, m, d; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<Kid> v(n);
    for (int i = 0; i < n; i++) cin >> v[i].name >> v[i].y >> v[i].m >> v[i].d;
    reverse(v.begin(), v.end());                          // ★ 先整个反过来
    stable_sort(v.begin(), v.end(), [](const Kid& a, const Kid& b) {
        if (a.y != b.y) return a.y < b.y;
        if (a.m != b.m) return a.m < b.m;
        return a.d < b.d;
    });
    for (int i = 0; i < n; i++) cout << v[i].name << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

想法很直接：stable_sort 保「靠前的先」，那就先把序列整个 reverse 一下，「靠后」就变成了「靠前」。

⚠ 但它依赖 stable_sort 的稳定性 —— 把 stable_sort 换成 sort 就错。而上一版换成 stable_sort 也照样对。⇒ 两条路都能过，但前提数不一样。

3两个 WA，一个「确定地反了」，一个「不确定」

p1104Stable.cpp⚠ stable_sort 用反了

// ⚠ 故意写错的：一看到「相同的按输入顺序」就用了 stable_sort
//
//     stable_sort(v.begin(), v.end(), 只比 y/m/d 的 cmp);
//
// ★★★ `stable_sort` 保证的是「相等的元素**保持原有相对顺序**」——
//   也就是**输入靠前的排在前面**。
//   而这道题要的是「**输入靠后的先输出**」。**正好反过来。**
//
// ⇒ 它在「没有人同生日」的数据上完全正确，一旦有人同生日就把那两个人的顺序输反。
// ★ 所以它是那种「样例过、随机数据也常常过、专门造同生日才抓得到」的错
//   —— 而 n < 100、年份只有 [1960, 2020]，**随机数据里同生日其实不算罕见**，
//     这一条可以量（见页面上那张表）。

#include <bits/stdc++.h>
using namespace std;
struct Kid { string name; int y, m, d; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<Kid> v(n);
    for (int i = 0; i < n; i++) cin >> v[i].name >> v[i].y >> v[i].m >> v[i].d;
    stable_sort(v.begin(), v.end(), [](const Kid& a, const Kid& b) {
        if (a.y != b.y) return a.y < b.y;
        if (a.m != b.m) return a.m < b.m;
        return a.d < b.d;
    });
    for (int i = 0; i < n; i++) cout << v[i].name << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

p1104NoIdx.cpp⚠ sort 且没写第四关键字

// ⚠ 故意写错的：用 sort，而且 cmp 里没有第四关键字
//
//     sort(v.begin(), v.end(), 只比 y/m/d 的 cmp);
//
// 同生日的两个人，`sort` 把谁放前面**是不确定的**（标准不保证，也不保证稳定）。
// ⇒ 它比 p1104Stable.cpp **更糟**：那一版至少是「确定地反了」，
//   这一版是「**不确定**」—— 换个编译器版本、换个数据规模，结果都可能变。
//
// ★ 这两版放在一起，正好说明「稳定」到底是什么：
//   **稳定 = 相等元素的相对顺序有保证。** 有保证不等于是你要的那个顺序，
//   但至少它是**可预期**的；而不稳定连预期都谈不上。

#include <bits/stdc++.h>
using namespace std;
struct Kid { string name; int y, m, d; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<Kid> v(n);
    for (int i = 0; i < n; i++) cin >> v[i].name >> v[i].y >> v[i].m >> v[i].d;
    sort(v.begin(), v.end(), [](const Kid& a, const Kid& b) {
        if (a.y != b.y) return a.y < b.y;
        if (a.m != b.m) return a.m < b.m;
        return a.d < b.d;
    });
    for (int i = 0; i < n; i++) cout << v[i].name << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★ 这两版放在一起，正好说明「稳定」到底是什么

Stable 版：同生日时确定地把顺序输反了（它保证「靠前的先」，而题目要「靠后的先」）。
NoIdx 版：同生日时谁在前不确定 —— 标准既不保证稳定，也不保证任何特定顺序。

⇒ 稳定 = 相等元素的相对顺序有保证。 有保证不等于是你要的那个顺序，但至少它是可预期的；而不稳定连预期都谈不上 —— 换个编译器版本，结果可能就变了。

⚠ 所以本页的断言只钉这两版「和正解不一致」，不钉它们具体输出了什么。

4★★★ 关键的一步：这个坑，样例和「照题面随机」都抓不到

p1104Brute.cpp参照物：直接照题面做

// P1104 的对拍参照物：照题面**一个字一个字**做，不用任何排序库
//
// 反复扫描：每一轮挑出「生日最早；同一天时**输入序号最大**」的那个人输出，
// 然后把他标记掉。⇒ O(n²)，但 n < 100，随便跑。
//
// ★ 它和三个被测版本**没有共用任何排序逻辑** —— 那三版都在调 sort / stable_sort，
//   这一版连比较函数都没有，只有一层「谁更早」的直接判断。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<string> name(n);
    vector<int> y(n), m(n), d(n);
    for (int i = 0; i < n; i++) cin >> name[i] >> y[i] >> m[i] >> d[i];
    vector<bool> used(n, false);
    for (int k = 0; k < n; k++) {
        int best = -1;
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;
            if (best < 0) { best = i; continue; }
            if (y[i] != y[best]) { if (y[i] < y[best]) best = i; continue; }
            if (m[i] != m[best]) { if (m[i] < m[best]) best = i; continue; }
            if (d[i] != d[best]) { if (d[i] < d[best]) best = i; continue; }
            if (i > best) best = i;                       // ★ 同一天：输入靠后的先
        }
        used[best] = true;
        cout << name[best] << '\n';
    }
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

p1104Gen.cpp生成器：四个档位

// 数据生成器（P1104 对拍用）：`./p1104Gen <seed> [level]`
//
//   level 0（默认）**照题面随机**：年 ∈ [1960, 2020]、月日合法 —— 可选日期约 2.2 万种
//   level 1        ★ **年份压到 3 年**：同生日一下子变得很常见
//   level 2        ★ **所有人同一天**：全是并列
//   level 3        ★★ **照题面随机，但 n 顶到 99**（题面是 n < 100）
//                  —— 和 level 0 只差一个 n：日期空间没变，人多了，撞的概率却完全不同。
//                  ★ 这就是**生日悖论**：撞不撞看的是「两两配对数」n(n−1)/2，不是 n。
//
// ★ 这三档量的是同一件事：**「同生日」有多密**。
//   三个错误版本（stable_sort 用反了 / 没写第四关键字）**只在有人同生日时才现形** ——
//   而题面的日期空间有两万多种、n 又不到 100，随机数据里撞上的概率**不高但也不低**，
//   正好是「本地随便测测过了、交上去挂几个点」的那种。
//   ⇒ 又一次「**密度才是覆盖能力**」（第 7 章 P1102 那条）。
//
// ⚠ 姓名要互不相同 —— 否则输出里分不清是哪个人，对拍会「一致地输出垃圾」。

#include <bits/stdc++.h>
using namespace std;
static mt19937 rng;
static int ri(int lo, int hi) { return lo + (int)(rng() % (unsigned)(hi - lo + 1)); }
static const int MDAY[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

int main(int argc, char** argv) {
    rng.seed((argc > 1) ? (unsigned)atoi(argv[1]) : 1);
    int level = (argc > 2) ? atoi(argv[2]) : 0;
    int n = (level == 3) ? 99 : ri(2, 12);
    printf("%d\n", n);
    for (int i = 0; i < n; i++) {
        int y, m, d;
        if (level == 2) { y = 2000; m = 6; d = 15; }
        else if (level == 1) { y = ri(1999, 2001); m = ri(1, 12); d = ri(1, MDAY[m]); }
        else if (level == 3) { y = ri(1960, 2020); m = ri(1, 12); d = ri(1, MDAY[m]); }
        else { y = ri(1960, 2020); m = ri(1, 12); d = ri(1, MDAY[m]); }
        printf("name%02d %d %d %d\n", i, y, m, d);         // 姓名互不相同
    }
    return 0;
}

点一下即可编辑

输出

点「运行 ▶」看结果

每档 300 轮，和参照物不一致的轮数：

档位	正解 ≡ 参照物	`Rev` ≡ 参照物	⚠ `Stable` 被抓	⚠ `NoIdx` 被抓
`level 0` 照题面随机，`n ≤ 12`	300 / 300	300 / 300	★★★ 0	★★★ 0
`level 3` ★ 照题面随机，`n = 99`	300 / 300	300 / 300	★ 49	★ 30
`level 1` 年份压到 3 年	300 / 300	300 / 300	6	6
`level 2` 所有人同一天	300 / 300	300 / 300	300	300

★★★ 第一行和第二行只差一个 n —— 日期空间一个字没改

两行用的是同一套随机策略（年 ∈ [1960, 2020]、月日合法，约 2.2 万种日期）。唯一的区别是人数：n ≤ 12 对 n = 99。

n ≤ 12：300 轮，一次都抓不到。
n = 99（题面上限是 n < 100）：Stable 抓到 49 次。

⚠ 而 NoIdx（不稳定那版）在同一档只被抓 30 次，比 Stable 的 49 还少 —— 它有时候「碰巧」排对了。⇒ 「不确定」的错比「确定地反了」的错更难抓，这正是它更危险的地方。

⇒ 这就是生日悖论：撞不撞看的是「两两配对数」n(n−1)/2，不是 n。 12 个人只有 66 对，99 个人有 4851 对 —— 差 73 倍。

★★ 而这一条对写生成器的意思很直接： 「照题面随机」还不够，还要照题面的 n 顶格。 我第一版生成器随手写了 n ≤ 12，于是这个 bug 是精确的 0 —— 不是它难抓，是我的数据太小。

⚠ 顺带：level 1 反而比 level 3 抓得少（6 vs 49）

level 1 把年份压到 3 年，看起来「同生日会更多」—— 可它只抓到 6/300，比顶格随机的 49/300 还少。

原因是它的 n 仍然是 ≤ 12：压值域和加人数是两个旋钮，而这道题上人数那个更有效 （3 年 × 365 天还有一千多种日期，12 个人照样撞不上）。

⇒ 又一次：旋钮拧对了没有，要量了才知道（第 7 章 P1147 那条：专门造的档位可能反而抓得更少）。

5一张总表

版本	做法	依赖稳定性吗	对拍（1200 轮）	结果
`p1104`	序号当第四关键字（降序）	不依赖	1200 / 1200	★ AC
`p1104Rev`	先 `reverse` 再 `stable_sort`	⚠ 依赖	1200 / 1200	★ AC
⚠ `p1104Stable`	直接 `stable_sort`	依赖，且用反了	被抓 355	✗ WA
⚠ `p1104NoIdx`	`sort`，cmp 少一句	——	被抓 336	✗ WA（不确定）

这一页记住三句话

★★★ stable_sort 保的是「输入靠前的先」，而这道题要「输入靠后的先」——正好反过来。 ⇒ 看到「相同的按输入顺序」先问一句：是哪个方向？
★★ 把序号写进 cmp，就不需要稳定排序了。 少依赖一个前提，就少一个会被换掉的东西。
★★★ 「照题面随机」还不够，还要照题面的 n 顶格。 同一套随机策略，n ≤ 12 抓 0 次，n = 99 抓 49 次 —— 日期空间一个字没改。

洛谷 P1104 生日

0题目原文（本地存了一份）

输入

输出

1★★★ 难点只有题面最后那半句

2另一条也对的路：把输入倒过来

3两个 WA，一个「确定地反了」，一个「不确定」

4★★★ 关键的一步：这个坑，样例和「照题面随机」都抓不到

5一张总表