ResurrectionTX

笔记

比赛(7) 题解(32)

/ 注册

全部文章 / 笔记（共6篇）

动态规划

树形\(dp\) P6419 [COCI2014-2015#1] Kamp 换根\(dp\)，先以\(1\)为根，记\(f_x\)表示\(x\)的子树中的关键点到\(x\)的距离之和，\(dis_{x, 1}\)和\(dis_{x, 0}\)表示\(x\)的子树中关键点到\(x\)的最远和次远距...

树形DP 状压DP

2020-07-06

0 431

Weight Balanced Leafy Tree

\(1.1\) \(Leafy \ Tree\) 定义 \(Leafy \ Tree\) 是一种二叉树，其每个节点要么为叶子，要么有两个儿子。其信息完全储存在叶子上面，每个非叶节点存储的信息是其儿子的信息的合并。例如线段树就是一种\(Leafy \ Tree\)，每个节点上存的信...

数据结构平衡树 WBLT

2020-06-12

0 527

随笔

算[l, r]区间里所有子区间最小值的和。对每个位置i向左知道第一个小于它的位置，向右找到第一个小于它的位置，算算贡献。考虑可以用单调栈算。但是如果一个区间里同一个最小值出现多次就挂了，所以考虑魔改一下，对于右边找到第一个小于它的点，对于左边找到第一个小于等于它的点并记录位置，这样的话就...

2020-06-12

0 384

斐波那契数

\(1.1.1\)斐波那契循环节 \[gcd(fib_n, fib_m) = fib_{gcd(n, m)} \] 考虑设\(n < m\)，\(fib_n = a\)，\(fib_{n + 1} = b\)，那么对应的有\(fib_{n + 2} = a + b\)，\(fib_...

数论

2020-06-12

0 329

组合数学

懒得复制的一些东西 1.1 可重复组合 \(n\)个数中选择\(r\)个数，每个数可以重复选择多次。方案数为\(\binom{n + r - 1}{r}\)。考虑若没有选择多次的条件，就是在\(n\)个数中选择一个子数列，满足\(a_i < a_{i + 1}\)，现在有了可以重复...

组合数学数论

2020-06-12

0 454

网络流

最大流 \(Dinic\) 直接上代码CwQwC。 #include <iostream> #include <cstdio> #include <cstring> #include <queue> using namespace std; c...

网络流

2020-06-12

0 492