题解：P17853 [LBA-OI R6 A] Su通ki信yu题ri

· · 题解

题意

给定 Bob 最终拿到的集合 T，找出所有可能的 x，即存在某个满足题目条件的初始集合 S，使得按策略加入的数恰好为 x。

思路

先固定一个候选 x = t_j（T 中第 j 小的数）。此时初始集合 S 就是 T 去掉 x 后剩下的集合，大小为 k = m - 1。设 S 的补集为 C，即 1 \sim n 中不在 S 里的数，升序记为 c_1 < c_2 < \dots。

按策略配对时，S 的第 i 小数匹配的总是当前最小的未匹配补集元素，也就是 c_i。k 对全部配完后，第一个没被匹配的补集元素是 c_{k + 1}，即 C 的第 m 小。

所以 x = t_j 合法，当且仅当 C 的第 m 小恰好是 t_j。由于 C 中除了 t_j 之外全是不在 T 里的数，这等价于 C 中比 t_j 小的数恰好有 m - 1 个。而在 1 \sim t_j - 1 中，属于 T 的恰好有 j - 1 个，所以 C 中比 t_j 小的数共有 (t_j - 1) - (j - 1) = t_j - j 个，于是

t_j - j = m - 1

整理得 t_j = j + m - 1。因此答案就是所有满足这个等式的 t_j，按升序输出即可。数据范围保证 m < \left\lfloor\frac n2\right\rfloor，此时 t_j \le 2m - 1 < n，不需要额外检查范围。这一判断在读入时即可完成，不需要预处理或额外数据结构，单组复杂度 O(m)。

代码

#include<bits/stdc++.h>
#define int long long
#define inf 1e9
using namespace std;
int n, m, cnt, ans[1000005];
void solve() {
    cin >> n >> m, cnt = 0;
    for (int i = 1; i <= m; i++) {
        int t; cin >> t;
        if (t == i + m - 1) ans[++cnt] = t;
    }
    cout << cnt << "\n";
    for (int i = 1; i <= cnt; i++) {
        cout << ans[i] << " ";
    }
    cout << "\n";
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

:::info[AI 使用说明] 本文使用 AI 工具润色。 :::