xixike

# 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 -...

# 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...

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

# 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 -...

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

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

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

# Description Luogu 传送门 # Solution 首先看到 n≤20n \leq 20n≤20，可以想到状压，然后题目要求我们求从全部为 1 的状态到全部为 0 状态的最短时间，不难想到使用最短路或者 dp\text{dp}dp 来解决。 对于这道题，我们使用最短路。 把每一种状态当作一个节点，每次处理一个节点时枚举所有的补丁，判断该补丁能否使用，如果可以，直接计算出使用该补丁之后的状态，即为当前点能到达的下一个点。 那么这时还有两个问题： 如何判断当前点能否使用。 把每个补丁必须有的 bug\text{bug}bug 存到 b1b_1b1​ 里，必须没有的...

# Descirption Luogu 传送门 # Solution 题目要求我们求出符合某种条件的方案数，不难想到使用容斥或者二项式反演。 考虑二项式反演的套路，设至少 blablabla 的方案数 g(i,j,k)g(i, j, k)g(i,j,k)，恰好 blablabla 的方案数 f(i,j,k)f(i, j, k)f(i,j,k)，然后通过一定方法来计算。 回到这道题目上，我们设： 至少有 iii 行 jjj 列没有染色，且有 kkk 种颜色没有使用的方案数为 g(i,j,k)g(i, j, k)g(i,j,k)。 恰好有 iii 行 jjj 列没有染色，且有 kkk...

# 二项式系数 # 定义 符号：(nk)\dbinom{n}{k}(kn​)，读作：“nnn 选 kkk”。 组合意义：从有 nnn 个元素的集合中选出 kkk 个元素作为子集的方案数。 我们称 nnn 是 上指标，称 kkk 是下指标。 (nk)={n(n−1)⋯(n−k+1)k(k−1)⋯1=nk‾k!,k≥0;0,k<0.\dbinom{n}{k}=\left\{ \begin{aligned} & \frac {n(n - 1)\cdots(n - k + 1)}{k(k - 1)\cdots1} = \frac...