命题:南京大学

无 BJ。

IDDiffDescriptionSolutionCode
AExpertf(r)f(r):当树以 rr 为根时满足 i<ji<j 且 AjA_j 是 AiA_i 的祖先的 (i,j)(i, j) 数量。QQ 次交换 Ai,Ai+1A_i, A_{i+1},求 min⁡rf(r)\min_{r} f(r)。AjA_j 是 AiA_i 的祖先   ⟺  \iff 删去点 AjA_j 后,rr 与 AiA_i 处于不同的连通块中。用数据结构维护 f(r)f(r),做子树修改,查询全局 min。初始情况:枚举 jj,考察 AjA_j 将树切分出的各个连通块,设 AiA_i (i<ji < j) 在连通块 bb 中,那么 rr 在除 bb 之外的其他连通块任意位置皆可,使用二维偏序维护。修改:仅影响二元组 (i,i+1)(i,i+1),考察删去路径 (i,i+1)(i,i+1) 后得到的两个连通块,亦可按上述逻辑计算。AC
CHard可以随时花费 11 的代价获得新英雄 xx,给定击杀与存活规则,求消灭敌方英雄的最小总代价。DP,转移方法按规则模拟。AC
DEasy任意重排所有奇 / 偶数下标的字符,是否可以变成回文串。分类讨论。分别考虑奇数下标和偶数下标的出现次数与对称位置下标的奇偶性。AC
EMedium树。求 01 串 cc 的数量,任意选择 cu=0c_u = 0 的点 uu 并 flip 子树内所有点权,可以变为 CC。逆向考虑,只能操作 Cu=1C_u = 1。考虑子树 uu 的子问题。若不操作 uu,贡献 ∏vfv\prod_{v} f_v。若操作,需 Cu=1C_u = 1,而且操作后子树可以达到任意状态,贡献 2su−12^{s_u - 1}。O(N)\mathcal{O}(N)。AC
FExpert判断是否存在序列 AA 的重排 A′A',满足对于任意分割点 ii 都有前缀 gcd⁡≠\gcd \ne 后缀 gcd⁡\gcd。不妨 gcd⁡A=1\gcd A =1。形态:前缀有因子 pp,后缀有因子 qq,中间至多一项没有因子 pp, qq。枚举两个数的素因子作为 pp,再枚举两个数的素因子作为 qq 进行验证。O(A+Nω(A)2)\mathcal{O}(\sqrt{A}+N \omega(A)^{2})。AC枚举枚举,不要暴力。
GEasy序列 AA 和整数 KK。定义任意长度为 mm 的序列 bb 的权值为:∑i=1m(−1)i+1bi\sum_{i=1}^m (-1)^{i+1} b_i,计算满足移除区间 [l,r][l, r] 后的序列权值为 KK 的数对 (l,r)(l,r) 数量。主机派。AC
HEasyNN 个点有点权 WiW_{i}。连边 i,ji,j   ⟺  \iff 2∤popcount⁡(Wi⊕Wj)2 \nmid \operatorname{popcount}(W_{i} \oplus W_j)。求最大权独立集的点权和。依 popcount⁡Wi\operatorname{popcount}W_{i} 的奇偶性,图是完全二分图,对左右部点分别计算。AC好。
IExpert2D 平面的点集,求在任意旋转方向下的平均投影长度。点集的投影 = 凸包的投影,这可以拆为每条边的平均投影之和,于是答案正比于凸包周长。比例系数依据样例判断。AC好。非常巧妙的转化。
KHard将基环树的每个点替换为简单环,边的端点随机选取在环上某点。给定新图,还原基环树。模拟。删去所有桥,然后反复合并度为 2 的点,并处理重边和自环,再加上删去的桥,便得到了原图。AC
LHard给定 SS。每次删除 SS 的首或尾字符并移至 TT 末尾,若首尾相同,可以同时删除并将其中一个移至 TT 末尾。直至 SS 为空,求字典序最小的 TT。贪心。贪心取较小的一端,若首尾相同,则向内寻找第一个不同的字符,分别讨论内侧字符和首尾字符的大小,仍然贪心。AC贪心。