ryp 的博客本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-12 15:18:28
一个点儿子形成的链，在整个树上只能是两种情况，要么是往上连接成一条链，要么是和儿子形成一条链。
考虑怎么实现。首先 DFS，所返回的是儿子剩下的那条链。我们把它放到 multiset 里头，每次加入的时候看里面有没有和它匹配的。如果没有就加入，否则就匹配掉。最后没匹配到的就返回。
注意 multiset.erase 不能直接删数，否则会全部删掉。要用 q.erase (q.find (x))。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-13 08:22:32
设 $g(i)$ 表示选出恰好 $i$ 个元素进行组合的方案数，$f(i)$ 表示选出至少 $i$ 各元素组合的方案数，那么有
$$f(n) = \sum\limits_{i=0}^n {n\choose i}g(i)$$
有些时候 $f(i)$ 好计算，而 $g(i)$ 由于恰好的那个限制，不好计算，我们考虑怎么反推。
事实上，有
$$g(n) = \sum\limits_{i=0}^n {n \choose i}(-1)^{n-i}$$
这个用组合数的性质是好证的。
于是我们就可以将 $f(i)$ 转化为 $g(i)$，例题，也是我接触这玩意儿的第一道题是 P10596 集合计数。
$k$ 个元素已经确定了为交，这里有 $n \choose k$ 种方案，那么还剩下 $n - k$ 个数状态仍待确定。我们要把这 $n - k$ 个数划分为
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-16 13:32:23
轮廓线，做 P1896 和 P1879，把枚举整一列的状态优化到枚举点。
并且发现状态数并不一定是满的，可以用 map 或者 umap 优化掉
cf1209e2
另外有 sosdp，可以利用包含关系优化转移。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-18 15:36:26
题目里头说 $S_i = 1$ 当且仅当 $i \equiv b \pmod m$，我们就知道一个串中如果两个 $1$ 的距离不是 $m$ 就肯定无解。场上没有理解这个充要条件，以为是必要，被捆爆了。
判完段内的无解，我们就把问题转化为了：对于每个 $S_i$ 有一个 $z_i$ 表示其第一个 $1$，这显然是小于 $m$ 的。我们于是建出 $[0, m)$ 的所有点，表示当前长度模掉 $m$ 的值。
对于每一个串，我们需要从 $b - z_i \bmod m$ 转移过来，然后转移到 $b - z_i + \lvert S\rvert\bmod m$。
于是问题就转化为了一条从 $0$ 到 $0$ 的欧拉回路。跑就完了。
题意：给定 $l_i, r_i, v_i$，对方可任取 $w_i\in [l_i, r_i]$，我们可以选一个集合 $S$，这之后 $v_i$ 被选中的概率是
$$\dfrac {w_i}{w_0 + \sum_S w_i}$$
我们要求最大化这个 $v_i$ 的总期望。
我们考虑如果选某个数 $j$ 更优，就说明
$$\dfrac{\sum_S v_iw_i}{\sum_S w_i} \lt \dfrac{\sum_S v_iw_i + v_jw_j}{\sum_S w_i + w_j}$$
整理一下得到
$$\dfrac{\sum_S v_iw_i}{\sum_S w_i} \lt v_j$$
非常美妙的柿子！我们于是得知，如果 $v_i$ 不能选，那么小于 $v_i$ 的所有肯定也不选；反之不一定。
因为值域小，我们可以用线段树二分来完成。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-21 16:15:04
$n\choose m$，从一个大小为 $n$ 的集合中选出 $m$ 个，不考虑选出顺序的方案数。
很明显，集合大小如果增加一，那么这个新元素要么选要么不选，即
$${n\choose m} = {n-1\choose m}+{n-1\choose m - 1}$$
插板法：
$n$ 个人，分成 $k$ 组的方案数量。
用插板法，相当于总共 $n - 1$ 个间隔中选出 $k$ 个，相邻两个间隔是一组，即 $n-1\choose k - 1$。
用 dp，设 $f(i, j)$ 为前 $i$ 个元素，分成 $j$ 组的方案数，有显然转移
$$f(i, j) = \sum\limits_{k=0}^{i-1} f(k, j - 1)$$
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-22 19:49:53
ABD 都是基本题，加起来就打了 150 值得反省。
主要说一下 C 题。
$\mathcal{O}(nm\log V)$ 的做法是比较显然的。我们从最高位枚举就可以了。
注意这个做法的本质，就是我们不断的根据最高位将当前的边集合 $E$ 分为 $E_0$ 和 $E_1$。
如果 $E_0$ 就能让图连通，我们肯定是选 $E_0$ 的，并在这上面继续这个过程；否则，我们当前的边集仍然是 $E$。
我们的答案就是按照这个过程走得到的答案。
我们发现很难独立考虑新边对每一位的贡献。
考虑每一位
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-25 07:30:51
$n$ 个球，$m$ 个盒子，
设 $f(i, j)$ 表示 $i$ 个球，$j$ 个盒子的方案数，有
$$f(i, j) = f(i - j, j) + f(i, j - 1)$$
由于球是不同的，所以我们不能单独考虑每个球的状态。这 $i$ 个球，要么每个都要放，也就是 $f(i - j, j)$，要么是至少一个不放，也就是 $f(i, j - 1)$。
最后答案是 $f(n, m)$。
我们提前取出 $n$ 个球不放，于是方案数就是上一问的 $f(n - m, m)$。
设 $f(i, j)$ 表示 $i$ 个球，$j$ 个盒子的放置
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-26 19:55:03
我们可以用类似点边容斥的东西，也即点的贡献是正的，边的贡献是负的，然后统计区间和，即得到总贡献。
点的贡献是显然的，那么怎么统计边的贡献呢？
边的贡献，来源于开关状态的变化。
考虑在开关管辖大小上根号分治。我们设阈值 $B$，管辖小于 $B$ 的叫做小开关，否则叫做大开关。
开关之间只有三种：对小，对大和大带小。
小开关之间的贡献，可以枚举其管辖范围暴力算；大开关由于只有 $\dfrac N B$ 个，所以可以预处理出每个大开关和哪几个相邻，然后暴力统计就可以了；
小开关和大开关带起来就不一样了。一个大开关对的小开关数量可能很多，因此不能直接做。但是我们可以考虑从小开关那里算贡献。
小开关状态变化的时候，我们枚举了它管辖的所有点；这时候，如果这个管辖的点旁边是个大开关的话，我们就在这个大开关的贡献上加一，表示它状态翻转会增加一条边。
大概就是这样，细节好像不少，写一下。
估计可以到紫了。紫并不恐怖。
更新一下细节。
如果更新的是一个小点，我们就暴力扫它的管辖范围，然后看看构成了多少个新边。同时，如果某个点旁边是一个大开关，我们需要将这个大开关的贡献加上一。
否则如果更新的是大点，我们就先看和它相邻的所有大点，然后看小点维护出来的和它的贡献即可。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-29 14:55:27
我非常喜欢的组合题。
首先我们把贡献式化简：
$$ \begin{aligned} (\sum |A_i - B_i|)^2 &= (\sum (\max - \min))^2 \ &= (\sum(\max + \min) - 2\sum\min)^2 \ &= (2m - 2\sum\min)^2 \end{aligned} $$
这个式子拆出来之后，贡献式就变得只跟 $\min$ 有关了。我们设 $s = \sum\min$，那么一个 $s$ 的贡献就是 $(2m - 2s)^2$
于是我们现在就只需要知道一个 $s$ 对应了多少个 $A$ 与 $B$ 序列。
首先，$\min$ 的选法是可知的，是 $n + s - 1\choose s$，也就是插板。
这个时候我们已经从这两个序列中选完 $n$ 个位置了。考虑剩下 $n$ 个位置的选法。
剩下 $n$ 个数的总和是 $m - s$，并且我们选的每个数不能小于对应位置所选的最小值。
但是我们并不知道，也不能知道每个位置上选的最小值。
我们考虑枚举有 $x$ 个位置上，$A_i$ 取的是最小值，这里有一个 $n\choose x$，现在考虑对应的 $B_i$ 的方案，因为这里 $A_i$ 的方案已经在前面算过了。
由于这些 $B_i$ 至少选到最小值，我们就把最小值先选上，然后剩下 $m - s$ 分配给 $x$ 个数可空，方案数是 $x + m - s + 1\choose m - s$。
剩下的 $n - x$ 个位置，同理，$A_i$ 选不为最小值的任意数，且和为 $m - s$，方案数是显然的 $m - s - 1 \choose n - x - 1$。
最后的式子是
$$ \sum\limits_{s=0}^m \sum\limits_{x=0}^n \bigg({{n \choose x}{n+s-1\choose s}{x + m - s - 1\choose m - s}{m - s - 1 \choose n -x - 1}{(2m - 2s)^2}}\bigg) $$
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-17 12:40:43
本题即求最大的独立点集。
如果设关系为两点是否可达，然后做一遍传递闭包，我们就把原问题转化为了图的最大反链。
最大反链就是说，在这条链上的所有点，都不满足这一偏序关系。我们统计最大反链的数量就是第一问的答案。
这怎么做？根据 Dilworth 定理，最大反链等于最小链覆盖，后者是经典题。匈牙利或者 Dinic 都好，前者好写。
然后看第二问，也就是构造一组解。
最开始感觉这问挺水的，好像很好构造，但是实际上比第三问麻烦。
我们先第一问匹配出来，然后从右边的非匹配点开始 DFS，右点只走非匹配边，左点只走匹配边，我们就可以知道哪些点被 DFS 到。
取集合 $S$ 代表左边被访问到与右边没有访问到的点的并，那么 $S$ 是一个最小点覆盖，它的补集就是最大独立集。
为啥？
点覆盖指的就是使得每条边的两个端点至少有一个被覆盖的点的集合。根据我们上面的构造方法，右边选取的点一定是匹配点。而如果一个右边的匹配点没有被选入，其一定是由左边某个匹配点访问到了，否则就产生了一条增广路，就不是最大匹配了。因此，一条边要么被左边点选中，要么被右边点选中。
根据这样，我们取 $S$ 的补集就能得到构造方案。
第三问要求我们判断一个点是否可能在最大独立集中。强制选择这个点，删除与它有关的所有点，然后再跑一遍就可以了。
鲁ICP备2025150228号