Codeforces 的 1530 场 RoundD 题叫 Secret Santa。题目读完第一反应这不就是个座位安排问题吗结果写起来处处是坑。简单说n 个人玩互送礼物第 i 个人希望收到来自 a[i] 的礼物你需要构造一个 p[1..n]p[i] 表示第 i 个人把礼物送给谁要求每个人恰好送出一份、恰好收到一份并且让尽可能多的愿望成真。这个题在 Div2 里属于“代码不到五十行思路想明白就很简单想不明白就 WA 到怀疑人生”的典型特别适合拿来练贪心匹配和环的处理。下面我把整个思路、完整代码和踩坑过程过一遍给同样被这题折磨过的朋友做个参考。1. 先把题意翻译成数学问题1.1 Secret Santa 的规则到底在说什么原题给了两个数组a 和 p。a[i] 表示第 i 个人“希望收到来自谁”的礼物这是输入固定不变。p[i] 表示第 i 个人“实际把礼物送给谁”这是我们要输出的东西。合法方案必须满足两个条件p 是一个排列即每个人恰好送出一份礼物也恰好收到一份礼物。每个人不能自己送自己也就是 p[i] ! i。如果 p[i] a[i]说明第 i 个人的愿望实现了这个人就是“满意”的。题目要求最大化满意人数并输出任意一个合法方案。有的朋友可能觉得这不就是一个二分图匹配吗左边 n 个人右边 n 个人每个人有一条偏好边指向 a[i]。没错确实可以这么建模但直接跑匈牙利就浪费了——因为每个人的偏好边只有一条这个图极其特殊用贪心就能解决。1.2 排列、置换与“一进一出”把 p 看成一个置换函数每个点有一条出边送给谁和一条入边谁送给我。合法方案等价于把 n 个点划分成若干个有向环每个环上的点依次送礼。关键约束是“一进一出”。也就是说a[i] 作为接收者只能被一个人选中。如果两个人同时想要来自 a[i] 的礼物那必然有一个人要失望因为 a[i] 只能收一份礼物。这个观察直接给出了本题最重要的上界答案不可能超过 a 数组中不同值的个数。因为同一个目标 a[i] 最多只能满足一个人。这个上界看着简单却是后面所有贪心正确性的根基。2. 第一轮贪心能配就先配上2.1 先到先得的匹配策略第一轮我们做这样一件事按 i 从 1 到 n 扫一遍如果 a[i] 还没有被别人“预定”为接收者就立刻让 i 满意即令 p[i] a[i]然后把 a[i] 标记为已被占用。for (int i 1; i n; i) { if (a[i] ! i !used[a[i]]) { used[a[i]] 1; p[i] a[i]; } }这里用 used 数组记录“这个接收者已经有人送礼了”。之所以要加a[i] ! i的判断是为了防止极端数据里出现自己送给自己的情况。原题数据一般保证了 a[i] 不等于 i但写上这个判断也不碍事至少能挡一手非法自环。这个策略其实就是“先到先得”。有人会问扫描顺序会不会影响最终结果比如 i1 抢了位置导致后面某个更“合理”的配对失败答案是不会影响最大匹配数。原因很简单每个人只有一条偏好边 a[i]如果 a[i] 被占用了这个人无论如何都无法第一轮满意如果 a[i] 没被占用他就能第一轮满意。扫描顺序改变的只是“谁占到了这个位置”而不是“这个位置能不能被占到”。2.2 为什么第一轮贪心就是最优前面说了答案上界是“a 中不同值的个数”。第一轮贪心结束之后所有不同的 a[i] 值应该都已经被某个想要它的人占用了。也就是说第一轮满意的人数恰好等于不同值的个数达到了上界所以它已经是最优解。那剩下的问题就是第一轮没被安排的人怎么办这些人都是因为自己的目标已经被别人占了被迫成为“不满意候选者”。他们还得送礼物而接收者池子里恰好也剩下同样数量的人没收礼物。这个数量相等是必然的第一轮安排了多少对匹配就消耗了多少个送礼者和多少个接收者两边余量自然相等。第一轮结束后的状态我用两个集合描述senderp[i] 0也就是还没送出礼物的人。receiverused[i] 0也就是还没收到礼物的人。这两个集合大小相等这是后面所有做法的前提。3. 自由节点配对最大的坑在这里3.1 顺序配对会碰出 self-loop既然 sender 和 receiver 数量相等最简单的做法就是把两个集合按下标顺序一一配对for (int i 0; i k; i) { p[sender[i]] receiver[i]; }问题来了有些位置可能出现 sender[i] receiver[i]也就是一个人既没送礼物也没收礼物结果顺序配对时让自己送给自己。这在 Secret Santa 里是非法的。随便举个例子a [2, 2, 2]第一轮只有 1 号能满意因为 a[1] 2 是唯一的空位p[1] 2used[2] 1。没送礼的人是 2、3没收礼的人是 1、3。sender 集合是 [2, 3]receiver 集合是 [1, 3]。顺序配对2 送给 13 送给 3——3 号自己送自己炸了。这种 self-loop 是这道题最阴间的地方。它不只在自由节点比较多的时候出现最麻烦的是只有一个人落在自由集合里的情况。3.2 相邻交换法处理 self-loop处理 self-loop 的标准操作是发现 sender[i] receiver[i] 时让 receiver[i] 和相邻位置的 receiver 交换。for (int i 0; i k; i) { if (sender[i] receiver[i]) { int j (i 1 k) ? i 1 : i - 1; swap(receiver[i], receiver[j]); p[sender[i]] receiver[i]; p[sender[j]] receiver[j]; } }为什么交换一个邻居就够因为 sender 集合和 receiver 集合内部都没有重复元素。交换后位置 i 拿到的是原来的 receiver[j]。由于 receiver 没有重复receiver[j] 不可能等于 sender[i]所以位置 i 的 self-loop 被消除。位置 j 拿到的是原来的 receiver[i]这个值等于 sender[i]而 sender[j] 和 sender[i] 是不同的人所以位置 j 也不会出现自己送自己。而且这个交换不会破坏前面已经修好的位置操作只动了 i 和 j 两个位置其他位置的 receiver 没变之前检查过的位置依然合法。一次扫描就能把所有 self-loop 全部消掉。3.3 最阴间的 corner casek 1 且是同一个人有一种特殊情况上面的交换法会直接越界k 1也就是自由集合里只有一个人而且他既没送礼也没收礼。比如 a [2, 1, 2]第一轮1 号想要 2满足p[1] 22 号想要 1满足p[2] 13 号想要 22 已经被 1 号占了跳过。没送礼的人只有 3没收礼的人也只有 3。sender [3]receiver [3]。3 号既没送出也没收到还得让他送礼物怎么办如果直接让 3 送给 3非法。这时候需要“破环”。破环的思路是这样让 3 送给他想要的 2也就是 p[3] 2这样 3 号反而满意了。可是 2 已经收到 1 号的礼物了如果 3 再送一份2 就收两份了。所以要把原本送给 2 的人改走找到当前 p[i] 2 的那个人这里是 1 号让 1 号改送给 3。于是变成 p[1] 3p[3] 2。检查一下1 号现在送给 33 号收到礼物3 号送给 22 号收到礼物2 号本来就是送给 1 的。每个人都一进一出合法。关键点是满意人数没有减少。3 号从不满意变成满意1 号从满意变成不满意一进一出总数不变。这里很容易误以为答案要减 1我当初就在这里翻过车。通用写法是if (k 1 sender[0] receiver[0]) { int x sender[0]; int target a[x]; for (int i 1; i n; i) { if (p[i] target) { p[x] target; p[i] x; break; } } }这个循环一定能找到 i因为 target 在第一轮已经被占用了而 p 数组里当前给 target 送礼的人一定存在。4. 完整代码与实现细节4.1 C17 参考实现下面是 C 版本整体思路就是“第一轮贪心 自由节点配对 self-loop 修复”。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin T; while (T--) { int n; cin n; vectorint a(n 1); for (int i 1; i n; i) cin a[i]; vectorint p(n 1, 0), used(n 1, 0); // 第一轮尽量满足每个人的愿望 for (int i 1; i n; i) { if (a[i] ! i !used[a[i]]) { used[a[i]] 1; p[i] a[i]; } } // 收集自由送礼者和自由收礼者 vectorint sender, receiver; for (int i 1; i n; i) { if (p[i] 0) sender.push_back(i); if (!used[i]) receiver.push_back(i); } int k (int)sender.size(); // 特殊 case只有一个人既没送也没收 if (k 1 sender[0] receiver[0]) { int x sender[0]; int target a[x]; for (int i 1; i n; i) { if (p[i] target) { p[x] target; p[i] x; break; } } } else { // 自由节点顺序配对 for (int i 0; i k; i) { p[sender[i]] receiver[i]; } // 修复 self-loop交换相邻 receiver for (int i 0; i k; i) { if (sender[i] receiver[i]) { int j (i 1 k) ? i 1 : i - 1; swap(receiver[i], receiver[j]); p[sender[i]] receiver[i]; p[sender[j]] receiver[j]; } } } // 最后重新统计满意度最稳妥 int ans 0; for (int i 1; i n; i) { if (p[i] a[i]) ans; } cout ans \n; for (int i 1; i n; i) { cout p[i] \n[i n]; } } return 0; }最后输出 p 时用 \n[i n]是 C 里控制空格和换行的惯用写法i 等于 n 时输出换行否则输出空格不用单独判断。4.2 Python 参考实现Python 版本的逻辑完全一致适合用来快速验证思路。import sys def solve(): input sys.stdin.readline T int(input()) for _ in range(T): n int(input()) a [0] list(map(int, input().split())) p [0] * (n 1) used [False] * (n 1) for i in range(1, n 1): if a[i] ! i and not used[a[i]]: used[a[i]] True p[i] a[i] sender [i for i in range(1, n 1) if p[i] 0] receiver [i for i in range(1, n 1) if not used[i]] k len(sender) if k 1 and sender[0] receiver[0]: x sender[0] target a[x] for i in range(1, n 1): if p[i] target: p[x] target p[i] x break else: for i in range(k): p[sender[i]] receiver[i] for i in range(k): if sender[i] receiver[i]: j i 1 if i 1 k else i - 1 receiver[i], receiver[j] receiver[j], receiver[i] p[sender[i]] receiver[i] p[sender[j]] receiver[j] ans sum(1 for i in range(1, n 1) if p[i] a[i]) print(ans) print( .join(map(str, p[1:]))) if __name__ __main__: solve()Python 这里要注意i 1 k的判断当 k 1 时在 else 分支里不会进入 self-loop 修复因为前面已经被特判分流了所以不会出现 j -1 的越界情况。4.3 复杂度与数据范围每个测试用例只需要线性扫描几遍第一轮匹配 O(n)。收集 sender 和 receiver O(n)。配对和 self-loop 修复 O(n)。总时间复杂度 O(n)空间复杂度 O(n)。CF 上 n 的总和在 2e5 级别这个复杂度非常宽松。有人可能想用 set 或者 vector erase 来做自由节点分配那样最坏会退化到 O(n^2)完全没有必要。数组标记加线性扫描就够了。5. 常见问题与排查技巧5.1 高频 WA 原因速查我在写这题的时候以及在评论区看别人翻车最常见的几个错误大概是这些症状可能原因解决办法输出里有 p[i] i自由节点顺序配对后没修复 self-loop用相邻交换法处理自由节点冲突数组越界 / REk 1 时执行了交换逻辑先把 k 1 且 sender receiver 的情况特判掉答案比期望小 1k 1 破环后误以为满意数减少破环是“一进一出”满意度总数不变输出不是排列同一个 receiver 被分配给两个 sender第一轮 used 标记后后续配对只针对未收礼的人TLE用 set 或 erase 动态维护自由节点改用数组标记线性扫描最容易踩的是第三类错误。很多人写到这里觉得“把一个满意的人改成不满意答案肯定要减一”于是在输出前对 ans 做了减一操作反而把对的写成错的。建议不要在中途维护 ans全部构造完之后重新扫一遍统计 p[i] a[i] 的个数。这样即使中间有调整也不会影响最终输出。5.2 手造几个测试用例验证我自己调试的时候用了下面几组数据基本能覆盖所有坑输入 a合法输出 p满意人数说明2 1 23 1 22k 1 自环需要破环2 2 22 3 11自由节点配对出现 self-loop2 3 1 24 3 1 23经典的三人环 一个孤立点2 1 3 42 1 4 32有两个固定点需要额外调整写完代码之后我建议加一个自检函数对拍几组数据比如检查每个 p[i] 是否在 1 到 n 之间、是否互不相同、是否不等于 i// 自检用不建议提交进 CF setint st; for (int i 1; i n; i) { assert(p[i] 1 p[i] n); assert(p[i] ! i); assert(!st.count(p[i])); st.insert(p[i]); }这个自检在调试阶段能帮你快速定位是配对没完成还是 self-loop 没修好。5.3 为什么 first round 的 ans 可以不维护我最初版本是边匹配边加 ans结果自由节点调整的时候脑子就乱了。后来改成“最后统一统计”代码立刻清爽很多。这背后的经验其实通用很多构造题里中间状态会被多次调整不如等到最终方案确定后再算答案。尤其是这种需要“牺牲一个人来满足另一个人”的破环操作中途统计极容易出错。另外平时做题可以多用几个极端数据测一下所有 a[i] 都相同比如全是 1。a 本身是排列但包含固定点。自由节点恰好构成一个奇环。n 2 的最小规模。这些边界情况往往能一针见血地暴露实现里的 bug。6. 从这题能带走什么6.1 套路总结自由节点循环移位这类“构造排列 最大化某些相等位置”的题核心套路其实一致找上界每个目标位置只能被一个人占据。贪心达到上界能配就先配。处理剩余自由节点重点防止自己送自己。遇到孤立自环用破环操作牺牲一个满意的人来补位。如果自由节点不只一个还有一种更直观的写法把所有 self-loop 位置收集起来然后把它们的 receiver 做循环移位。不过相比之下相邻交换法代码更短也不用额外存储位置列表。我个人的建议是这两种方法任选一种掌握考试时不要现场试新写法。我就因为临时换写法在 k 1 的特判上翻过车。6.2 实际场景中的延伸Secret Santa 在真实生活中通常是用随机抽签实现的但抽签不允许抽到自己。本题相当于每个人预先声明“我最想收到谁送的礼物”然后由组织者设计一个送礼置换让尽量多的人满意。这个模型还可以延伸如果每个人可以提供多个偏好题目就从贪心退化成了带权匹配复杂度会上升。如果增加“相邻座位不能互送”之类的限制就得在置换上再加约束。如果要求输出字典序最小的方案贪心的顺序就需要重新设计。但不管怎么变“排列构造 环修复”这个核心思想是不变的。6.3 一点个人经验这题给我最大的教训是corner case 一定要单独拎出来写不要混在通用逻辑里硬扛。k 1 且 sender receiver 的情况放在 else 分支里用交换法去处理必然越界只有单独特判才能把逻辑理清楚。另外写构造题时“最后统计答案”这个习惯帮我避免了很多次虚假的 AC。中间算出来的 cnt 可能会被破环操作影响而最后统一统计永远不会错。建议你也试试这个习惯尤其对于这种输出和答案高度耦合的题目能让得分稳定很多。
Secret Santa 题解：贪心匹配与排列构造的环修复技巧
Codeforces 的 1530 场 RoundD 题叫 Secret Santa。题目读完第一反应这不就是个座位安排问题吗结果写起来处处是坑。简单说n 个人玩互送礼物第 i 个人希望收到来自 a[i] 的礼物你需要构造一个 p[1..n]p[i] 表示第 i 个人把礼物送给谁要求每个人恰好送出一份、恰好收到一份并且让尽可能多的愿望成真。这个题在 Div2 里属于“代码不到五十行思路想明白就很简单想不明白就 WA 到怀疑人生”的典型特别适合拿来练贪心匹配和环的处理。下面我把整个思路、完整代码和踩坑过程过一遍给同样被这题折磨过的朋友做个参考。1. 先把题意翻译成数学问题1.1 Secret Santa 的规则到底在说什么原题给了两个数组a 和 p。a[i] 表示第 i 个人“希望收到来自谁”的礼物这是输入固定不变。p[i] 表示第 i 个人“实际把礼物送给谁”这是我们要输出的东西。合法方案必须满足两个条件p 是一个排列即每个人恰好送出一份礼物也恰好收到一份礼物。每个人不能自己送自己也就是 p[i] ! i。如果 p[i] a[i]说明第 i 个人的愿望实现了这个人就是“满意”的。题目要求最大化满意人数并输出任意一个合法方案。有的朋友可能觉得这不就是一个二分图匹配吗左边 n 个人右边 n 个人每个人有一条偏好边指向 a[i]。没错确实可以这么建模但直接跑匈牙利就浪费了——因为每个人的偏好边只有一条这个图极其特殊用贪心就能解决。1.2 排列、置换与“一进一出”把 p 看成一个置换函数每个点有一条出边送给谁和一条入边谁送给我。合法方案等价于把 n 个点划分成若干个有向环每个环上的点依次送礼。关键约束是“一进一出”。也就是说a[i] 作为接收者只能被一个人选中。如果两个人同时想要来自 a[i] 的礼物那必然有一个人要失望因为 a[i] 只能收一份礼物。这个观察直接给出了本题最重要的上界答案不可能超过 a 数组中不同值的个数。因为同一个目标 a[i] 最多只能满足一个人。这个上界看着简单却是后面所有贪心正确性的根基。2. 第一轮贪心能配就先配上2.1 先到先得的匹配策略第一轮我们做这样一件事按 i 从 1 到 n 扫一遍如果 a[i] 还没有被别人“预定”为接收者就立刻让 i 满意即令 p[i] a[i]然后把 a[i] 标记为已被占用。for (int i 1; i n; i) { if (a[i] ! i !used[a[i]]) { used[a[i]] 1; p[i] a[i]; } }这里用 used 数组记录“这个接收者已经有人送礼了”。之所以要加a[i] ! i的判断是为了防止极端数据里出现自己送给自己的情况。原题数据一般保证了 a[i] 不等于 i但写上这个判断也不碍事至少能挡一手非法自环。这个策略其实就是“先到先得”。有人会问扫描顺序会不会影响最终结果比如 i1 抢了位置导致后面某个更“合理”的配对失败答案是不会影响最大匹配数。原因很简单每个人只有一条偏好边 a[i]如果 a[i] 被占用了这个人无论如何都无法第一轮满意如果 a[i] 没被占用他就能第一轮满意。扫描顺序改变的只是“谁占到了这个位置”而不是“这个位置能不能被占到”。2.2 为什么第一轮贪心就是最优前面说了答案上界是“a 中不同值的个数”。第一轮贪心结束之后所有不同的 a[i] 值应该都已经被某个想要它的人占用了。也就是说第一轮满意的人数恰好等于不同值的个数达到了上界所以它已经是最优解。那剩下的问题就是第一轮没被安排的人怎么办这些人都是因为自己的目标已经被别人占了被迫成为“不满意候选者”。他们还得送礼物而接收者池子里恰好也剩下同样数量的人没收礼物。这个数量相等是必然的第一轮安排了多少对匹配就消耗了多少个送礼者和多少个接收者两边余量自然相等。第一轮结束后的状态我用两个集合描述senderp[i] 0也就是还没送出礼物的人。receiverused[i] 0也就是还没收到礼物的人。这两个集合大小相等这是后面所有做法的前提。3. 自由节点配对最大的坑在这里3.1 顺序配对会碰出 self-loop既然 sender 和 receiver 数量相等最简单的做法就是把两个集合按下标顺序一一配对for (int i 0; i k; i) { p[sender[i]] receiver[i]; }问题来了有些位置可能出现 sender[i] receiver[i]也就是一个人既没送礼物也没收礼物结果顺序配对时让自己送给自己。这在 Secret Santa 里是非法的。随便举个例子a [2, 2, 2]第一轮只有 1 号能满意因为 a[1] 2 是唯一的空位p[1] 2used[2] 1。没送礼的人是 2、3没收礼的人是 1、3。sender 集合是 [2, 3]receiver 集合是 [1, 3]。顺序配对2 送给 13 送给 3——3 号自己送自己炸了。这种 self-loop 是这道题最阴间的地方。它不只在自由节点比较多的时候出现最麻烦的是只有一个人落在自由集合里的情况。3.2 相邻交换法处理 self-loop处理 self-loop 的标准操作是发现 sender[i] receiver[i] 时让 receiver[i] 和相邻位置的 receiver 交换。for (int i 0; i k; i) { if (sender[i] receiver[i]) { int j (i 1 k) ? i 1 : i - 1; swap(receiver[i], receiver[j]); p[sender[i]] receiver[i]; p[sender[j]] receiver[j]; } }为什么交换一个邻居就够因为 sender 集合和 receiver 集合内部都没有重复元素。交换后位置 i 拿到的是原来的 receiver[j]。由于 receiver 没有重复receiver[j] 不可能等于 sender[i]所以位置 i 的 self-loop 被消除。位置 j 拿到的是原来的 receiver[i]这个值等于 sender[i]而 sender[j] 和 sender[i] 是不同的人所以位置 j 也不会出现自己送自己。而且这个交换不会破坏前面已经修好的位置操作只动了 i 和 j 两个位置其他位置的 receiver 没变之前检查过的位置依然合法。一次扫描就能把所有 self-loop 全部消掉。3.3 最阴间的 corner casek 1 且是同一个人有一种特殊情况上面的交换法会直接越界k 1也就是自由集合里只有一个人而且他既没送礼也没收礼。比如 a [2, 1, 2]第一轮1 号想要 2满足p[1] 22 号想要 1满足p[2] 13 号想要 22 已经被 1 号占了跳过。没送礼的人只有 3没收礼的人也只有 3。sender [3]receiver [3]。3 号既没送出也没收到还得让他送礼物怎么办如果直接让 3 送给 3非法。这时候需要“破环”。破环的思路是这样让 3 送给他想要的 2也就是 p[3] 2这样 3 号反而满意了。可是 2 已经收到 1 号的礼物了如果 3 再送一份2 就收两份了。所以要把原本送给 2 的人改走找到当前 p[i] 2 的那个人这里是 1 号让 1 号改送给 3。于是变成 p[1] 3p[3] 2。检查一下1 号现在送给 33 号收到礼物3 号送给 22 号收到礼物2 号本来就是送给 1 的。每个人都一进一出合法。关键点是满意人数没有减少。3 号从不满意变成满意1 号从满意变成不满意一进一出总数不变。这里很容易误以为答案要减 1我当初就在这里翻过车。通用写法是if (k 1 sender[0] receiver[0]) { int x sender[0]; int target a[x]; for (int i 1; i n; i) { if (p[i] target) { p[x] target; p[i] x; break; } } }这个循环一定能找到 i因为 target 在第一轮已经被占用了而 p 数组里当前给 target 送礼的人一定存在。4. 完整代码与实现细节4.1 C17 参考实现下面是 C 版本整体思路就是“第一轮贪心 自由节点配对 self-loop 修复”。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin T; while (T--) { int n; cin n; vectorint a(n 1); for (int i 1; i n; i) cin a[i]; vectorint p(n 1, 0), used(n 1, 0); // 第一轮尽量满足每个人的愿望 for (int i 1; i n; i) { if (a[i] ! i !used[a[i]]) { used[a[i]] 1; p[i] a[i]; } } // 收集自由送礼者和自由收礼者 vectorint sender, receiver; for (int i 1; i n; i) { if (p[i] 0) sender.push_back(i); if (!used[i]) receiver.push_back(i); } int k (int)sender.size(); // 特殊 case只有一个人既没送也没收 if (k 1 sender[0] receiver[0]) { int x sender[0]; int target a[x]; for (int i 1; i n; i) { if (p[i] target) { p[x] target; p[i] x; break; } } } else { // 自由节点顺序配对 for (int i 0; i k; i) { p[sender[i]] receiver[i]; } // 修复 self-loop交换相邻 receiver for (int i 0; i k; i) { if (sender[i] receiver[i]) { int j (i 1 k) ? i 1 : i - 1; swap(receiver[i], receiver[j]); p[sender[i]] receiver[i]; p[sender[j]] receiver[j]; } } } // 最后重新统计满意度最稳妥 int ans 0; for (int i 1; i n; i) { if (p[i] a[i]) ans; } cout ans \n; for (int i 1; i n; i) { cout p[i] \n[i n]; } } return 0; }最后输出 p 时用 \n[i n]是 C 里控制空格和换行的惯用写法i 等于 n 时输出换行否则输出空格不用单独判断。4.2 Python 参考实现Python 版本的逻辑完全一致适合用来快速验证思路。import sys def solve(): input sys.stdin.readline T int(input()) for _ in range(T): n int(input()) a [0] list(map(int, input().split())) p [0] * (n 1) used [False] * (n 1) for i in range(1, n 1): if a[i] ! i and not used[a[i]]: used[a[i]] True p[i] a[i] sender [i for i in range(1, n 1) if p[i] 0] receiver [i for i in range(1, n 1) if not used[i]] k len(sender) if k 1 and sender[0] receiver[0]: x sender[0] target a[x] for i in range(1, n 1): if p[i] target: p[x] target p[i] x break else: for i in range(k): p[sender[i]] receiver[i] for i in range(k): if sender[i] receiver[i]: j i 1 if i 1 k else i - 1 receiver[i], receiver[j] receiver[j], receiver[i] p[sender[i]] receiver[i] p[sender[j]] receiver[j] ans sum(1 for i in range(1, n 1) if p[i] a[i]) print(ans) print( .join(map(str, p[1:]))) if __name__ __main__: solve()Python 这里要注意i 1 k的判断当 k 1 时在 else 分支里不会进入 self-loop 修复因为前面已经被特判分流了所以不会出现 j -1 的越界情况。4.3 复杂度与数据范围每个测试用例只需要线性扫描几遍第一轮匹配 O(n)。收集 sender 和 receiver O(n)。配对和 self-loop 修复 O(n)。总时间复杂度 O(n)空间复杂度 O(n)。CF 上 n 的总和在 2e5 级别这个复杂度非常宽松。有人可能想用 set 或者 vector erase 来做自由节点分配那样最坏会退化到 O(n^2)完全没有必要。数组标记加线性扫描就够了。5. 常见问题与排查技巧5.1 高频 WA 原因速查我在写这题的时候以及在评论区看别人翻车最常见的几个错误大概是这些症状可能原因解决办法输出里有 p[i] i自由节点顺序配对后没修复 self-loop用相邻交换法处理自由节点冲突数组越界 / REk 1 时执行了交换逻辑先把 k 1 且 sender receiver 的情况特判掉答案比期望小 1k 1 破环后误以为满意数减少破环是“一进一出”满意度总数不变输出不是排列同一个 receiver 被分配给两个 sender第一轮 used 标记后后续配对只针对未收礼的人TLE用 set 或 erase 动态维护自由节点改用数组标记线性扫描最容易踩的是第三类错误。很多人写到这里觉得“把一个满意的人改成不满意答案肯定要减一”于是在输出前对 ans 做了减一操作反而把对的写成错的。建议不要在中途维护 ans全部构造完之后重新扫一遍统计 p[i] a[i] 的个数。这样即使中间有调整也不会影响最终输出。5.2 手造几个测试用例验证我自己调试的时候用了下面几组数据基本能覆盖所有坑输入 a合法输出 p满意人数说明2 1 23 1 22k 1 自环需要破环2 2 22 3 11自由节点配对出现 self-loop2 3 1 24 3 1 23经典的三人环 一个孤立点2 1 3 42 1 4 32有两个固定点需要额外调整写完代码之后我建议加一个自检函数对拍几组数据比如检查每个 p[i] 是否在 1 到 n 之间、是否互不相同、是否不等于 i// 自检用不建议提交进 CF setint st; for (int i 1; i n; i) { assert(p[i] 1 p[i] n); assert(p[i] ! i); assert(!st.count(p[i])); st.insert(p[i]); }这个自检在调试阶段能帮你快速定位是配对没完成还是 self-loop 没修好。5.3 为什么 first round 的 ans 可以不维护我最初版本是边匹配边加 ans结果自由节点调整的时候脑子就乱了。后来改成“最后统一统计”代码立刻清爽很多。这背后的经验其实通用很多构造题里中间状态会被多次调整不如等到最终方案确定后再算答案。尤其是这种需要“牺牲一个人来满足另一个人”的破环操作中途统计极容易出错。另外平时做题可以多用几个极端数据测一下所有 a[i] 都相同比如全是 1。a 本身是排列但包含固定点。自由节点恰好构成一个奇环。n 2 的最小规模。这些边界情况往往能一针见血地暴露实现里的 bug。6. 从这题能带走什么6.1 套路总结自由节点循环移位这类“构造排列 最大化某些相等位置”的题核心套路其实一致找上界每个目标位置只能被一个人占据。贪心达到上界能配就先配。处理剩余自由节点重点防止自己送自己。遇到孤立自环用破环操作牺牲一个满意的人来补位。如果自由节点不只一个还有一种更直观的写法把所有 self-loop 位置收集起来然后把它们的 receiver 做循环移位。不过相比之下相邻交换法代码更短也不用额外存储位置列表。我个人的建议是这两种方法任选一种掌握考试时不要现场试新写法。我就因为临时换写法在 k 1 的特判上翻过车。6.2 实际场景中的延伸Secret Santa 在真实生活中通常是用随机抽签实现的但抽签不允许抽到自己。本题相当于每个人预先声明“我最想收到谁送的礼物”然后由组织者设计一个送礼置换让尽量多的人满意。这个模型还可以延伸如果每个人可以提供多个偏好题目就从贪心退化成了带权匹配复杂度会上升。如果增加“相邻座位不能互送”之类的限制就得在置换上再加约束。如果要求输出字典序最小的方案贪心的顺序就需要重新设计。但不管怎么变“排列构造 环修复”这个核心思想是不变的。6.3 一点个人经验这题给我最大的教训是corner case 一定要单独拎出来写不要混在通用逻辑里硬扛。k 1 且 sender receiver 的情况放在 else 分支里用交换法去处理必然越界只有单独特判才能把逻辑理清楚。另外写构造题时“最后统计答案”这个习惯帮我避免了很多次虚假的 AC。中间算出来的 cnt 可能会被破环操作影响而最后统一统计永远不会错。建议你也试试这个习惯尤其对于这种输出和答案高度耦合的题目能让得分稳定很多。
