CCPC 2023 Guilin Onsite (部分)解题报告

发布时间 2023-11-07 18:59:16作者: do_while_true

B The Game

从小到大排序之后,应当是 \(A\) 的后 \(m\) 个对应到 \(B\) 的后 \(m\) 个,记录 \(A\) 的后 \(m\) 个的总大小 \(sa\)\(B\) 的后 \(m\) 个的总大小 \(sb\),以及 \(A\)\(B\) 多出来的数的个数 \(res\)\(sb-sa=res\) 那么可以直接对应从小到大将 \(A\) 中的数依次修正为 \(B\),删的一定是前面 \(res\) 个。否则我们需要浪费次数,贪心,需要浪费时去操作 \(A\) 的最小值。

用俩 multiset 实现了一个对顶堆一样的玩意维护前 \(m\) 大。时间复杂度 \(\mathcal{O}(n\log n)\)

Code

C Master of Both IV

枚举 xor \(=x\),考虑它的真因子一定 \(\geq x/2\),无论怎么异或都搞不出 \(x\) 的最高位,所以一定有奇数个 \(x\),从而 \(x\) 的真因子 xor 和为 0。xor 为 0 的个数即为不在线性基里的元素个数,注意去重以及统计 \(x=0\) 的情况。

Code

E Prefix Mahjong

考虑怎么 check,那就是按值域 \(f_{0/1/2,0/1/2,0/1}\) 表示前前位置开头有几个顺子,前一个位置开头有几个顺子,是否已经有雀头。转移是一个矩阵乘法,那么直接在值域上线段树维护矩阵乘法。因为是 01 矩阵所以可以压位,然后值域可以离散化到 1e5,这样复杂度就是 \(\mathcal{O}(n k^2\log n)\),其中 \(k=18\)

Code

G Hard Brackets Problem

首先发现无论怎么操作,光标的右侧永远是一堆 ),只有光标右侧为空的时候才会插入一个 )。所以合法当且仅当串是若干个合法括号序列中间拼上若干 ) 构成的,分析到这里构造就很简单了。

Code

H Sweet Sugar

一个连通块合法当且仅当 \(\sum\geq k\) 且与 \(k\) 同奇偶。和这个题一样证,\(w\) 合法那么 \(w-2\) 一定合法。所以贪心一下就行了。

Code

I Barkley II

计算 cnt-mex 最大的区间。枚举 mex 是 \(x\),计算删去 mex 之后剩余的若干区间 cnt 最大是多少。这里虽然不能保证 mex 是 \(x\),首先答案一定能被统计到,其次算错的话真实 mex \(<x\),只会更劣,所以这么做是对的。

Code