本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-26 02:07:22

赛时只过了 A,B,C,D1，D2 一个细节写挂了没过，非常遗憾。

A

容易发现 $s_1 = s_n$ ，那么一定无解，反之可以构造 $k=2$ 有解。

B

通过一些（感觉？）得出答案与数组顺序无关。

数组排序后第 $\lfloor \frac{n}{2}\rfloor + 1$ 个元素一定不会可以被保留。

可以略加模拟加以验证，感性理解差不多可以。

严格数学证明不会。

C

贪心方向：尽可能让所有相邻数不同。

一个可行解：

int cnt[26];
void solve(int id_of_test){
	scanf("%d",&n);
    scanf("%s",s+1);
    FOR(i,1,n){
        cnt[s[i]-'a']++;
    }
    vi rem;
    FOR(i,0,25){
        if(cnt[i])rem.eb(i);
    }
    while(!rem.empty()){
        for(int& id:rem){
            cnt[id]--;
            pc(id+'a');
        }
        vi nw;
        for(int id:rem){
            if(cnt[id]){
                nw.eb(id);
            }
        }
        rem=nw;
    }
    pln;
}

D1

注意到同一个序列操作最大能得到的值是次小未出现的非负数。

对于初始值 $x$，注意到在同一个序列操作两次，就能得到本序列操作最大值。

也就是说，对于任意 $x$，操作能得到的最大值其实是所有序列能操作得到的最大值，当然也可以不操作。

D2

注意到，设同一个序列的最小未出现的非负数为 $mex$，次小未出现的非负数为 $semex$。

那么，假设对当前序列操作的初始值为 $x$，若 $x = mex$，那么操作完成后，$x$ 变为 $semex$，否则，$x$ 变为 $mex$。

也就是说，$x$ 作为初始值可以变换为 $semex$ 。

考虑以此关系建边。

从 $semex$ 连一条单向边到 $mex$，代表 $semex$ 可以从 $mex$ 操作得到。

对每个序列这样建图，注意到这个图是一个 DAG，用拓扑排序就可以求解每个数能操作跳转到的最大的值，设 $x$ 能最多操作到 $f_x$（目前只考虑从 $semex$ 输出 $mex$）。

另外注意到，对于同一个序列的任意 $x \neq mex$，输入 $x$ 都会输出 $mex$。这意味着如果有两个序列的 $mex$ 是相同的，那么可以先操作得到其中一个的 $semex$，然后继续跳转到 $f_{semex}$。

另外一个坑点：每个数 $x$，其操作后的最小值有所有序列的最大 $mex$ 保底，但是不判断这个也能过样例，赛时死在了这里。