2024.10.11总结

本文于github博客同步更新

最简单但挂分最惨的一集。

唐死我了唐死我了唐死我了唐死我了唐死我了唐死我了唐死我了唐死我了唐死我了唐死我了唐死我了唐死我了唐死我了唐死我了唐死我了唐死我了唐死我了唐死我了唐死我了唐死我了唐死我了唐死我了唐死我了唐死我了唐死我了唐死我了唐死我了唐死我了唐死我了唐死我了唐死我了唐死我了唐死我了唐死我了唐死我了唐死我唐

A：

首先特判 \(n=1\)，考虑 \(n>1\) 的情况：

容易发现在树为链的时候 \(ans\) 最大，为 \(\left\lfloor\frac{n}{2}\right\rfloor+1\)；在树为菊花的时候 \(ans\) 最小，为 \(2\)，继续往下找规律，发现将一个链尾指向链首，形成链套菊花，每次操作可以使答案减少 1。

然后模拟即可。

B：

对于每个点，维护 \(val_i\) 为当前点能跳到的最靠左的端点。

对于 \(\forall i\in[1,n],c_i=c_n\)，每次二分 + 哈希找到 \(L_{min}\)，\(val_i=\min(L_{min},val_j,j\in[L-1,i])\)，其余的 \(val\) 赋为 \(n+1\) 即可。

树状数组维护即可，时间复杂度为 \(\mathcal O(n\log n)\)。

C：

先考虑第二条限制，容易发现 \(B\) 中的数不能重复，接着打表发现 \(1\) 只能放在第一位，\(2\) 和 \(4\) 只能出现一个，\(3\) 只能放在最后，其余的数需倒序放置。

差不多是这样：\(1,n,n-1...\{4,2\},3\)。

现在带入第一条限制，容易发现最终取出的序列形态只有两种：

• \(\{1,x,y,z\}(x>y>z>1)\)
• \(\{1,x,y,2,3\}(x>y\neq4)\)

设 \(f_{i,j}\) 为将 \(A_j\) 放在 \(B_i\) 的方案数，不难发现转移区间为 \(f_{i-1}\) 的一段后缀，开若干个树状数组优化转移即可。

时间复杂度为 \(\mathcal O(n\log n)\)。

D：

不会，没讲，广二老哥一个没改我改集贸。

扔个题解：

我们先忽略把圣遗物分成两份这个限制，思考该弱化版下二人的策略。

可以感知到，在最终局面中，对于每一个圣遗物，二人都会尽量做到平均分配。

这说明对于 \(s_{i} \not \equiv-1\left(\bmod 2 a_{i}\right)\) 的圣遗物 \(i\) ，二人的收益都是 \(c_{i}\left\lfloor\frac{s_{i}}{2 a_{i}}\right\rfloor\) 。而对于 \(s_{i} \equiv-1\left(\bmod 2a_{i}\right)\) 的圣遗物 \(i\) ，我们按 \(c\) 从大到小将其排序成 \(p_{1}, p_{2}, \ldots, p_{m}\) ，则先手的额外收益为 \(\sum_{2 i+1 \leq m} c_{p_{2 i+1}}\) ，后手的额外收益为 \(\sum_{2 i \leq m} c_{p_{2 i}}\) 。

回到原问题，我们据此 dp ，将所有圣遗物按 \(c_{i}\) 从大到小排序，用 \(dp_{i, j, c_{1}, c_{2}}\) 表示考虑完前 \(i\) 种圣遗物，第一份圣遗物个数为 \(j\) ，两份中 \(s_{i} \equiv-1\left(\bmod 2 a_{i}\right)\) 的圣遗物 \(i\) 的个数的奇偶性分别为 \(c_{1}, c_{2}\) 小 w 的最大收益。转移时同时考虑一般贡献和额外贡献即可。

时间复杂度 \(\mathcal O\left(\left(\sum s_{i}\right)^{2}\right)\) ，可以通过第二个 Subtask。

注意到，令其中一份中圣遗物 \(i\) 的数量为 \(x_{i}\) ，对于 \(x_{i} \bmod 2 a_{i}\) 值相同的 \(x_{i}\) ，最终两份中圣遗物 \(i\) 的贡献和是相同的，这启示我们只枚举 \(x_{i} \in\left[0,2 a_{i}\right)\) ，但注意到我们原来的 dp 是在做背包的同时计算贡献，如果这样处理后背包便无法进行，于是我们考虑将背包分成 \(\bmod 2 a_{i}\) 的余数和 \(2 a_{i}\) 的倍数两部分做。

特判掉 \(s_{i}<2 a_{i}\) 的圣遗物，这些圣遗物我们用之前的 dp 暴力做，对于剩下部分，我们将余数做背包的同时算贡献，这部分复杂度为 \(\mathcal O\left(\left(\sum a_{i}\right)^{2}\right)\) 。

对于倍数部分的背包，我们需要知道倍数枚举的上界，但这和余数的实际值有关，看似无法继续。但观察到，可能的上界只有两种：令圣遗物 \(i\) 分给第一份的个数的余数部分为 \(r_{i}\) ，则当 \(r_{i} \leq s_{i} \bmod 2 a_{i}\) 时，上界为 \(\left\lfloor\frac{s_{i}}{2 a_{i}}\right\rfloor\) ，否则为 \(\left\lfloor\frac{s_{i}}{2 a_{i}}\right\rfloor-1\) 。

我们不妨统一令上界为 \(\left\lfloor\frac{s_{i}}{2 a_{i}}\right\rfloor-1\) ，同时对于余数部分的 dp ，如果 \(r_{i} \leq s_{i} \bmod 2 a_{i}\) ，我们多进行一个大小为 \(r_{i}+2 a_{i}\) 背包转移即可。

于是我们只用关心倍数部分的背包，即：给定 \(n\) 种物品，第 \(i\) 种物品有 \(L_{i}=\left\lfloor\frac{s_{i}}{2 a_{i}}\right\rfloor-1\) 个，每一个的体积为 \(V_{i}=2 a_{i}\) ，问能不能凑出某个固定大小的背包。暴力做还是是 \(\mathcal O\left(\left(\sum s_{i}\right)^{2}\right)\) 的，但这显然可以 bitset 优化，可以通过第三个 Subtask。

做可行性 dp 显然是浪费的，我们更改定义为 \(g_{i, j}\) 表示前 \(i\) 种物品想凑出大小为 \(j\) 的背包，第 \(i\) 个物品至少要选多少个，不合法则 \(g_{i, j}=-1\) 。

对于该 dp ，显然可以通过分讨 \(\mathcal O(1)\) 转移，时间复杂度 \(\mathcal O\left(n \sum s_{i}\right)\) ，可以通过第四个 Subtask。

考虑继续优化。我们发现，其实很多物品都是等价的。具体地，由于 \(2 a_{i}\) 只有最多 \(\sqrt{\sum} a_{i}\) 种，故我们把体积相同的物品合并，再做刚刚的 dp ，时间复杂度 \(\mathcal O\left(\sqrt{\sum} a_{i} \sum s_{i}\right)\) ，可以通过本题。