水群看到的

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

以下设 $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

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

云斗国庆集训

Day 1100 + 0 + 100 + 0，唉唉被绿题战胜了。A QOJ2957设 $dp[i][j][k][l][3]$ 表示现在在 $(i,j)$ 位置，走到第 $k$ 个数字串的第 $l$ 位，上一步是从左边/右边/上面过来的最小值。枚举下一步往哪走，判断是否存在数字串满足条件，随便转移一下即可。B P6884我们递归地计算每个子表达式的最大值。假设一个表达式 $A$ 是由子表达式 ...