SunJude的文章

csp 前训练

2 条评论 OI 无标签 SunJude
10.18T2 P14066容易发现分成的三段按 $a_i$ 排序之后一定是连续的三段，否则可以通过交换两个人所在的集合使得限制更严格。钦定最大的 $a_i$ 在第三组。按照 $a_i$ 从小到大的三段分别为 $123$ 还是 $213$ 分类。枚举第一段的长度，然后可以计算出第二段最少是多少，最后检查第三段长度是否符合要求。T3 AT_joisc2015_f首先把每个人进门出门看成一个事件...

曼哈顿距离和切比雪夫距离

0 条评论 OI 无标签 SunJude
曼哈顿距离$$ d = |x_1 - x_2| + |y_1 - y_2| $$切比雪夫距离$$ d = \max(|x_1 - x_2|, |y_1 - y_2|) $$曼哈顿距离转切比雪夫距离$$ \begin{aligned} d &= |x_1 - x_2| + |y_1 - y_2| \\ &= \max\{x_1 - x_2 + y_1 - y_2, \space...

水群看到的

0 条评论 OI 无标签 SunJude
gza：给定两个序列 $a$ 和 $b$，现在要你求$$ \sum_{S \subset \{1, \cdots, n\}}\max(\min_{i \in S}a_i,\min_{i \in S}b_i) $$首先第一步有一个很精彩的转化：$\max(x, y) = x + y - \min(x, y)$于是里面的东西可以拆掉第一层 $\max$ 变成$$ \min_{i \in S} ...

DFS 序 O(1) LCA

0 条评论 OI 无标签 SunJude
以下设 $dfn_u < dfn_v$。结论$u = v$ 时：$u$ 为 LCA。$u \neq v$ 时：LCA 为 dfs 序上 $[dfn_u + 1, dfn_v]$ 区间内深度最小的点的父亲。ST 表维护，预处理 $O(n\log n)$，查询 $O(1)$。证明$u = v$ 时显然。$u \neq v$ 时：记 LCA 到 $v$ 路径上的儿子为 $x$。$u$ 不为 ...

题解：CF2147B Multiple Construction

0 条评论 OI 无标签 SunJude
赛时这个题和 E 卡了我八百年，怄火怄火怄火。来个不需要脑电波构造的方法。如何用奇怪的方式撞到通解。Solution首先从剩余系的角度入手：把每个下标 $\bmod x$，划分成 $x$ 个同余类，这样想给 $x$ 选两个位置只需要在某个同余类里找两个空位即可。有一个显然错误的暴力思路是按 $x$ 从小到大暴力放。具体地，对于每个 $x$，用并查集维护空位 $p$，每次找到一个空位就暴力跳，...