冷滟泽的个人博客

2020-03-30 lengyanze 阅读(50) 评论(0)

shortest 先求出这张 DAG 的拓扑序。考虑删掉一个节点后从 S 到 T 的最短路，它的构成一定是 S + 一些拓扑序递增的节点 + 一条拓扑序跨过被删掉节点的边 + 一些拓扑序递增的节点 + T。那么这条路...

2020-03-24 lengyanze 阅读(42) 评论(0)

题意 给出一棵 n(n\leq 100) 个点的树，要求给每个点染成黑色或白色，使得每个点都存在至少一个黑点与它的距离不大于 k(0\leq k\leq\min(20,n-1))。求染色方案数模 10^9+7。 题解...

2020-03-18 lengyanze 阅读(48) 评论(0)

区间最值操作 & 区间历史最值 本文讲解了吉老师在 2016 年集训队论文（见参考资料）中提到的使用线段树维护区间最值操作和区间历史最值的方法。 前置知识：懒标记线段树。 区间最值操作 首先假设我们有一个序列...

2020-03-16 lengyanze 阅读(39) 评论(0)

前置知识：快速沃尔什变换（FWT） 考虑使用 FWT 的高维扩展，这里的按位取 \min 对应与运算。 将原序列 DWT，求出每个十进制数的超集和。那么现在要对每个位置的超集构成的集合的每个子集，求出它里面元素的和的...

2020-03-16 lengyanze 阅读(54) 评论(0)

高维前缀和 一维前缀和是形如这样的递推式： s_i=s_{i-1}+a_i 它也可以扩展到二维： s_{i,j}=s_{i-1,j}+s_{i,j-1}-s_{i-1,j-1}+a_{i,j} 比较容易发现它是个...