Spode经学院题解¶
出题人解法：残量网络反向可达性、逐人增广与最近可行排名。 Codex（GPT-6）补全可达性单调性的证明，并将递归搜索整理为显式遍历。标程保留出题人的算法。
1. 固定档次，保留同档调整¶
按排名逐个处理学生。已经处理且被录取的学生，只连接其已确定档次内的导师；连边容量为一。每位导师向汇点连边，容量为招生名额。每名已录取学生向某位导师发送一单位流。
这里不把同档导师固定死。残量网络中，沿着“导师、已录取学生、另一导师”的交替路径，可以把已有学生换到同档的其他导师，从而腾出名额，同时保持此前的档次不变。
2. 哪些导师还能接收一个学生¶
从汇点沿残量边的反方向遍历，标记所有能够在残量网络中到达汇点的节点。导师被标记，当且仅当可以在保持已录取学生档次的情况下，再给它增加一个学生。
充分性：沿导师到汇点的残量路径增广，直接使用空闲名额或通过同档换位取得空闲名额。
必要性：如果存在增加该学生后的可行分配，它与当前分配的差中必有一条从该导师到汇点的残量增广路径；其他差异可分解为环，不影响增加的一单位流。
扫描当前学生的全部导师，选择被标记导师中的最小志愿档次。若没有，则未录取。否则，加入这个档次中被标记的导师连边，再从学生增广一单位流。每档至多三位导师，所以每位学生只增加至多三条边。
未标记导师不必加边：若它以后能成为该学生的合法分配，把后来学生全部删除，就会得到它当前可接收该学生的分配，与未标记矛盾。
3. 最少提升名次¶
设当前学生处在排名 \(r\) .处理排名 \(t\) 的学生之前，把当时所有可接收新学生的导师的最近可行排名更新为 \(t\) ，未标记导师保留过去记录。
随着已确定录取要求增多，一个导师能否再接收一名学生只会从可行变为不可行。因为加入更多学生不能扩大已有学生的可行分配集合。这个论证不依赖当前具体选择了哪份最大流。
对当前学生满意范围内的导师，取最近可行排名的最大值 \(t_{\max}\) .若它不存在，任何提升都不能满意；否则答案为
把当前学生移到位置 \(t\) 后，排在其前面的恰好是原排名的前 \(t-1\) 人。他们的优先录取结果不受后来学生影响，因此之前保存的可行性正好对应这个提升询问。可行性单调说明最大的可行位置就是最少需要提升到的位置。若 \(t_{\max}=r\) ，答案为零。
正确性与复杂度¶
归纳处理排名：残量可达性准确描述保留前面学生档次时的可行导师，选取其中最小档次即满足录取规则；增广保持所有容量与档次限制。由此得到全部正确录取档次。上节的前缀对应关系和单调性给出正确的最少提升量。
记学生数为 \(n\) 、导师数为 \(m\) 、排名询问数为 \(q\) .网络有 \(O(n+m)\) 个点和边；每名学生需要一次反向遍历、至多一次增广和一次 \(m\) 项扫描。总时间为 \(O(qn(n+m))\) ，空间为保存志愿的 \(O(nm)\) 加网络的 \(O(n+m)\) .
每次排名重新初始化网络和历史可达时间。满意档次为零、所有导师名额为零、未填报导师、同档换位与未录取都按同一逻辑处理。
数据与验证¶
tests/generate.py 按固定种子生成数据，可用 --std 指定编译后的参考程序。正式数据包含共同志愿、三人同档、增广链、空名额和充足名额。独立小规模校验枚举全部合法师生分配，直接选取按排名字典序最小的档次向量，并为每个学生重新枚举所有提升位置。性能见评测环境与性能。