CF1530D 这道题我印象很深题目标题叫 Secret Santa看起来像一道圣诞主题的模拟题实际上一句话概括有 n 个人第 i 个人心里偷偷藏了一个最想送礼物的对象 a[i]现在需要你安排一个送礼方案 b[i]让每个人都恰好送出一份礼物、也恰好收到一份礼物同时让尽量多的人送到心里想送的那个人。说白了就是一个带有“排序/排列约束”的贪心构造题。我当时第一次遇到它是在 CF 上刷 1600~1700 分段摸到这道题时被“自送礼”这个隐形坑折腾得不轻。网上题解大多是几行代码加一句“最后特判一下”但没有把为什么这么判讲清楚。这篇文章就把题意、贪心原理、实现细节、自送修正逻辑和常见调试坑一次性说透适合刚接触排列构造、函数图、贪心证明的选手。1. 题目在讲什么一个隐晦的置换构造问题先老老实实复盘题面。输入多组测试数据每组一个 n然后给一个长度为 n 的数组 aa[i] 表示 i 最想送礼物的对象序号题目保证 a[i] ! i也就是没有人想送给自己。你要输出一个数组 b满足b 是 1 到 n 的一个排列等价于每个数字恰好作为收礼人出现一次最大化满足 b[i] a[i] 的下标数量输出这个最大数量和对应的构造。n 的上限是 2×10^5所有测试数据的 n 之和也是这个量级所以正解必须接近 O(n)。别想着费用流、二分图最大匹配这类重型算法范围不允许。如果没有“b 是排列”这个限制做法非常简单直接让 b[i] a[i]全员满意。问题麻烦就麻烦在“一个人只能收到一份礼物”和“每个人都要收到一份礼物”这两个约束叠在一起。当多个人同时想送给同一个人时只能有一个人如愿其他人得临时改目标反过来如果某个人从头到尾没被任何人想送那他就成了“空槽”必须有个人补上去。从图论视角看这是典型的函数图问题把每个 i 当成一个点从 i 向 a[i] 连一条有向边。每个人出度为 1入度不一定。最终构造出的 b 要求每个点入度也为 1也就是把初始的函数图通过改边的方式变成若干个环同时保留尽可能多的原始边。实际做题时不需要真的去写基环树 Tarjan 之类的东西抓住“入度”这个核心词就够。我记忆里这道题有一个很经典的朴素理解方式第一遍先顺着 a 数组安排能占坑就占坑第二遍处理那些“没送出去的人”和“没人送的人”。两个集合大小一定相等因为第一遍已经分配了 k 个礼物目标剩下的目标有 n-k 个而没送出去的人也正好 n-k 个。后面所有代码基本都围绕这个平衡展开。2. 核心思路先贪心占坑再补洞2.1 第一轮想送的人还没被抢就让他先如愿第一轮直接遍历 i如果 a[i] 这个目标还没有被安排收礼人就让 i 满足并把这个目标标记为“已经有人送了”。这样得到一批 ans[i] a[i] 的人满足人数记为 k。那些没能如愿的人都是因为自己的愿望目标在第一轮就被前面的人抢占了。很多人会担心第一轮遍历顺序影响最终答案。例如 1 号和 2 号都想送给 3 号不管先处理谁目标 3 只能贡献一个满足名额所以顺序不影响最大满足人数。贪心在这一轮已经拿满了所有“能产生满足”的名额剩下的只能靠第二轮补。这一轮代码上有个细节遇到 a[i] 已经被占用时直接跳过不要当场把他丢进未处理集合而是先留着等第一轮结束后统一收集。原因是后续可能需要维护多个数组边遍历边插入容易下标错乱统一收集逻辑更清晰。2.2 第二轮把没送出去的人和没人收礼的人配对第一轮结束后统计两个列表needans[i] 仍然为 0 的人也就是还没决定送谁的人have还没有收到礼物的人也就是第一轮中没有任何人的 a[i] 指向他。两个列表长度相同这一点很关键。通常做法是把它们按下标一一配对第 k 个 need 送给第 k 个 have。举个例子第一轮结束后 need [3, 5]have [4, 5]那就让 3 送 4让 5 送 5。这里立刻暴露一个问题第 2 个 need 和第 2 个 have 都是 5配对结果就成了 5 送 5这违反了“自己不能送给自己”的约束。题目虽然保证了 a[i] ! i但经过第二轮的分配完全可能构造出 b[i] i这个坑最容易在第一次提交时踩中。为了避免这个坑常见做法是错位配对need[0] 送给 have[1]need[1] 送给 have[2]以此类推最后一个 need 送给 have[0]。这种循环移位能大幅降低自送概率但并不能保证 100% 消除所以还需要第三轮做最终修正。2.3 自送礼陷阱最后一轮修正逻辑处理 b[i] i 的标准思路分两种情况。第一种未处理的人不止一个。此时可以找一个同样未满足的人交换这两个人的送礼目标。因为两个人原本都不满足交换之后依然不满足但两人都能摆脱自送状态满足人数 k 不变。这个操作在置换构造里非常常用互相换一下目标整个排列依然合法。第二种未处理的人只剩一个而且他对应的空槽也只剩他自己。比如 need [x]have [x]此时 x 只能送 x必须打破一个已经满足的人。做法是找一个 y且 y ! x满足 ans[y] a[y]然后令ans[x] a[y]ans[y] x为什么可以这么改这里有一个隐藏条件x 是没人送的人所以任何人的 a[i] 都不可能等于 x。这意味着 a[y] 不是 x修改后 x 不会自送同时 y 改成送 xx ! yy 也不会自送。代价是 y 不再满足最初愿望k 减 1。很多题解写“随便找一个已经满足的人交换”核心就是这层逻辑。我第一次看到这里时卡了很久后来才意识到关键在“x 是无人问津的目标”这一点上它是整个修正方案成立的前提。3. 完整实现与代码解析3.1 一份可直接 AC 的 C 代码直接放代码后面逐段解释。#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), ans(n 1, 0); vectorint hasOwner(n 1, 0); int k 0; for (int i 1; i n; i) { cin a[i]; if (hasOwner[a[i]] 0) { hasOwner[a[i]] i; ans[i] a[i]; k; } } vectorint need, have; for (int i 1; i n; i) { if (ans[i] 0) need.push_back(i); if (hasOwner[i] 0) have.push_back(i); } int m (int)need.size(); // 循环移位配对尽量避免自送 for (int i 0; i m; i) { int give have[(i 1) % m]; ans[need[i]] give; } // 处理仍可能存在的自送 for (int i 1; i n; i) { if (ans[i] i) { if (m 1) { for (int j 1; j n; j) { if (j ! i ans[j] ! a[j]) { swap(ans[i], ans[j]); break; } } } else { for (int j 1; j n; j) { if (j ! i ans[j] a[j]) { ans[i] a[j]; ans[j] i; k--; break; } } } } } cout k \n; for (int i 1; i n; i) { cout ans[i] (i n ? \n : ); } } return 0; }3.2 关键变量说明hasOwner[x]当前被安排送给 x 的人编号0 表示还没人送 x。ans[i]最终 i 的送礼目标初始为 0 表示还没确定。k满足 b[i] a[i] 的人数。need没确定送礼目标的人。have没有收到礼物的人。第一轮结束后hasOwner 里所有非 0 的位置代表这些人已经有礼物入账所有 0 的位置代表没人送。need 和 have 长度相等的原理前面说过不再重复。3.3 为什么这样写更不容易出错很多新手喜欢用 set 来模拟“占坑”和“找空位”但在多组数据下 set 的常数偏大而且迭代器操作容易出错。这里直接用数组标记第一轮做占坑第二轮用循环移位配对逻辑非常线性。循环移位配对是代码里最重要的技巧。为什么移位而不是同下标因为 need 和 have 都是从同一批人里筛出来的很可能出现 need[i] have[i] 的情况也就是某个人被迫送给自己。循环移位之后相当于人为制造了一个错排直接避开大部分自送情况。第三轮的处理我写成 for 循环而不是找到一个自送就 break是为了应对多个位置同时自送的边界情况。这里的 m 1 分支交换两个未满足的人不减少 km 1 分支则是真正让一个已满足的人让路需要 k--。这段逻辑比网上一些只写一半的题解要稳。4. 正确性分析为什么这组贪心可行4.1 第一轮已经拿走所有“必然满足”名额从匹配角度看每个人只有一条偏好边 i - a[i]目标是选出一个覆盖所有人的置换匹配。每个目标节点最多只能成为一个已满足者的收礼对象所以一个目标即使被几千人喜欢最终也只能提供一份“满足”。第一轮贪心相当于每个目标第一次被盯上时就锁定下来已经拿到了这个目标能贡献的最大值。有人会问如果先让 1 号满足结果 2 号的愿望没法满足反过来先让 2 号满足1 号也没法满足两种方案满足数一样。这就是为什么第一轮的遍历顺序无关紧要。因为每个目标只能贡献一次冲突时无论保留哪个人总满足数的上限都不会变。4.2 第二轮配对一定能补齐排列第二轮的核心事实是need 和 have 数量相等。第一次分配结束后所有人里没确定送礼目标的数量是 n-k没确定收礼人的数量也是 n-k。把 need 映射到 have每个 need 恰好送出一个礼物每个 have 恰好收到一个礼物这就把剩余槽位补齐了。循环移位只是映射方式之一它保证排列性质只是可能在某些特殊位置产生自送。第三轮再处理自送本质是把映射调整成一个“没有自环的排列”。由于第二轮所有操作都是在未满足者和空余目标之间进行不会碰已满足的人所以第一轮攒下的 k 个满足名额不会在第二轮丢失。4.3 最坏情况为什么只是减 1一个很重要的结论最终满足人数要么是 n要么是 n-1。因为第一轮贪心已经拿到了所有可能满足的名额第二轮如果不产生自送k 就是 n如果产生自送也只需要破坏一个已满足的人便能修复所以最多减 1。为什么不会被迫破坏更多人因为自送只会发生在 need 和 have 重叠的人身上而 need 中的人本来就不满足我们只需要让这些人不送给自己即可。m 1 时可以靠互相交换来解决m 1 时才需要牺牲一个原本满足的人。这样 k 的下限是 n-1。题目最终答案的输出也确实是 n 或 n-1 这两个值之一。5. 实战调试与常见错误5.1 自送没特判样例过了照样 WA这道题最有迷惑性的一点是样例经常构造得比较温柔第一轮直接全员满足根本走不到自送分支。于是很多人把贪心写完就交了结果 test 3 就挂。我调试时的建议是自己多构造几个“多人抢同一目标”和“出现空槽”的用例。例如1 5 2 3 2 1 1第一轮 1 - 22 - 34 - 1 满足3 和 5 没满足没人送的人有 4 和 5。如果不处理自送很容易构造出 5 - 5。手动跑一遍这个例子比反复想题解更直观。5.2 多组数据的清空时机CF 这类多测题最容易翻车的是 vector 没重置。我习惯每轮 while 内重新声明 vector而不是在外层定义后一遍遍 clear。原因是重新声明代码更短且不担心上一组数据残留影响长度判断。hasOwner、ans 这类数组必须跟着每组数据重新赋值。如果图省事用全局数组记得在每组数据开始前 fill 置零。5.3 输出格式和换行不要小看输出要求第一行是最大满足人数第二行是构造的 b 数组。有人最后检查时只盯着算法结果输出的时候把 ans 的索引写错或者换行符多打了一个导致 PE也很可惜。我这里用cout ans[i] (i n ? \n : )是为了避免行尾多一个空格直接满足常规判题要求。也可以先全部输出空格最后单独换行CF 对这题不会卡行尾空格但规范一点总是好的。5.4 用 set 实现的注意点网上也能看到 set 版本的代码先把所有 iset 放进去第一轮如果能抢到 a[i] 就从 set 里删掉第二轮从 set 里依次取元素分配。这种写法更贴近“占坑”的直觉但注意遍历 set 时不能用下标只能靠迭代器。而且如果第一轮“抢”的顺序不佳第二轮的 need / have 集合可能出现偏差需要同样的自送特判。我个人更推荐数组双 vector 写法因为它把“没送的人”和“没人送的人”两个集合展示得非常直观调试时打印起来也方便。6. 从这道题看一类置换构造题6.1 通用套路函数图 入度出度 补洞CF 里很多与排列、礼物、配对相关的题底层都是同一个套路先按原始偏好尽量占坑然后统计入度为 0 和出度缺失的点再把两者配对最后处理自环。这题本质上就是给每个点分配一个出边使得每个点入度也恰好为 1同时最大化保留原始边。遇到这类题我一般会写在草稿纸上的三步是第一轮所有目标先到先得能满意就满意第二轮统计剩余 need 和 have数量必然相等配对第三轮检查是否有 b[i] i有就针对性地换。这套模板在 Codeforces 上适用面很广建议背下来。6.2 如果去掉 a[i] ! i 限制会怎样原题特意保证了 a[i] ! i这让第一轮不会出现“某人想送自己且成功”的情况也保证了第三轮修正时可以找到合法的让路人选。如果题目改成允许 a[i] i那么自送不仅会在第二轮出现第一轮就可能出现情况会复杂很多。第三轮修正的关键在于“x 是没人想送的人”所以任何 a[j] 都不等于 x。如果 a[j] 可以等于 x那么 ans[x] a[j] 后 x 可能又变成自送整个修正必须额外判断。平时刷题遇到变体时要先检查题目有没有类似的约束。6.3 类似的题可以往哪扩展与这题思路接近的还有带权匹配版本比如每个人有多个偏好列表要求最大化满足权值之和。那种题就不能靠简单贪心得用 KM 或者费用流。但如果你只是做 CF 1600 分段函数图补洞这套已经覆盖了很多题。还可以思考如果每个人必须收到且只能收到一份礼物但允许某些人不满意如何最小化不满意人数。答案其实就是 n 减最大满足数这题已经给出了构造。再进一步如果希望不满意的人尽可能集中在某类人身上就需要在第三轮选人时加入优先级逻辑这时候又变成贪心排序的问题了。我个人刷题到现在碰到这种“先贪心、再补洞、最后处理自环”的题已经养成了条件反射。第一轮永远无脑占便宜第二遍永远考虑入度缺失最后一定检查自送。这套思路不仅对付 CF1530D对付很多排列构造题都特别顺手。最后分享一个小技巧这题调代码时可以在本地写一个随机数据生成器n 从 1 到 8 随机生成 a保证 a[i] ! i然后跑完输出后自己写一个 check校验 b 是否为排列、是否有 b[i] i、满足数是否正确。我当初就是靠这套 check 把自送边界彻底搞明白的比盯着题解看十遍都管用。