2021年8月学习记录

2021.8.6

[APIO2016]划艇

题目 博客
当 $dp$ 中涉及较大的值域时，可以考虑离散化后进行 $dp$ ，在 $dp$​ 时要注意很多细节。如要分别考虑之前状态和当前状态在同一区间和不同区间的情况。

CF1045H Self-exploration

题目 代码

把 $01$ 和 $10$ 看作隔板，在隔板之间放 $0$ 或 $1$ 。

[POI2008]KUP-Plot purchase

题目 代码

对于一个和大于 $2k$ 的矩阵，一定不能被分成两个和小于 $k$ 的矩阵.

所以对于一个和大于 $2k$ 的矩阵，如果矩阵中不存在大于 $2k$ 的数，那么它可以通过去掉一些行和去掉一些列来得到一个和在 $[k,2k]$ 的矩阵

可以用悬线法找到不存在大于 $2k$ 的数的和最大的矩阵，然后通过不断去掉一行或一列来得到所求的矩阵

CF1032F Vasya and Maximum Matching

题目 代码

一棵树最大匹配唯一当且仅当除孤点外它的最大匹配是完美匹配

证明可以考虑反证。若其不唯一，我们先把两种匹配方案中不同的其中一个匹配 $(x,y)$ 断掉。接下来考虑给 $x$ 找新的匹配点；由于最大匹配是完美匹配，因此这样一定会导致另一个匹配 $(x', y')$ 断掉。不妨设 $x'$ 与 $x$ 间有边，那么接下来我们就要给 $y'$ 再找一个结点匹配…如此重复，为了最终构成一个匹配，这条路径一定会绕一圈回到 $y$；于是就形成了环。但树中是不允许存在环的 —$from Piwry$

然后设 $f[i][0]$ 表示 $i$ 和儿子断掉了， $f[i][1]$ 表示有儿子和 $i$ 连通但是没有匹配， $f[i][2]$ 表示有儿子和 $i$ 连通且已经匹配。然后 $dp$ 一下就行.

总结

1. 当 $dp$ 中涉及较大的值域时，可以考虑离散化后进行 $dp$.
2. 要提高寻找性质的能力

2021.8.7

CF932E Team Work

题目 代码

大力推式子题，因为二项式系数和下降幂更搭，所以过程如下

$\begin{aligned} &\quad\sum_{i=1}^{n}\tbinom{n}{i}i^k\\ &=\sum_{i=1}^{n}\tbinom{n}{i}\sum_{j=0}^{k}S(k,j) i^{k\downarrow}\\ &=\sum_{j=0}^{k}S(k,j)\sum_{i=1}^{n}\tbinom{n}{i}i^{k\downarrow}\\ &=\sum_{j=0}^{k}S(k,j)\sum_{i=1}^{n}\tbinom{n-k}{i-k}n^{k\downarrow}\\ &=\sum_{j=0}^{k}S(k,j)n^{k\downarrow}\sum_{i=1}^{n}\tbinom{n-k}{i-k}\\ &=\sum_{j=0}^{k}S(k,j)n^{k\downarrow}\sum_{i-k=0}^{n-k}\tbinom{n-k}{i-k}\\ &=\sum_{j=0}^{k}S(k,j)n^{k\downarrow}2^{n-k}\\ \end{aligned}$

然后就可以 $O(k^2)$ 解了。

[ARC087D] Squirrel Migration

题目 代码

考虑答案的上界，对于一条边 $(u,v)$，设它子树大小为 $siz_u$ 和 $siz_v$, 那么它的贡献最大为 $2\min(siz_u, siz_v)$ . 也就是这条边两端子树大小的最小值。找到树的重心，对于以重心为根的每个子树，它里面的点对应的 $p_x$ 一定在这个子树外，所以考虑容斥，设 $f[j]$ 表示钦定 $j$ 个点的 $p_x$ 在同一子树内的方案数。
$ans = \sum_{i=0}^{n}(-1)^if[i](n-i)!$

2021.8.9

CF1156E Special Segments of Permutation

题目 代码 博客

1. 遇到和区间的 $max$ 有关的求数量算贡献的题，要考虑笛卡尔树，单调栈。
2. 借助笛卡尔树可以在树上用启发式来优化复杂度

2021.8.10

[GXOI/GZOI2019]旅行者

题目 代码

1. 对于集合 $A$ 和 $B$ ， 求 $A$ 中的点到 $B$ 中的点的最短路的最小值. 可以建一个点 $s$ ，向所有 $A$ 中的点连边，权值为 $0$ ，建一个点 $t$ ，从所有 $B$ 中的点连边, 权值为 $0$ 。从 $s$ 向 $t$ 跑最短路即可.
2. 按照二进制的某一位是否为 $1$ ， 把所有数分成两组，那么显然对于任意一个数，其它数都和它至少一次不在同一个集合中

最小割树

link

2021.8.11

[模板]Min_25筛

题目 代码

2021.8.12

[CTS2019]珍珠

题目 代码 题解

1. 减法卷积可以通过翻转多项式来转化成加法卷积
2. $e^x$ 全是 $1$ ， $e^{-x}$ 奇数位是 $-1$ ， 偶数位是 $1$ 。 $\frac{e^x - e^{-x}}{2}$ , 奇数位是 $1$ , 偶数位是 $0$ 。

[SDOI2015]约数个数和

题目 代码

$d(ij) = \sum_{a|i}\sum_{b|j}[gcd(a, b) = 1]$

51nod1584加权约数和

题目 代码

$\sigma(ij) = \sum_{a|i}\sum_{b|j}[gcd(a, b) = 1]a\frac{j}{b}$

2021.8.14

2021-08-14新高二一期暑假集训11