trick 集合

· · 个人记录

  1. k 直径

定义 k 直径为树上选取 k 个点使得虚树边权和最大的 k 个点的集合。 若固定集合内一点求 k 直径（需要确定剩余 k-1 个点），则剩下 k-1 个点一定在原本 k 直径的集合中。

  1. lca 问题下树

当树上问题仅和 x,y,lca(x,y) 有关时，如果问题较为复杂，可以考虑把 lca(x,y) 写成欧拉序取 min 的形式，并把 x 和 y 放到欧拉序形成的序列上进行分治。

例如统计 x 向上半径为 r 的毛毛虫内信息，可以列出 de_y - de_{lca} \le r_x，此时因为符号和 de_{lca} 的方向一致，所以可以把 de_{lca} 拆成分治上两个值取 min 的形式，形成三维偏序，cdq 分治即可。

相关题目：link

  1. 维护黑白连续段，连续段的不均摊扩张维护

将黑色连续段表示为括号内的位置，即 1 (2 3 4) 5 6 (7) 为 0111001。此时直接把左括号向左平移，右括号向右平移，能直接使所有黑色段发生扩张。

  1. 矩形三染色 构造 a[i][j] = b[i][j]\bmod 3 且相邻 b 的差恰好为 1

若已知边界的 b，则有如下构造：

b_{x,y}=\max(b_{x,1}-(y-1),b_{x,n}-(n-y),b_{1,y}-(x-1),b_{n,y}-(n-x))

可以证明这个构造满足相邻的差恰好为 1。

相关题目：link

  1. 区间 and，区间除，区间求和：xor master & 诡异操作

详见 link。

相关题目：集训队互测 2024 xor master，uoj unr 诡异操作。

  1. 树的深度可以用括号串的深度来刻画

括号串是一条路径，所以可以用双线容斥的方法做 最大深度不超 d 的点数为 n 的有根树 的计数。

  1. 小模数的格路计数

根据 lucas 定理，可以发现两个 x+y \bmod p 相同的斜线之间的贡献是简单的。

例如 n=p^2 的 n 障碍格路计数，就可以制造 x+y\bmod p=0 的斜线辅助 dp，复杂度为 p^3。

  1. 边三连通分量有关

link

  1. 01 棋盘上的最小独立集

问题的背景是一个 01 矩阵上进行匹配，同一行的 01 可以匹配，同一列的 01 可以匹配。

转化后变成 01 最小独立集，即选取若干位置使得不存在同行或同列的 01。

根据定义，可以钦定一些行选的都是 0，一些列选的都是 0，设这两个集合为 r,c，那么答案是 S_0(r,c)+S_1(R-r,C-c)。其中 S 是数行里交集的 0 或 1 的个数。

把 S_1 展开，得到 S_0(r,c)+S_1(R,C)-S_1(R,c)-S_1(r,C)+S_1(r,c)=S_1(R,C)-S_1(R,c)-S_1(r,C)+|r||c|。

最小独立集的形式发生了本质变化，行列由此独立。