题解：P15321 【MX-X24-T2】「RiOI-7」Oops, It's Yesterday Twice More

· · 题解

闲话

看到 \operatorname{mex} 脑子一晕，这已经是两场比赛第三次看见它了。然后赛时不知道怎么想的和这道题死磕了将近三个小时，难绷。

做法

用 mx 表示原序列的 \operatorname{mex}。

注意到只能删数不能加数，所以显然 \operatorname{mex} 不会增大。对于大于 mx 的 i 输出 -1 即可。

考虑 \le mx 的 i，设原序列中有 cnt_i 个 i。一定要删完序列中所有的数 i 且 \forall 0 \le j < i 数 j 不能被删光才有解。可以分以下步骤删除：

  1. 当 cnt_i >= 3 时用一次操作删掉两个 i。重复操作直到不满足条件。
  2. 若 cnt_i = 2，找到一个不等于 i 且可以被删除的数，删除这个数和一个 i。
  3. 若 cnt_i = 1，找到两个大于/小于 i 且可以被删除的数，删掉其中一个和 i。
  4. 最后剩下一些可以删除的数，尽量删除之。

注意一下如果 i 之前有重复出现的数的话可以判断一下能否用一个不能删除的数作为 a_j，可能可以多进行一次操作。

做完了。

代码

为什么我的代码那么长。

#include <bits/stdc++.h>
using namespace std;
#define pre(i,n) for(int i = n;~i;--i)
#define rep(i,n) for(int i = 1;i <= n;i++)
#define rpt(i,a,n) for(int i = a;i <= n;++i)
#define ll long long
#define swap(x,y) (x ^= y ^= x ^= y)
#define debug cerr<<"Help!\n"
constexpr int N = 1e6 + 5;
int a[N],cnt[N],sum[N],T,n,mx;
inline void work(int i){
    #define no return cout<<"-1 ",void();
    if(i > mx) no;
    int cl = i >= 1 ? sum[i-1] - i : 0,cr = sum[n] - sum[i];
    if(i == mx){
        cout<<(cl + cr - 1 + (bool)(i ? sum[i-1] ^ i : 0)) / 2<<' ';
        return;
    }
    //from here
    int res = cnt[i];
    if(cnt[i] >= 3){
        res = (cnt[i] - 1) / 2,cnt[i] -= res * 2,res += cnt[i];
    }
    // to here
    if(cl + cr < cnt[i] - 1) no;
    int lft = cl + cr - (cnt[i] - 1);
    // if(lft + i < 2 || (lft < 2 && !cl) || max(cl + i,cr) < 2) no;
    bool f = i ? sum[i-1] ^ i : 0;
    if(lft + f < 2 || (lft < 2 && !cl) || max(cl + f,cr) < 2) no;
    // int res = cnt[i];
    --lft;//还有 lft 个可以删除的数.
    cout<<res + (lft - 1 + (bool)(i ? sum[i-1] ^ i : 0)) / 2<<' ';
}
inline void solve(){
    rpt(i,0,n + 1) cnt[i] = sum[i] = 0;
    cin>>n;
    rep(i,n) cin>>a[i],++cnt[a[i]];
    sum[0] = cnt[0];
    rep(i,n + 1) sum[i] = sum[i-1] + cnt[i];
    rpt(i,0,n + 1) if(!cnt[i]){
        mx = i;
        break;
    }
    rpt(i,0,n) work(i);
    cout<<'\n';
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--) solve();
    cerr<<'\n'<<1.0 * clock() / CLOCKS_PER_SEC;
    return 0;
}