题目分析

我们需要构造一个二分图的完美匹配：

• 左部 $L$：所有大小为 $K$ 的 $[n]$ 子集
• 右部 $R$：所有大小为 $K-1$ 的 $[n]$ 子集
• 边关系：$T \subset S$ 时存在边 $(S,T)$
• 条件：$2K > n$

根据 Hall 定理，这样的完美匹配一定存在，但需要给出具体的构造方法。

关键观察

1. 集合的二进制表示：每个子集用一个 $n$ 位二进制数表示，低位对应小元素
2. 包含关系：$T \subset S$ 当且仅当 $T$ 可以通过从 $S$ 中删除一个元素得到
3. 平衡条件：由于 $2K > n$，每个 $K-1$ 子集的补集大小 $n-K+1 < K$

算法思路

核心思想：括号匹配法

将集合的二进制表示看作一个括号序列：

• 1 表示左括号（集合包含该元素）
• 0 表示右括号（集合不包含该元素）

具体步骤

对于输入的大小为 $K$ 的集合 $S$：

1. 扫描二进制位（从低位到高位，即元素 0 到 n-1）

   • 遇到 1（集合包含该元素）：计数器 sum 加 1
   • 遇到 0（集合不包含该元素）：计数器 sum 减 1

2. 记录最大前缀和位置

   • 跟踪 sum 的最大值 mx 及其位置 loc

3. 删除最大前缀和位置的元素

   • 返回 $S$ 删除第 loc 个元素后的集合

代码实现

#include "hall.h"
using namespace std;

int solve(int n, int K, int s) {
    int mx = -2, loc = 0, sum = 0;
    
    for (int i = 0; i < n; i++) {
        if (s & (1 << i))
            sum++;      // 遇到1，计数器加1
        else
            sum--;      // 遇到0，计数器减1
        
        // 记录最大前缀和的位置
        if (sum > mx) {
            mx = sum;
            loc = i;
        }
    }
    
    // 删除最大前缀和位置的元素
    return s ^ (1 << loc);
}

算法正确性证明

为什么这样构造是完美匹配？

1. 单射性：不同的 $K$-子集删除不同位置的元素得到不同的 $(K-1)$-子集
2. 满射性：每个 $(K-1)$-子集 $T$ 都能找到唯一的 $K$-子集 $S$ 使得 $T = S \setminus \{\text{loc}\}$
3. 包含关系：显然 $T \subset S$

括号匹配的直观理解

• 最大前缀和位置对应一个"关键元素"
• 删除该元素能保持匹配的平衡性
• 在 $2K > n$ 的条件下，这种构造保证了一一对应

复杂度分析

• 时间复杂度：$O(n)$ 每次查询
• 空间复杂度：$O(1)$
• 总复杂度：$O(qn)$，其中 $q$ 是查询次数

算法优势

1. 简单高效：线性扫描即可完成
2. 无需预处理：每次查询独立处理
3. 保证正确性：基于组合数学的经典构造
4. 适合交互：响应快速，内存占用小

该算法巧妙地利用了括号序列的性质，将复杂的组合匹配问题转化为简单的前缀和扫描，实现了优雅而高效的解决方案。