Codeforces Round #968 ABCD1D2 简单记录

__vector__ · 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 保底，但是不判断这个也能过样例，赛时死在了这里。