2026 四川省赛
命题:南京大学
无 BJ。
| ID | Diff | Description | Solution | Code | |
|---|---|---|---|---|---|
| A | Expert | :当树以 为根时满足 且 是 的祖先的 数量。 次交换 ,求 。 | 是 的祖先 删去点 后, 与 处于不同的连通块中。用数据结构维护 ,做子树修改,查询全局 min。初始情况:枚举 ,考察 将树切分出的各个连通块,设 () 在连通块 中,那么 在除 之外的其他连通块任意位置皆可,使用二维偏序维护。修改:仅影响二元组 ,考察删去路径 后得到的两个连通块,亦可按上述逻辑计算。 | AC | |
| C | Hard | 可以随时花费 的代价获得新英雄 ,给定击杀与存活规则,求消灭敌方英雄的最小总代价。 | DP,转移方法按规则模拟。 | AC | |
| D | Easy | 任意重排所有奇 / 偶数下标的字符,是否可以变成回文串。 | 分类讨论。分别考虑奇数下标和偶数下标的出现次数与对称位置下标的奇偶性。 | AC | |
| E | Medium | 树。求 01 串 的数量,任意选择 的点 并 flip 子树内所有点权,可以变为 。 | 逆向考虑,只能操作 。考虑子树 的子问题。若不操作 ,贡献 。若操作,需 ,而且操作后子树可以达到任意状态,贡献 。。 | AC | |
| F | Expert | 判断是否存在序列 的重排 ,满足对于任意分割点 都有前缀 后缀 。 | 不妨 。形态:前缀有因子 ,后缀有因子 ,中间至多一项没有因子 , 。枚举两个数的素因子作为 ,再枚举两个数的素因子作为 进行验证。。 | AC | 枚举枚举,不要暴力。 |
| G | Easy | 序列 和整数 。定义任意长度为 的序列 的权值为:,计算满足移除区间 后的序列权值为 的数对 数量。 | 主机派。 | AC | |
| H | Easy | 个点有点权 。连边 。求最大权独立集的点权和。 | 依 的奇偶性,图是完全二分图,对左右部点分别计算。 | AC | 好。 |
| I | Expert | 2D 平面的点集,求在任意旋转方向下的平均投影长度。 | 点集的投影 = 凸包的投影,这可以拆为每条边的平均投影之和,于是答案正比于凸包周长。比例系数依据样例判断。 | AC | 好。非常巧妙的转化。 |
| K | Hard | 将基环树的每个点替换为简单环,边的端点随机选取在环上某点。给定新图,还原基环树。 | 模拟。删去所有桥,然后反复合并度为 2 的点,并处理重边和自环,再加上删去的桥,便得到了原图。 | AC | |
| L | Hard | 给定 。每次删除 的首或尾字符并移至 末尾,若首尾相同,可以同时删除并将其中一个移至 末尾。直至 为空,求字典序最小的 。 | 贪心。贪心取较小的一端,若首尾相同,则向内寻找第一个不同的字符,分别讨论内侧字符和首尾字符的大小,仍然贪心。 | AC | 贪心。 |
本部落格所有文章除特別聲明外,均採用CC BY-NC-SA 4.0 授權協議。轉載請註明來源 小明の雜貨屋!
評論