260427 - 260507

P6313 [eJOI 2018] 护照

两张护照是独立的，可以通过一次卷积求出答案。显然完成一个集合的签证肯定是时间越早越好，所以直接设 dp 表示最早时间，随便转移即可。

P8293 [省选联考 2022] 序列变换

把操作上树，根据贪心可以得知肯定是由浅到深依次合并。分讨四种代价系数，其中三种都是比较显然的贪心策略，\(x=1,~y=0\) 是最下面的节点不产生贡献，所以特判一下是把谁放到最下面，那么这个东西走过的路都不能留住它，贡献有变但是情况很少容易计算。

CF1876G Clubstep

过程是显然的，考虑 \(q\) 次贪心一起跑，从右往左扫描线，形如把过高的限制跟 \(a_i\) 取个平均数上取整，并加上对应的贡献。这玩意的差分数组的对数之和显然有势能，用平衡树维护可以做到 \(O((n+q)\log n\log V)\)。

P5208 [WC2019] I 君的商店

排序完了显然可以二分，考虑怎么排序，发现只比较两个数没什么意义，拿三个数 \(a,b,c\) 出来，先比较 \(b,c\)，然后比较 \(a\) 和 \(b+c\)，若大于等于，则 \(b,c\) 中的较小者为 \(0\)，若小于等于，则较大者大于等于 \(a\)。

这样我们会将 \(n-1\) 个数排序，剩一个数不知道，先特判掉剩的数是 \(1\)，别的都是 \(0\) 的情况，然后对 \(n-1\) 个数二分，现在剩两个数不知道，拿一个 \(1\) 跟两个数进行上面的过程即可确定一个数，再根据奇偶性确定另一个数即可。

P5073 [Ynoi Easy Round 2015] 世上最幸福的女孩

对线段树的每个区间维护最大前缀和、最大后缀和以及答案，显然我们只关心凸包上的点，合并形如凸包拼接、卷积和取 \(\min\)，\(O(n\log n)\) 预处理凸包然后直接回答即可。可以通过各种离线手段做到 \(O(n\log n)\) 的时间和线性空间。

CF1558E Down Below

首先二分答案。从当前已经到达的点集往外走，走回到原先的点集或者走出一个环，这样的一次扩展显然是不劣的。又注意到如果能从原先的点集出发，通过两条不相交的路径走到一个点，那么一定可以走回去形成一个环，这样一个点不会被经过两次，dfs 就是对的，时间复杂度 \(O(n\log V)\)。

CF1644F Basis

第二个限制可以看成：两个数组是本质相同的，当且仅当元素的相等关系相同，方案数显然是斯特林数一列的某个前缀的和。如果一个数组的所有连续段（除了最后一段）长度的 \(\gcd>1\)，那么它可以被表示出来。对这个 \(\gcd\) 进行莫反，用卷积算一下一行的斯特林数即可。

需要特判 \(n=1\)。

P10896 移言丁真：Unavoided linyue

先考虑最优策略是什么，由于不匹配的括号数量等于起点到最低点的高度差加上最低点到终点的高度差，所以肯定是把左括号比右括号多的串放到最低点右边，反之放到左边，产生 \(|h_1-h_2|\) 的贡献。然后最低点的串额外产生 \(\min(h_1,h_2)\) 的贡献。

容易发现把 \(\min(h_1,h_2)\) 最大的串放到中间可以使它成为最低点。

\(|h_1-h_2|\) 的贡献显然容易计算，\(\max\min(h_1,h_2)\) 考虑拆贡献，改为对每一个 \(k\) 统计全部 \(\min(h_1,h_2)\le k\) 的概率。考虑 \(f(n,k)\) 向 \(f(n+1,k)\) 的递推式，由于第 \(n+1\) 步可以往上走或者往下走，然后有一些方案会变成合法（\(>k\to k+1\to k\)）有些会变成不合法（\(>k\to k\to k+1\)），即：

\[ f(n+1,k)=f(n,k)+2^{-n-1}\Big[\binom{n}{\lceil n/2\rceil+k+1}-\binom{n}{\lfloor n/2\rfloor+k+1}\Big] \]

这里的格路计数是从定点走到某个范围的高度，不穿过 \(x\) 轴，稍微推一下发现组合数两两消掉了，只剩一个。显然只有 \(n\) 为奇数时有值，所以

\[ f(n,k)=1+\sum_{i=1}^{\lfloor n/2\rfloor}2^{-2i}\Big[\binom{2i-1}{i+k+1}-\binom{2i-1}{i+k}\Big] \]

由于直接对 \(n\) 递推复杂度不对，没什么前途，考虑改成对 \(k\) 递推，然后应用组合数恒等式：

\[ \begin{align*} f(n,k+1)&=f(n,k)+\sum_{i=1}^{\lfloor n/2\rfloor}2^{-2i}\Big[\binom{2i-1}{i+k+2}-2\binom{2i-1}{i+k+1}+\binom{2i-1}{i+k}\Big]\\ &=f(n,k)+\sum_{i=1}^{\lfloor n/2\rfloor}2^{-2i}\Big[\binom{2i+1}{i+k+2}-4\binom{2i-1}{i+k+1}\Big]\\ &=f(n,k)+2^{-2\lfloor\frac{n}{2}\rfloor}\binom{2\lfloor\frac{n}{2}\rfloor+1}{\lfloor\frac{n}{2}\rfloor+k+2}-\binom{1}{k+2} \end{align*} \]

手动计算 \(f(n,0)\) 的初值并代入，发现如果设置 \(f(n,-1)=0\)，那么可以直接扔掉 \(\binom{1}{k+2}\)，于是直接枚举 \(k\) 并对每个串分别根据 \(f(n,k-1)\) 计算 \(f(n,k)\) 即可。值得注意的是，显然 \(k>\lfloor\frac{n}{2}\rfloor-1\) 时 \(f(n,k)\) 就始终等于 \(1\) 了，所以不用管。

AT_arc156_e [ARC156E] Non-Adjacent Matching

考虑充要条件，其实是总和 \(S\) 是偶数，并且所有 \(i,(i+1)\bmod n\) 的和不超过数组中其他数的和。也许可以通过手模小样例猜测出来。充分性是容易证明的，考虑下一次不合法当且仅当有三个不相交的满足 \(sum=\frac{S}{2}\) 的区间，这显然不可能。

考虑计数。正难则反，先考虑计算总方案数，可以不用 gf，考虑容斥一个集合的位置超过 \(m\)，然后一个组合数做完了。然后是一个位置和两个位置不合法，注意到如果存在一个位置不合法，那么 \(S\) 不会超过 \(4m\)，直接背包即可。时间复杂度 \(O(n^2)\) 级别。

qoj12156 Furniture

上下两排显然是分别按照高度递增和递减排序，如果已经知道上下两排各自的集合，考虑将两个阶梯尽可能向中间移动，那么合法的充要条件是不能再移动时两阶梯大头侧的距离不超过 \(a\)，并且各自也不超过 \(a\)。我们将块按照高度 \(\le\lfloor b/2\rfloor\) 进行分类，大的一组看作限制，小的一组看作被限制。

按照限制与被限制的高度从大到小考虑，每次考虑当前块放到上面还是下面，显然后面的限制不能碰到前面的限制和被限制。钦定该位置是卡住两阶梯的接触点，稍微分析一下其实就是 \(sum+i\le a\wedge sum+(cur-i)\le a\)，其中 \(sum\) 是还没放进来的限制，\(i\) 是上面一排的宽度和。用 bitset 优化 dp 即可，复杂度 \(O(\frac{na}{w})\)。