13k 字 18 分钟

# P4717 【模板】快速莫比乌斯/沃尔什变换 (FMT/FWT) 先放一个模板后面写题直接复制就可以了。 FWTFWTFWT 原理就不解释了，大家自己去看题解吧 QwQ 这里直接放代码。 CodeCodeCode 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192#include...
4.6k 字 6 分钟

数论，树状数组 + 按右端点排序再扫一遍，树上背包

2.3k 字 3 分钟

# Description Luogu传送门 # Solution 题目让我们求 kkk 个串 LCP\text{LCP}LCP 之和最大，所以考虑建 trie\text{trie}trie 树，然后我们就可以跑树形 dp\text{dp}dp。 设 dpu,idp_{u, i}dpu,i​ 表示在以 uuu 为根的子树中，选取 iii 个结束节点，两两 LCP\text{LCP}LCP 之和最大是多少。 转移的时候为了避免重复转移，我们只加上 xxx 点到其父亲的贡献，即： dpx,i=max⁡{dpx,i−j+dpy,j+(n2)}dp_{x, i} = \max\{dp_{x, i -...
2.7k 字 4 分钟

# Description Luogu传送门 # Solution 首先我们计算出整棵树的 dfs\text{dfs}dfs 序，然后一个点的祖先的 dfs\text{dfs}dfs 序一定小于当前点的 dfs\text{dfs}dfs 序。 我们把输入的关键点按照 dfs\text{dfs}dfs 序从小到大排序，对于一个关键点 pip_ipi​，所有不能和它放到同一组的点一定在它前面。 考虑依次加入每个关键点，假设 g(x)g(x)g(x) 为 xxx 到根路径上的关键点个数，f(i,j)f(i, j)f(i,j) 表示把前 iii 个关键点分成 jjj...
2.6k 字 3 分钟

# Description Luogu传送门 # Solution 明显是要使用费用流，考虑如何建图。 把每一天拆成晚上和早上两个点，每天晚上会获得脏餐巾，早上会获得干净的餐巾。 从源点向每天晚上连流量为 xxx，费用为 0 的边，表示晚上会获得当天所需的 xxx 条脏餐巾。 从每天早上向汇点连流量为 xxx，费用为 0 的边，表示每天早上提供 xxx 条干净的餐巾给汇点，如果满流则合法。 从每天晚上向第二天的早上连流量为 inf\text{inf}inf，费用为 0 的边，表示把当天的脏餐巾留给第二天。 快洗：第 iii 天晚上向第 i+t1i + t_1i+t1​ 天早上连流量为...
3.9k 字 5 分钟

# Description Luogu传送门 # Solution 首先考虑朴素的 dp\text{dp}dp，设 dpi,jdp_{i, j}dpi,j​ 表示前 iii 的数的排列，有 jjj 个前缀最大值。 从小到大依次填数来转移，转移方程： dpi,j=dpi−1,j−1+(i−1)×dpi−1,jdp_{i, j} = dp_{i - 1, j - 1} + (i - 1) \times dp_{i - 1, j} dpi,j​=dpi−1,j−1​+(i−1)×dpi−1,j​ 把 iii 放到最后一位即加上 dpi−1,j−1dp_{i - 1, j -...
2.2k 字 3 分钟

# Description 观察题意，一个点被走过之后权值变为 0，但是还可以继续走，所以我们可以把一个点拆成入点和出点，然后从入点向出点连两条边。 # Solution 网络流 题意即为选取一个点之后，当前点上下左右均不能选择，求选取的点的最大权值和。 所以我们把矩阵黑白染色，每个黑点向周围的 4 个白点连边，流量为正无穷。 然后建超级源点，超级汇点。源点向黑点连边，流量为黑点的权值；白点向汇点连边，流量为白点的权值。 然后我们对于这张图跑一个最小割，图中剩下的边权和就是能选取的最大和。 所以答案就是 sumsumsum 减去最小割。最小割 = 最大流 相信大家都知道。 #...
1.8k 字 2 分钟

# Description Luogu传送门 # Solution 观察到 nnn 极小，坐标的范围也不是特别大，我们考虑直接暴力求解！ 不难发现，一个三角形覆盖的格子中分为两种情况： 全部覆盖。 覆盖了左下角，右上角没有被覆盖。 因此我们可以把一个格子拆成左下角和右上角两个小三角形来计算，然后总格子数会是一个整数，最后答案再除以 2 即可。 再来看这个小三角形如何统计。 我们考虑枚举每一列，然后开一个数组记录当前列被覆盖的情况。 不难发现由于三角形的摆放方式的特点，第 x+1x + 1x+1 列与第 xxx...
2.1k 字 3 分钟

# Description Luogu传送门 # Solution 最大费用最大流 虽然叫方格取数加强版，但是感觉跟方格取数没半毛钱关系（ 我们还是要从当前点向下，向右连边。 观察题意，一个点被走过之后权值变为 0，但是还可以继续走，所以我们可以把一个点拆成入点和出点，然后从入点向出点连两条边。 建一条流量为 1，费用为 www 的边。 再建一条流量为 k−1k - 1k−1，费用为 0 的边。 表示第一次走可以获得 www 的收益，但只能走一次，后面再走到当前点时没有收益。 从当前点向下方和右方连一条流量为 kkk，费用为 0...