CVBB ACM Team

题目大意：给你 $n$ 个整数，每次操作可以选取两个整数 $x,y$，将 $2x-y$ 加到集合中。问能否凑出 $k$。

题解：注意到可以将所有数加上一个常数，结果不变。不妨将所有数减去 $x_{1}$。现在显然能构造出所有数的倍数。如果 $k-x_{1}$ 不能被这些数的 $\gcd$ 整除，那么显然无解。否则考虑任意两个数 $u,v$ 的 $\gcd$，以及裴蜀定理，$ux+vy=\gcd$。可以证明存在不全为奇数的 $x,y$。这是因为，考虑 $ux'+vy'=0$，其中 $(x',y')=1$，那么 $x',y'$ 中至少有一个奇数。把 $(x',y')$ 与 $(x,y)$ 组合，就很容易构造出一个存在偶数的解。那么这个解显然可以通过 $2x-y$ 得到。

题目大意：给你两个 01 串 $s,t$，以及 $m$ 次操作 $[l_{i},r_{i}]$。操作时你需要保证 $s[l_{i},r_{i}]$ 中的字符相同，随后你可以修改其中严格小于一半数量的字符。问能否在满足要求的前提下，把 $s$ 修改成 $t$。

题解：倒序思考，由于每次只能修改严格小于一半的字符，且修改前所有字符相同，因此把 $t$ 改回去只有一种可能。线段树维护。

题目大意：给定平面上 $n$ 个不同的点，给它们排个顺序，使得任意 $\angle A_{i}A_{i+1}A_{i+2}$ 是严格的锐角。

题解：从任意一点出发，走到剩下的点中离它欧氏距离最远的点即可。很容易证明这样不会存在直角或钝角。

题目大意：给出 $m$ 个 pair $(l_{i},r_{i})$，要求构造两个 $1\sim n$ 的排列，满足对于每个 pair，$p_{l_{i}},p_{r_{i}}$ 及 $q_{l_{i}},q_{r_{i}}$ 的大小关系相同，或者说 $(p_{l_{i}}-p_{r_{i}})(q_{l_{i}}-q_{r_{i}})>0$。定义这两个排列的价值是它们不相同的位置数。求最大价值及一种方案。

题解：将限制建成一个无向图。若某个点与其它点都有边，那么显然它在 $p,q$ 中必须相同，我们不妨递归地把这样的点删去。那么剩下的点中，每个点的度都不满。

我们构造一种方案，证明这种情况下可以找到两个所有位置都不同的排列。注意到如果能够将图分成几个部分，其中每个部分可以完全重新排列，不同部分之间顺序保持不变即可，这样可以简化问题。其中一种满足要求的结构是菊花图：如果某些点之间的限制的补图是菊花图，即不妨设点 $1$ 与其它点之间没有边，那么可以构造两个排列 $1,2,\ldots,n$ 和 $n,1,2,\ldots,n-1$。

考虑原图的补图的生成森林。由于没有孤立点，因此所有树至少有两个点。我们需要将它们分解成一些菊花图。对于任意一棵树，任取一个非叶子结点作为根，它的儿子中，把所有非叶子的子树递归下去求解，而所有叶子和根组成一个菊花图。

题目大意：有两只队伍，第一只队伍的权值分别是 $a_{1},\ldots,a_{n}$，第二只队伍的权值分别是 $b_{1},\ldots,b_{m}$。现将这 $n+m$ 个人按某种顺序排序，登台表演。有一个分数计数器，开始等于 $k$，假设一个人的权值是 $x$，他前一个人的权值是 $y$（对于第一个人，$y=x$），那么分数计数器增加 $y-x$。但是当分数计数器变为负数是，它会变为 $0$。当前这个人的得分就是分数计数器的值。你需要求出队伍 $1$ 的分数和减队伍 $2$ 的分数和的最大值。

此外，题目有若干修改操作，修改 $a$ 或 $b$，以及若干次询问，给定 $k$ 求答案。

题解：考虑一个权值序列 $f_{1},f_{2},\ldots,f_{n+m}$，补充定义 $f_{0}=a_{0}-k$。容易发现 $i$ 的得分 $s_{i}=f_{i}-\min_{0\le j\le i}\{f_{j}\}$。记 $p_{i}=\min_{0\le j\le i}\{f_{j}\}$。

不妨先枚举第一个元素。那么显然，其余元素中，第一只队伍的成员一定在所有第二只队伍的成员后面。考虑 $i$ 属于队伍 $1$，$i+1$ 属于队伍 $2$。交换它们之后，显然 $p_{i}\ge p'_{i+1}$，即队伍 $1$ 的收益不变小，而 $p_{i+1}\le p'_{i}$，即队伍 $2$ 的收益不变大。因此交换一定更优。

第二只队伍一定从大到小排序。考虑两个相邻的队伍二成员 $f_{i}<f_{i+1}$。那么交换后队伍二的前缀最小值变大，收益减小。同理第一只队伍一定从小到大排序。

接下来分类讨论：

• 若 $f_{1}-k\le p_{n+m}$，那么 $p$ 数组是个常数。根据 $n$ 与 $m$ 的相对大小即可确定要让 $f_{1}$ 尽可能大或尽可能小。
• 否则，若第一个元素属于第二只队伍。那么 $p_{m+1}\sim p_{n+m}$ 是常数，因此第一只队伍的答案是常数，只需要选取最大的 $f_{1}$ 即可。
• 否则，若第一个元素属于第一只队伍。那么 $p_{m+2}\sim p_{n+m}$ 是常数，那么第一组相对损失了 $f_{1}$ 的价值，但是 $f_{1}$ 越大时，第二组的收益也越小，看似不好判断。但是，假设 $f_{1}$ 增加 $\Delta$ 时，注意到第一组的损失为 $\Delta$，而当 $f_{1}-k+\Delta\le a_{1}$ 时，第二组的损失也至少是 $\Delta$。说人话就是当 $b_{i}-k<b_{j}-k\le a_{1}$ 时，$b_{j}-k$ 总是更优。而当 $b_{i}-k>a_{1}$ 时，显然增大 $b_{i}$ 又没有必要了。最终只需要考虑 $a_{1}$ 左右的两个元素。

整个算法可以用一棵平衡树或线段树实现，时间复杂度 $\mathcal{O}(n\log n)$。

真难写啊。

题目大意：有 $n$ 个巧克力棒，每次按长度比例选取其中一根，设它的长度为 $x$，等概率随机 $y\sim U(0,x)$，将它分成 $y,x-y$ 的两根。直到所有棒长度都 $\le k$ 为止。求期望次数。

题解：不妨先考虑 $1$ 根巧克力棒。不妨认为巧克力棒并未分开，只是在 $y$ 处打了个标记。不妨设棒的长度为 $1$。那么问题等价于随机选取独立同分布的 $X_{1},X_{2},\ldots,X_{n}\sim U(0,1)$，在这些位置切断。考虑统计量 $X_{(1)},X_{(2)},\ldots,X_{(n)}$，$Y_{1}=X_{(1)},Y_{2}=X_{(2)}-X_{(1)},\ldots,Y_{n}=X_{(n)}-X_{(n-1)}$ 的联合分布为 $n!I_{\{0<y_{1},y_{2},\ldots,y_{n}<1,0<\sum_{i=1}^{n}y_{i}<1\}}$。

考虑答案，显然为 $\sum_{i=0}^{+\infty}1-p_{i}$，其中 $p_{n}$ 表示第 $n$ 次分割后所有棒 $\le k$ 的概率。那么

$$ \begin{aligned} p_{n}&=n!\int_{0<y_{1},y_{2},\ldots,y_{n}<k,1-k<\sum_{i=1}^{n}y_{i}<1}1\mathrm{d}\mathbf{y}\\ &=n!k^{n}\int_{0<z_{1},z_{2},\ldots,z_{n}<1,1/k-1<\sum_{i=1}^{n}z_{i}<1/k}1\mathrm{d}\mathbf{z} \end{aligned} $$

其中，$\sum_{i=1}^{n}Z_{i}$ 服从 Irwin–Hall 分布，即 $F(x)=\frac{1}{n!}\sum_{k=0}^{\lfloor x\rfloor}(-1)^{k}{n\choose k}(x-k)^{n}$，因此

$$ \begin{aligned} p_{n}&=n!k^{n}\left(F(\frac{1}{k})-F(\frac{1}{k}-1)\right)\\ &=k^{n}\left(\sum_{i=0}^{\lfloor 1/k\rfloor}(-1)^{i}{n\choose i}(1/k-i)^{n}-\sum_{i=0}^{\lfloor 1/k-1\rfloor}(-1)^{i}{n\choose i}(1/k-1-i)^{n}\right)\\ &=\sum_{i=0}^{\lfloor 1/k\rfloor}(-1)^{i}{n\choose i}(1-ik)^{n}-\sum_{i=0}^{\lfloor 1/k-1\rfloor}(-1)^{i}{n\choose i}(1-k-ik)^{n} \end{aligned} $$

注意到这里的关键是要求出

$$ \begin{aligned} &\sum_{i=0}^{+\infty}{i\choose k}x^{i}\\ =&x^{k}\sum_{i=0}^{+\infty}{i+k\choose k}x^{i}\\ =&x^{k}(1-x)^{-k-1} \end{aligned} $$

当有多根巧克力棒时，设 $q_{i}$ 为第 $i$ 根巧克力棒被选的概率，$p_{ij}$ 为第 $i$ 根巧克力棒，经过 $j$ 次分割后已经 $\le k_{i}$ 的概率。那么

$$ \begin{aligned} P_{n}=\sum_{n_{1}+\ldots+n_{m}}\frac{n!}{n_{1}!\cdots n_{m}!}\prod_{i=1}^{m}q_{i}^{n_{i}}p_{in_{i}} \end{aligned} $$

考虑

$$ \begin{aligned} &\sum_{i=0}^{+\infty}\frac{1}{i!}{i\choose k}x^{i}\\ =&\frac{1}{k!}\sum_{i=k}^{+\infty}\frac{1}{(i-k)!}x^{i}\\ =&\frac{x^{k}}{k!}\sum_{i=0}^{+\infty}\frac{1}{i!}x^{i}\\ =&\frac{x^{k}e^{x}}{k!} \end{aligned} $$

那么

$$ \begin{aligned} P(x)&=\sum_{n=0}^{+\infty}\frac{1}{n!}q^{n}p_{n}x^{n}\\ &=\sum_{n=0}^{+\infty}\frac{1}{n!}\left(\sum_{i=0}^{\lfloor 1/k\rfloor}(-1)^{i}{n\choose i}(qx-qikx)^{n}-\sum_{i=0}^{\lfloor 1/k-1\rfloor}(-1)^{i}{n\choose i}(qx-qkx-qikx)^{n}\right)\\ &=\sum_{i=0}^{\lfloor 1/k\rfloor}(-1)^{i}\frac{(qx-qikx)^{i}e^{qx-qikx}}{i!}-\sum_{i=0}^{\lfloor 1/k-1\rfloor}(-1)^{i}\frac{(qx-qkx-qikx)^{i}e^{qx-qkx-qikx}}{i!} \end{aligned} $$

对于 $P_{j}(x)$ 来说，$q=\frac{L_{j}}{L}$，$k=\frac{K}{L_{j}}$。因此

$$ \begin{aligned} P_{j}(x)&=e^{qx}\left(\sum_{i=0}^{\lfloor 1/k\rfloor}a_{ji}x^{i}e^{-bix}-\sum_{i=0}^{\lfloor 1/k-1\rfloor}(-1)^{i}c_{ji}x^{i}e^{-bx-bix}\right)\\ &=e^{qx}\left(\sum_{i=0}^{\lfloor 1/k\rfloor}a_{ji}(xe^{-bx})^{i}-\sum_{i=0}^{\lfloor 1/k-1\rfloor}c_{ji}x^{-1}(xe^{-bx})^{i+1}\right)\\ &=e^{qx}\left(\sum_{i=0}^{\lfloor 1/k\rfloor}a_{ji}y^{i}-\sum_{i=0}^{\lfloor 1/k-1\rfloor}c_{ji}x^{-1}y^{i+1}\right) \end{aligned} $$

其中 $b=\frac{K}{L}$ 是一个常数，$y=xe^{-bx}$。

答案为 $\sum_{n=0}^{+\infty}1-P_{n}$，它的指数型生成函数为 $e^{x}-\prod_{i=1}^{m}P_{i}(x)$。

这是一个简单的二元生成函数问题，在本题有两种实现方式。一种是按两两合并的方式相乘，复杂度是 $\mathcal{O}(nL\log nL)$。如果把 $x$ 部分看作系数，由于每个乘项 $x$ 最高只有一次，这很棒，复杂度是 $\mathcal{O}(n^{2}L+nL\log L)$。

对于乘积的一项 $x^{a}e^{bx}$，它给答案的贡献应当是

$$ \begin{aligned} &\sum_{i=a}^{+\infty}i![x^{i}]x^{a}e^{bx}\\ =&\sum_{i=a}^{+\infty}i!\frac{b^{i-a}}{(i-a)!}\\ =&a!\sum_{i=0}^{+\infty}{i+a\choose i}b^{i}\\ =&a!(1-b)^{-a-1} \end{aligned} $$

本题需要特别注意 $0^{0}$ 的处理。