- 1.06
  - CF1975G
  - P8518
- 1.07
  - CF1503D
  - P11519
- 1.09
  - P6822
  - P3587
- 1.10
  - CF1753F

2025.1 做题记录

发布于 2025-01-10 | 标签: 做题记录 | 2分钟 | 470字数

1.06

CF1975G

如果两边都存在任意符，或都不存在任意符直接比较即可。判掉两端的固定字符。a 没有任意符，b 有任意符。任意符将 b 分为若干长为 $m$ 的段，在长为 $n$ 的 a 中做带通配符的字符串匹配，贪心取最前的一个匹配的位置。 $m$ 可能很小但很多，所以一次取 a 的前 $2\times m$ 进行匹配，如果失败删去前 $m$ 个。复杂度 $O(m\log m)$ 。

P8518

对盒子扫描线，线段树维护时间，形如后缀加减。只需要关心最后一次顶上下界，即线段树二分最后一次 $\max-\min\ge a_i$ 。然后分讨计算。

1.07

CF1503D

一定有 $\min (a_i,b_i)\le n$ ， $\max(a_i,b_i)>n$ 。按 $\max(a_i,b_i)$ 降序排序取出两个 $\min(a_i,b_i)$ 升序的子序列。线段树维护。

P11519

并查集启发式分裂。

1.09

P6822

建超级源汇点，拆成有向边，化边为点。每条边向反向边连其权值。把每个点的出边权值排序，相邻的小的向大的连权值的差值。跑最短路。

P3587

异或哈希，改同颜色最后一个点的权值使得同颜色异或为 $0$ 。

1.10

CF1753F

枚举对角线确定正方形，同条对角线有决策单调性。每条对角线只用加入 $(min(n,m))^2$ 个点，每个点只会被枚举 $\min(n,m)$ 次。每条对角线只用查询 $\min(n,m)$ 次。只需要插入 $O(1)$ 查询 $O(\sqrt k)$ 的分块求 mex 即可。

0%

召唤看板娘