一、先从题意抽象

题目给了：

• 个宿舍点， 个机厅候选点
• 每个机厅的覆盖半径都是
• 你最多只能选 个机厅，要让所有宿舍都被至少一个选中的机厅覆盖
• 还要求：机厅数量最少，若有多个最优解，再要字典序最小

这里真正难的地方不是坐标，而是：

从 个候选机厅里选尽量少的点，覆盖所有宿舍。

这本质上就是一个“集合覆盖”问题。

二、为什么这题能做

如果直接暴力选机厅，复杂度是 。

但题目里最关键的限制是：

可以接受 级别的做法。

而 很大，所以必须把重点放在“机厅集合”上。

这就是这题的核心方向：

枚举机厅集合，宿舍只作为被检查对象。

三、把“覆盖关系”变成二进制

每个宿舍能被哪些机厅覆盖？

对于某个宿舍 ，我们可以检查所有机厅 ：

等价于：

如果成立，就说明机厅 可以覆盖宿舍 。

于是我们可以用一个二进制集合表示这个宿舍的“可覆盖机厅集合”：

• 第 位为 ：表示机厅 能覆盖它
• 第 位为 0：表示不能覆盖它

记这个集合为 mask[i]。

例如 ，若一个宿舍能被机厅 1、3、4 覆盖，则：

四、覆盖所有宿舍的条件怎么判

假设我们最后选择的机厅集合是 。

一个宿舍 能被覆盖，当且仅当：

宿舍的可覆盖集合 mask[i]和 有交集

即：

反过来，宿舍不能被覆盖，等价于：

它所有可覆盖的机厅都没被选中

也就是：

于是问题变成：

对于一个选定集合 ，是否存在某个宿舍的覆盖集合是 的子集？

如果存在，就说明这个宿舍被漏掉了；如果不存在，说明所有宿舍都被覆盖。

五、关键转化：把“是否存在某个子集”预处理出来

这一步是整题最关键的优化。

1. 先记录每种覆盖集合有没有出现过

设：

• v[mask] = 1 表示：存在某个宿舍，它的可覆盖机厅集合恰好是 mask

因为宿舍很多，但 mask 的总数只有 ，所以可以直接记录。

2. 再做一个“子集存在性”预处理

我们希望快速知道：

有没有某个宿舍，其覆盖集合是 mask 的子集

这可以用 SOS DP 做。不会的移步高维前缀和总结(sosdp) - heyuhhh - 博客园

定义：

• h[mask] = 1 表示：存在某个宿舍，它的覆盖集合是 mask 的子集

那么如果我们知道 h[full ^ S]，就能判断当前选的 是否可行。

为什么？

• full ^ S 是“没选的机厅集合”
• 如果存在某个宿舍的覆盖集合是它的子集，说明这个宿舍所有可覆盖机厅都没被选
• 那这个宿舍就无法被覆盖

因此：

• h[full ^ S] == 1：不合法
• h[full ^ S] == 0：合法

六、为什么 SOS DP 能算这个

初始时：

• h[mask] = v[mask]

然后做标准 SOS 递推：

for (int i = 0; i < n; ++i)
    for (int mask = 0; mask < 2^n; ++mask)
        if (mask & (1 << i))
            h[mask] |= h[mask ^ (1 << i)];

这段的含义是：

若 mask 中去掉某一位后，已有某个子集存在，那么 mask 也应该标记为存在子集。

最终 h[mask] 就表示：

mask 的所有子集中，是否至少有一个是某个宿舍的覆盖集合

也就是我们需要的“子集存在性”。

七、如何枚举答案

现在所有信息都可以在 时间判断一个机厅集合是否可行了。

于是直接枚举所有机厅集合 S：

• popcount(S) 是选了几个机厅
• 如果超过 (k)，跳过
• 如果 h[full ^ S] == 0，说明这个集合能覆盖所有宿舍

然后在所有可行集合里：

1. 先比机厅数量最少
2. 数量相同则比字典序最小

八、字典序怎么比较

输出的是机厅编号序列（从小到大）。

例如：

• {1, 3}
• {2, 3}

显然 {1, 3} 的字典序更小，因为第一个元素 1 < 2。

所以比较两个 mask 时，只要从低位到高位扫描：

第一个不同的位置上，哪个集合先出现 1，哪个就更小。

九、Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 210000;
int m, n, k, R;
int am[N];
struct _ {
    ll x, y;
} a[N], wm[30];
bool check(int x, int y) {
    for (int i = 0; i < n; ++i) {
        bool bx = (x >> i) & 1;
        bool by = (y >> i) & 1;
        if (bx != by) return bx; // x 在第一个不同位上为 1，则字典序更小
    }
    return false;
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> m >> n >> k >> R;
    for (int i = 0; i < m; ++i) cin >> a[i].x >> a[i].y;
    for (int i = 0; i < n; ++i) cin >> wm[i].x >> wm[i].y;
    bool ok = true;
    for (int i = 0; i < m; ++i) {
        int mask = 0;
        for (int j = 0; j < n; ++j) {
            ll dx = a[i].x - wm[j].x;
            ll dy = a[i].y - wm[j].y;
            if (dx * dx + dy * dy <= 1LL * R * R) {
                mask |= (1 << j);
            }
        }
        if (mask == 0) {
            ok = false;
            break;
        }
        am[i] = mask;
    }
    if (!ok) {
        cout << -1 << '\n';
        return 0;
    }
    int tot = 1 << n;
    int full = tot - 1;
    vector<char> h(tot, 0);
    for (int i = 0; i < m; ++i) h[am[i]] = 1;
    // h[mask]：是否存在某个宿舍，其可覆盖集合是 mask 的子集
    for (int i = 0; i < n; ++i) {
        for (int mask = 0; mask < tot; ++mask) {
            if (mask & (1 << i)) {
                h[mask] = h[mask] | h[mask ^ (1 << i)];
            }
        }
    }
    int bc = k + 1, bm = -1;
    for (int mask = 1; mask < tot; ++mask) {
        int cnt = __builtin_popcount(mask);
        if (cnt > k) continue;
        // 如果 h[full ^ mask] == 1，说明存在某宿舍只依赖未选中的机房，当前方案不合法
        if (h[full ^ mask] == 0) {
            if (cnt < bc) {
                bc = cnt;
                bm = mask;
            } else if (cnt == bc && check(mask, bm)) {
                bm = mask;
            }
        }
    }
    if (bm == -1) {
        cout << -1 << '\n';
        return 0;
    }
    cout << bc << '\n';
    for (int i = 0; i < n; ++i) {
        if ((bm >> i) & 1) {
            cout << i + 1 << ' ';
        }
    }
    return 0;
}

ps. 笔者输入时 写反了调了一万年，大家写的时候一定注意输入格式。