AT_abc_G选刷
目录ABC332G
题目大意
给定n种球，每种分别有\(a_i\)个，有m个盒子，每个盒子可以放\(b_i\)个球。特殊的，第i种球放在第\(j\)个箱子的最大数量为\(i\times j\)，问最后可以放最多可以放几个球(\(n\le500,m\le5e5\))
solution
首先可以非常简单的建出网络流，二分图，原点向第i个点连\(a_i\)的边，第j个点向汇点连\(b_i\)的边，\((i,j)\)连\(i\times j\)的边，最大流是答案。然后就最大流转最小割，求\(\sum_{i\in A}a_i+\sum_{j\in B}b_i+\sum_{i\in\complement A}\sum_{j\in\complement B}j\)
一开始想了一个\((n+m)n^2m^2\)的dp，表示\(f_{i,j}\)表示A集合中下标和为i，B集合中下标和为j的最小值，背包转移
然后考虑优化一下，观察一下，n比较小，设\(f_i\)表示A集合中下标和为i，\(a_i\)的最小和，然后对于每个j，贡献是\(min(i\times j,b_j)\)，最后按\(b_j/j\)排序，那么贡献就被分成两部分，用双指针+前缀和维护即可
ABC331G
题目大意
有 \(M\) 种颜色，用 \(1\sim M\) 编号，每次抽奖抽中第 \(i\) 种颜色的概率为 \(\frac{c_i}{N}\)，其中 \(\sum c_i=N\)，求抽中每种颜色至少一次的期望次数。
\(1\le M\le N\le 2\times 10^5\)。
solution
求至少一次的期望，就是求每个颜色第一次被抽中的时间的最大值
考虑min-max容斥
\[max(S)=\sum_{T\subseteq S}(-1)^{T+1}min(T) \]在期望上也适用，容易看出\(min(S)=\dfrac N{\sum_{i\subseteq S}c_i}\)
可以把S集合中的颜色看成 \(c=\sum_{i\subseteq S}c_i\) 的新颜色，然后解方程即可
考虑如何求max，把N提出来，把每个颜色看作多项式\((1-x^{c_i})\)，进行分治NTT，用系数统计答案即可
ABC328G
题目大意
给定两个长度为 \(n\) 的序列 \(a,b\) 和一个数字 \(c\)，有两种操作。
-
把 \(a\) 分成任意 \(x\) 个子段，并任意摆列他们的顺序，组成新的 \(a\) 序列，代价为 \(c\times (x-1)\)。
-
把 \(a_i\) 加上 \(x\)（\(x\) 为任意整数）代价是 \(|x|\)。
问把 \(a\) 变成 \(b\) 的最小代价， \(n\le 22\)。
solution
根据n比较小可以想到状压，考虑朴素的转移要设两维，分别表示状态和上一个填什么，然后转移，我们发现空间和时间都多了一个n，
考虑如何优化掉一个n，我们考虑设 \(f_s\) 表示s状态，然后暴力枚举全部是0的区间进行转移
证明一下时间复杂度，通过计算转移次数证明：每次转移时枚举一个全部是0的区间，所以有\((n-len+1)2^{n-len}\) 个
\[\sum_{len=1}^n(n-len+1)2^{n-len}=(n-1)2^n+2 \]ABC326G
题目大意
有 \(n\) 个技能，\(m\) 个成就。每个技能有一个等级，初始均为 \(1\)。
你可以用 \(c_i\) 块钱令技能 \(i\) 提升一个等级，该操作没有次数限制。
第 \(i\) 个成就达成的条件是对于 $\forall j\in [1,n],level_j \ge L_{i,j} $，其中 \(level_j\) 表示第 \(j\) 个技能的等级。达成成就 \(i\) 后，你会获得 \(a_i\) 元的奖励。
请最大化获得的奖励与所需成本之差，并输出该值。
\(n,m\le 50,\, 1\le L_{i,j}\le 5,\, 1\le a_i,c_i\le 10^6\)。
solution
根据等级比较小，可以想到拆点建图
从升级越多，奖励越多，转化为升级越多，不能享受的奖励越少
问题就变成 升级费用+不能得到的奖励 的最小值，用总奖励减去它，考虑最小割
如下图建图，黑边表示流量无限，蓝边的流量是升级的钱，红线的流量是奖励的钱。对于每个技能，拆成5个点，对于每个成就建一个点。
然后跑最小割即可
ABC324G
题目大意
给定一个长度为 \(n\) 的排列。有两种操作：
- 从序列的第 \(x\) 个位置将序列 \(s\) 分成两部分，其中前一部分（含 \(s\)）为新的序列 \(s\)，后面一部分为序列 \(s\)
- 按照值域，不改变原序列顺序从值 \(s\) 分为两部分，小于等于的为 \(s\) ，大于的为 \(i\)
每次操作完后询问序列 \(i\) 的长度
solution
考虑转化为数点问题，把每个数变成 \((i,a_i)\) 的点，因为两个分别是从两维割开矩形，所以序列长度就是矩形的点数
考虑如何动态维护矩形中第i个点和值，于是想到主席树，那么第二个操作就很简单的改变矩形范围即可
第一个操作还要找到矩形中第i个点，所以要二分找
ABC350G
题目大意
现有一张 \(n\) 结点的无向图，初始时没有边，接下来有 \(Q\) 次操作：
- 加入一条连接 \(u\to v\) 的边。保证操作前 \(u,v\) 不在同一个连通块内，换言之这张图总是森林。
- 询问是否存在和 \(u,v\) 都相邻的点，若存在输出编号，若不存在输出 \(0\)。
solution
考虑图一定为森林，我们可以维护出树的形态：
设 \(fa_i\) 表示 \(i\) 的父亲，那么连接 \(u\to v\) ，我们可以将 \(u\) 所在的树从根到 \(u\) 修改，使其以 \(u\) 为根，然后再 \(fa_u=v\)
我们考虑用启发式合并维护，时间复杂度为 \(O(n\log n)\)
有了 \(fa\) 数组，这道题目就是简单的
tips
关于这道题目的暴力，我们可以想到 \(O(\frac {n^2} {w})\)
鉴于一种很典的思想，我们把 \(deg\ge\sqrt n\) 的点记为大点，其他为小点，大点和大点之间的直接维护，大点和小点之间的用桶，小点和小点之间的直接暴力
不过本题的空间过不了
ABC352G
题目大意
有 \(n\) 种袜子，每种袜子有 \(a_i\) 只，问期望取出几只袜子能凑成一双
solution
因为：
\[\sum iP(x=i)=\sum P(x\ge i) \]所以我们考虑算出第i天还没结束的概率，相加即为答案
然后考虑 \(P(x\ge i)\) 如何计算，知道：
\[P(x\ge i)=\cfrac{\sum_{x_1\neq x_2...\neq x_i} a_{x_1}a_{x_2}...a_{x_i}}{\binom{i}{sum}} \]分子我们可以发现是 \([x^i]\prod_{j=1}^n(1+a_jx)\)
于是用分治NTT解决
标签：le,题目,sum,solution,选刷,序列,abc,大意 From： https://www.cnblogs.com/zhy114514/p/18258905