题解
树形动态规划（树形 DP）计数
题意
给定整数序列 $A$ ，要构造一个数列 $B$ ，其中 $B$ 由 $0, 1$ 组成，且 $0$ 的个数等于 $1$ 的个数。
在此前提下，构造一个数列 $B$ 使得 $\sum_{i=2}^n A_i*(B_i \otimes B_{\left\lfloor\frac{i}{2}\right\rfloor})$ 最大。输出这个值的最大可能值。
其中， $\ot …
Jayun 发布于 2023-11-02 17:01:29
00
全局平衡二叉树树形动态规划（树形 DP）
【模板】"动态 DP"&动态树分治
题目描述
给定一棵 $n$ 个点的树，点带点权。
有 $m$ 次操作，每次操作给定 $x,y$ ，表示修改点 $x$ 的权值为 $y$ 。
你需要在每次操作之后求出这棵树的最大权独立集的权值大小。
$1\le n,m\le 10^5$ ， $1 \leq u, v , x \leq n$ ， $-10^2 \leq a_i, y \le …
Jayun 发布于 2023-11-02 08:20:11
00
计数矩阵快速幂容斥原理
题意
一个无向图， $n$ 个点 $m$ 条边。
需要构造长度为 $d$ 的序列，要求必须包含 $[1,k]$ 的点，且相邻项有边连接，相邻不相同，可以重复。求序列数量。
$1\le n \le 20, 1 \le m \le \min(150,n*(n-1)/2),0 \le k \le \min(n,7),1\le d \le 10^9$ 。
题解
考虑 $k=0$ 的情况 …
Jayun 发布于 2023-11-01 13:52:57
00
数学推导杂项
题面
给定 $n$ 个点 $(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)$ ，求出 $\sum_{i=1}^{n}\sum_{j=i+1}^{n}{((x_i-x_j)^2+(y_i-y_j)^2)}$ 。
$2\le n \le 10^5,|x| \le 10^5,|y| \le 10^5$ 。
题解
简单题。对于 $x$ ，式子变成 $\sum_{i=1 …
Jayun 发布于 2023-11-01 13:42:47
11
并查集吉司机线段树（势能分析线段树）
题面
有 $n$ 个容器，从最高层到最底层分别编号为 $1,2,\cdots,n$ 。
现在会在这些容器中倒上一些香槟，当第 $i$ 层容器倒满时，多余的香槟会流到第 $i+1$ 层中，如果第 $n$ 层容器也满了香槟就会流到外面去。第 $i$ 层容器的容量为 $a_i$ ，不保证 $a$ 递增。
你需要实现下面两种操作 $q$ 次：
往某一个编号为 $x$ …
Jayun 发布于 2023-11-01 13:28:08
00
枚举区间动态规划（区间 DP）朴素模拟
题意
给一段程序：
int qsort(int L, int R) {
if (L >= R) return 0;
int i = L, j = R;
int x = Random.Next();
int x0 = A[x];
assert(L <= x && x <= R);
while (i < j) {
while (A[i] < …
Jayun 发布于 2023-11-01 07:20:17
00
博弈树形动态规划（树形 DP）二分答案
题意
给定两个人的树上博弈规则。小 N 初始时在节点 $S$ ，小 Y 需要通过一些操作“强迫”小 N 最后到达节点 $T$ 。小 N 想要让小 Y 的操作尽量多，而小 Y 希望自己的操作尽量少。求解两人都采取最优决策时，小 Y 的操作次数。 每一轮中操作如下：
小 Y 可选的操作有：恢复一条小 N 删除的边 ；或者删除一条边；或者跳过这次操作（不计入答案）。
小 N 接下来执行：如果 …
Jayun 发布于 2023-10-31 21:21:25
00
李超线段树
题目描述
要求在平面直角坐标系下维护两个操作：
在平面上加入一条线段。记第 $i$ 条被插入的线段的标号为 $i$ 。
给定一个数 $k$ ，询问与直线 $x = k$ 相交的线段中，交点纵坐标最大的线段的编号。
强制在线。
题解
李超树板题。在点上维护线段。
代码
const int N = 100005;
const int mod = 39989;
const double …
Jayun 发布于 2023-10-31 15:59:30
00
李超线段树
Escape Through Leaf
题面
有一颗 $n$ 个节点的树（节点从 $1$ 到 $n$ 依次编号），根节点为 $1$ 。每个节点有两个权值，第 $i$ 个节点的权值为 $a_i,b_i$ 。
你可以从一个节点跳到它的子树内任意一个节点上。从节点 $x$ 跳到节点 $y$ 一次的花费为 $a_x\times b_y$ 。跳跃多次走过一条路径的总费用为每次跳 …
Jayun 发布于 2023-10-31 15:51:30
00
区间动态规划（区间 DP）
题面
法阵由从左至右 $n$ 道魔力屏障组成，每道屏障有一个临界值 $a_i$ ，如果它承受攻击的魔力值 $>a_i$ ，屏障将会破碎，它所承受的魔力攻击将在魔力值减半后（向下取整）继续向右移动，否则该攻击会被该屏障完全拦截，停留在屏障前，屏障的临界值不会减少。当两次攻击相遇时，两次攻击会叠加形成新的攻击，新的攻击的魔力值为两次攻击魔力值之和，新的攻击会继续向右移动。小 Z 可以在法 …
Jayun 发布于 2023-10-31 14:12:43
00