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

· · 题解

\texttt{Problem}

题目意思很好理解，不讲了。

\texttt{Solution}

假设最后插入的 x 是 A_i，那么其余 m-1 个数会分别匹配不在集合 S 中且最小的 m-1 个数。

也就是说，A_i 是不在集合中的第 m 小的数。

这就很好判断了。

在闭区间 [1,A_i] 中有 A_i 个数。因为数组是升序的，在集合中出现过的就有 i-1 个数，没出现过的就有 A_i-(i-1)=A_i-i+1 个数。

要想它们刚好与其余 m-1 个数匹配，当且仅当 (A_i-i+1)-1=m-1。

也就是 A_i-i=m-1。

统计满足条件的 A_i 就好了。

时间复杂度：O(n)。

\texttt{Code}

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+7;
int t, n, m, a[N];
queue<int> ans;
void solve() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a[i];
        if (a[i] - i + 1 == m) ans.push(a[i]);
    }
    cout << ans.size() << '\n';
    while (ans.size()) cout << ans.front() << ' ', ans.pop();
    cout << '\n';
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//  freopen("cpp.in","r",stdin);
//  freopen("cpp.out","w",stdout);
    for (cin >> t; t; t--) solve();
    return 0;
}

后话

管理员大大大辛苦了。

~写题解不易，点个赞再走吧 QAQ。~

如有勘误，请指出 qwq。