主题

2020—2025 的第一题。

题目

今天是小 Q 的生日，他得到了 张卡牌作为礼物。这些卡牌属于火爆的「决斗怪兽」，其中第 张卡代表一只攻击力为 、防御力也为 的怪兽。

一场游戏分为若干回合。每回合，小 Q 会选择某只怪兽 以及另一只怪兽 （ ），并让怪兽 向怪兽 发起攻击。此时，若怪兽 的攻击力小于等于怪兽 的防御力，则无事发生；否则，怪兽 的防御被打破，怪兽 退出游戏不再参与到剩下的游戏中。一只怪兽在整场游戏中至多只能发起一次攻击。当未退出游戏的怪兽都已发起过攻击时，游戏结束。

小 Q 希望决定一组攻击顺序，使得在游戏结束时，未退出游戏的怪兽数量尽可能少。

限制

化为配对

一只怪兽的两种身份互不干扰：它至多发起一次攻击，也只可能被消灭一次。于是「安排攻击顺序」这件事可以看成在怪兽之间做一次配对：每一对里，攻击力大的那只消灭攻击力小的那只。

证明：每次成功消灭都消耗掉一只攻击者（它此后再也不能攻击）与一只被消灭者，两者都是原本的怪兽；同一只怪兽重复使用不可能，所以全部成功消灭对应一组配对。反过来，给定一组配对，让每对中攻击力较大的那只去攻击较小的那只即可实现这组配对，中间不会互相干扰。

贪心：排序加双指针

把怪兽按攻击力升序排列： 。

证明：设某个最优解第一次与贪心不一致时，贪心用 消灭了当前最小的怪兽 ，而它让某只怪兽 消灭了别的目标。把这一对换成 消灭 ： 是当前能消灭 的最小攻击力，替换后不违反条件，而 被空出来，还能继续与后面尚未被消灭的怪兽配对。于是总存在一个包含贪心选择的最优解，归纳可得贪心最优。

参考实现

1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5    int n;
6    cin >> n;
7    vector<int> a(n);
8    for (int i = 0; i < n; i++)
9        cin >> a[i];
10    sort(a.begin(), a.end());
11    for (int i = 0, j = 1; i < n; i++) {
12        while (j < n && a[j] == a[i])
13            j++;
14        if (j == n) {
15            cout << n - i << '\n';
16            break;
17        }
18        // j打死i
19        j++;
20    }
21}

实现要点

• 输出的是「未被消灭的怪兽数」 ，与题目要求的方向一致；不需要像另一种写法那样先求消灭数再相减。
• while (j < n && a[j] == a[i]) j++; 这一句是把「严格大于」落实成代码的关键：攻击力相同的怪兽互相打不动，所以 要跳过整整一段相等的值。
• 只会向右移动，全程 ；加上排序是 。
• 循环靠 break 结束：一旦 到末尾，后面更大的 同样找不到攻击者，答案已经确定。

部分分

官方报告的口径是：前 15 个测试点可以用搜索与剪枝拿到 分，满分做法「需要一定的思维能力，但相对容易想到」。

题目

小 Y 有一把五个拨圈的密码锁，每个拨圈上是从 到 的数字，并且从 到 循环。

她的锁车方式是从正确密码开始随机转动仅一次：每次以某个幅度仅转动一个拨圈，或者同时转动两个相邻的拨圈，此时两个拨圈转动的幅度相同——可以把 转成 ，但不会转成 。

小 Y 记下了锁车后密码锁的 个状态，这 个状态都不是正确密码。求可能的正确密码个数：每个这样的密码都要能按上述方式产生给出的全部 个状态。

限制

• 每个状态给出五个 到 之间的整数

转动关系对称

设 是一个给出的状态， 是一个候选密码。把小 Y 的动作看成状态之间的一次转动关系 。

证明：一次转动只做两件事之一，都是在若干位置上把数字加上同一个幅度 （模 ）：

• 转一个拨圈：位置集 ；
• 转两个相邻拨圈：位置集 。

反过来从 出发，把同样的位置集上的数字加上 ，就回到 ；当 时 也落在 到 之间，所以这也是一次合法的转动。

正向难，反向容易

要求的是「对每个给出的状态 ， 都能一次转动得到 」。直接判定一个候选 是否满足，需要逐个状态比较不同的位数，还要分类讨论不同的形态。

利用引理 1 把方向倒过来：

一个状态 被数到的次数，正好是「能一次转动得到 的给出状态个数」。于是

给出的状态都不是正确密码这一条不需要单独处理：从 出发转一次一定改变至少一个拨圈（幅度 ），所以 自己不会被数到。

枚举规模

每个给出状态 要枚举多少种转动？

状态只有五位十进制数，直接编码成一个整数：

用一个长度为 的数组 计数，最后统计 的 的个数。总复杂度 。

参考实现

1#include <bits/stdc++.h>
2using namespace std;
3int cnt[100000];
4int s[5], t[5];
5void count() {
6  // {0, 0, 1, 1, 5} => 115
7  int x = 0;
8  for (int i = 0; i < 5; i++)
9    x = x * 10 + t[i];
10  cnt[x]++;
11}
12
13int main() {
14  int n;
15  cin >> n;
16  for (int _ = 0; _ < n; _++) {
17    for (int i = 0; i < 5; i++)
18      cin >> s[i];
19    for (int j = 1; j < 10; j++) { //转动幅度
20      // 转一个轮
21      for (int i = 0; i < 5; i++) {
22        for (int k = 0; k < 5; k++) {
23          if (k == i)
24            t[k] = (s[k] + j) % 10;
25          else
26            t[k] = s[k];
27        }
28        count();
29      }
30      //转两个相邻的轮
31      for (int i = 0; i < 4; i++) {
32        for (int k = 0; k < 5; k++) {
33          if (k == i || k == i + 1)
34            t[k] = (s[k] + j) % 10;
35          else
36            t[k] = s[k];
37        }
38        count();
39      }
40    }
41  }
42
43  int ans = 0;
44  for (int i = 0; i < 100000; i++)
45    if (cnt[i] == n)
46      ans++;
47  cout << ans << '\n';
48
49  return 0;
50}

实现要点

• 计数数组开 ，下标就是五位状态的十进制编码；x = x * 10 + t[i] 这一句保留前导零，例如 0 0 1 1 5 编成 。
• 幅度循环写成 j = 1..9，不需要 j = 0（那是没转动），也不需要 （模 后与 到 重复）。
• 答案要统计的是 而不是 ：只有能被全部 个状态转到的候选才算正确密码。
• 换方向枚举的好处是判定被换成了计数，不需要判断「不同的位数是 、 还是 」，也就不用讨论那些边界。

题目

算法协会招收了 个新成员（ 为偶数），要把他们分到三个部门。第 个成员对第 个部门的满意度是 ，一个分配方案的满意度是所有人对自己部门的满意度之和。

如果第 个成员被分到第 个部门，则方案的满意度为

小 L 不希望某个部门人数过多：方案中不能有部门被分配多于 个成员。求满足要求的方案里满意度的最大值。

限制

• ， 为偶数

无约束最优解

先不考虑人数限制：让每个人都选自己最满意的部门，得到的满意度之和记为 。这个 是一切合法方案的上界，因为每个人在合法方案里的满意度都不超过他的最大值。

问题只剩下：为了满足人数限制，最少要损失多少满意度。

证明：若有两个部门的人数都超过 ，则这两个部门的人数之和超过 ，而所有部门的人数之和恰好是 ，矛盾。

于是只需处理唯一超标的那个部门。

调出多少人

设超标部门的人数为 ，需要调出 人。

证明：超标部门之外的总人数是 ，所以其中任何部门的人数都不超过 。从超标部门调出 人后，任何其他部门至多增加 人，于是至多达到

调哪些人

一个人从最优部门改到次优部门，满意度会下降

称为这个人的损失。因为超标部门之外的人数不会超标，所以每个人只需要考虑去次优部门，不必考虑第三选择。

证明：任何合法方案都必须把超标部门的至少 个人调出去，而每调出一个人至少损失 ，所以任何方案的总满意度不超过 减去「 个最小损失之和」。另一方面，取损失最小的 个人调出，由引理 2 是合法的，恰好达到这个界。

把每个人的三个满意度排序，取最小的 个损失只需要一次排序，总复杂度 。

参考实现

1#include <bits/stdc++.h>
2using namespace std;
3
4const int maxn = 1e5 + 5;
5struct S {
6    int myd;
7    int id;
8};
9S a[maxn][3];
10
11bool cmp(S x, S y) {
12    return x.myd > y.myd;
13}
14
15void solve() {
16    int n;
17    cin >> n;
18    vector<int> cnt(3);
19    int ans = 0;
20    for (int i = 0; i < n; i++) {
21        for (int j = 0; j < 3; j++) {
22            cin >> a[i][j].myd;
23            a[i][j].id = j;
24        }
25        sort(a[i], a[i] + 3, cmp);
26        cnt[a[i][0].id]++;
27        ans += a[i][0].myd;
28    }
29    for (int i = 0; i < 3; i++)
30        if (cnt[i] > n / 2) {
31            vector<int> loss;
32            for (int j = 0; j < n; j++) {
33                if (a[j][0].id == i) {
34                    loss.push_back(a[j][0].myd - a[j][1].myd);
35                }
36            }
37            sort(loss.begin(), loss.end());
38            ans -= accumulate(loss.begin(), loss.begin() + cnt[i] - n / 2, 0);
39        }
40    cout << ans << '\n';
41}
42
43int main() {
44    int T;
45    cin >> T;
46    while (T--) {
47        solve();
48    }
49}

实现要点

• 三个满意度用结构体 S{myd, id} 保存并排序：a[i][0] 是最优部门，a[i][1] 是次优部门，损失就是两者之差；存 id 是为了知道最优部门是哪一个。
• a 与排序都开在全局 / 函数外层，每组数据都会重新赋值，不需要额外清空。
• 求和用 int 就够（ 、 ，总和不超过 ），但如果换成 long long 更稳妥。
• accumulate(loss.begin(), loss.begin() + cnt[i] - n / 2, 0) 取的是排序后最小的 个损失之和； 一定不超过 loss.size()，因为超标部门里的人数就是 。
• 损失也可以用值域计数排序做到线性（值域 ），但 时直接排序已经足够。

部分分

题目

机场分为国内区与国际区：国内航班只能停靠国内区的廊桥，国际航班只能停靠国际区的廊桥；没有空闲廊桥时飞机停在远机位。

L 市新建的机场一共有 个廊桥，廊桥的使用遵循「先到先得」：每架飞机抵达后，如果相应的区还有空闲廊桥就停靠廊桥，否则停远机位。机场只有一条跑道，因此不存在两架飞机同时抵达。

给定未来一段时间两区飞机的抵达与离开时刻，请把 个廊桥分配给国内区与国际区，使停靠廊桥的飞机数量最多。

限制

• 抵达时刻 与离开时刻 都是正整数，且

直接做法的代价

分配方案有 种，若对每种方案都重新模拟一遍，每次模拟是 ，总代价 ，在 时不可接受。

证明：国内航班只停国内区，国际航班只停国际区，两区的飞机互不竞争，模拟过程完全独立。给定国内区 个廊桥后，国内区能停多少架只由国内航班自身的时刻决定。

于是只需要两个数组 与 ，答案是

逐个廊桥贪心

把「先到先得」按廊桥拆开看：第 个廊桥服务的飞机，是「抵达最早的飞机，接着是抵达时刻在其离开之后的最早飞机，再接着……」

证明思路（对 归纳）：第 个廊桥拿到的一定是抵达最早的飞机；把它的整条链去掉之后，剩下的问题与原问题同形。而「先到先得」中，若 个廊桥能停靠的飞机集合固定，那么编号最小的那个廊桥必然服务这条链——否则可以把链上的飞机整体换到编号最小的空闲廊桥上，不减少总数。

有序表实现

总代价 次 map 操作加上 的建表。

参考实现

1#include <bits/stdc++.h>
2using namespace std;
3
4int n;
5
6vector<int> solve(int m) {
7  map<int, int> t;
8  for (int i = 0; i < m; i++) {
9    int a, b;
10    cin >> a >> b;
11    t.insert({a, b});
12  }
13  vector<int> cnt(n + 1);// cnt[i]：停在第i个廊桥的飞机的数量
14  for (int i = 1; i <= n; i++) {
15    int x = 0;// 当前时刻
16    while (1) {
17      auto it = t.upper_bound(x);
18      if (it == t.end())
19        break;
20      cnt[i]++;
21      x = it->second;
22      t.erase(it);
23    }
24  }
25  for (int i = 1; i <= n; i++)
26    cnt[i] += cnt[i - 1];
27  return cnt;
28}
29
30int main() {
31  int m1, m2;
32  cin >> n >> m1 >> m2;
33  vector<int> c1 = solve(m1);
34  vector<int> c2 = solve(m2);
35
36  int ans = 0;
37  for (int i = 0; i <= n; i++)
38    ans = max(ans, c1[i] + c2[n - i]);
39  cout << ans << '\n';
40}

实现要点

• upper_bound(x) 是「抵达时刻严格大于 」：一架飞机在时刻 离开，则另一架在时刻 抵达的飞机不再复用它占用的廊桥。想清楚这一点再用，是这道题最容易写错的地方。
• map 以抵达时刻为键，这一点依赖题目「只有一条跑道、不存在同时抵达」的保证；若数据里出现相同抵达时刻，insert 会丢掉后一架飞机。
• solve 直接在函数里读入：两区各调用一次，各自读自己的 行，不需要先把数据存下来。
• 前缀和的语义是「前 个廊桥一共停靠的飞机数」，正是引理 2 里的 ； 可能大于 ，此时数组后半段都是 ，取用时不会越界。

题目

天文学家们使用儒略日来表达时间。儒略日定义为从公元前 年 月 日正午 点起，到此后某一时刻间所经过的天数，不满一天者用小数表达。给定一个不含小数部分的儒略日，请计算它对应的公历日期。

输出时，公元后的年份写成 日 月 年，公元前年份写成 日 月 年 BC。

限制

• ，年份答案不超过

公历规则

• 公元 年 月 日（含）以后适用格里高利历：当年份是 的倍数，或是 的倍数但不是 的倍数时，该年为闰年。
• 公元 年 月 日（含）至 月 日（含）不存在，这些日期被删除，该年 月 日之后为 月 日。
• 公元 年 月 日（含）以前适用儒略历：只要年份是 的倍数就是闰年。

注意公元零年并不存在，即公元前 年的下一年是公元 年。因此公元前 年、前 年、前 年……的年份应视为闰年。

天文纪年与闰年

用天文纪年表示年份：公元前 年记作 ，公元前 年记作 ，依此类推。这样「公元前 、、……年是闰年」就等价于

年首天数

就是按这个式子算的：先用「年数乘 」把整年跳过去，再加上闰年多出来的天数。

闰年前缀

要能以 求出，否则二分里每次判定都会变慢。把 分成两段：

于是 是 的单调不减函数，可以对它做二分。

二分年份

要求的是第 天，即找

单个询问的二分代价是 。

年内逐日

算出年份之后，从 出发（ 时取 ，同样跳过公元 年），在这一年里按月、按日累加：

单个询问的总代价是 ， 时约为 次运算。

参考实现

1int n_run(int y) {                       // y 年之前（不含 y 年）的闰年个数
2  if (y <= 1600) {
3    return (4713 + y + (y < 0) + 3) / 4;
4  }
5  y -= 1600;
6  return n_run(1600) + y / 4 - y / 100 + y / 400;
7}
8
9bool is_run(int y) {
10  if (y < 0)
11    return -y % 4 == 1;
12  if (y <= 1582)
13    return y % 4 == 0;
14  return y % 400 == 0 or (y % 4 == 0 and y % 100 != 0);
15}
16
17int days[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
18
19long long n_day(int y) {                 // 儒略日 0 到 y 年 1 月 1 日的天数
20  long long ans = (y + 4713 + (y < 0)) * 365LL + n_run(y);
21  if (y >= 1582)
22    ans -= 10;
23  return ans;
24}
25void solve(long long x) {
26  int l = -4713, r = 1000000000;
27  // 最小的 y 使 n_day(y) >= x + 1
28  while (l <= r) {
29    int y = (l + r) / 2;
30    if (y == 0)
31      y = 1;
32    if (n_day(y) >= x + 1) {
33      r = y - 1;
34      if (r == 0)
35        r = -1;
36    } else {
37      l = y + 1;
38      if (l == 0)
39        l = 1;
40    }
41  }
42  int y = l;
43  int py = y == 1 ? -1 : y - 1;
44  long long c = n_day(py);
45  for (int m = 1; m <= 12; m++) {
46    int t = days[m];
47    t += m == 2 and is_run(y);
48    for (int d = 1; d <= t; ++d) {
49      if (y == 1582 and m == 10 and d >= 5 and d < 15)
50        continue;                        // 1582-10-05 至 10-14 不存在
51      if (++c == x + 1) {
52        cout << d << ' ' << m << ' ' << abs(y) << (y < 0 ? " BC\n" : "\n");
53        return;
54      }
55    }
56  }
57}
58
59int main() {
60  int n;
61  cin >> n;
62  for (int i = 0; i < n; ++i) {
63    long long x;
64    cin >> x;
65    solve(x);
66  }
67}

两种做法

两份实现在 万组随机 （含 、、、 等边界）上逐项比对，结果一致。

实现要点

• 边界自查： 应得 4 10 1582， 应得 15 10 1582。
• 天文纪年与输出格式的换算：内部 是公元前 年，输出时写 abs(y) 并补 BC； 时闰年判据是 -y % 4 == 1。
• 年份用 int、天数用 long long：年份答案可到 ，天数可到 。
• 二分里的公元 年处理容易被忽略： 要当成 ，收缩边界时也要避开 ，否则二分可能停在不存在的那一年上。

题目

地图上有 个点， 号是小熊的家，其余都是景点。点对之间有双向直达线路；若 与 之间可以经过 条线路通达，就说它们之间可转车 次通达（有直达线路即可转车 次通达）。

小熊要从家出发游玩 个不同的景点再回家，行程固定为

每段行程最多转车 次。转车时经过的点没有限制，可以重复经过。每个景点有分数，求访问的四个不同景点的分数之和的最大值。

限制

• 景点分数

可达性预处理

从每个点出发做一次 BFS，把距离存进二维数组：

一步的代价是 ，在 、 时约为 ，可以接受。数组大小是 的 int，约 25 MB。

暴力枚举的代价

有了 之后，最直接的做法是枚举四个景点：

代价是 ： 时约 ，能过前 8 个测试点； 时是 ，不可能。

测试点表的规模提示了目标复杂度：最后 6 个测试点 ，必须是 级别。

枚举中间两点

固定中间的两个景点 、 之后， 与 的选择互相独立：

• 要满足 且 ；
• 要满足 且 。

证明：设最优解里的 不在 中。 里的 个点分数都不低于 ，其中至多有 个与 、 重合（ 只需避开这两个点），所以至少还有一个可用的候选 ，把 换成 不降低总分。对 同理。

枚举顺序