22 年 syzx 春季训练 13
phtniit
·
·
个人记录
A: cf830a
n 个人分别在坐标轴的 {a_i} 的位置处，他们要齐聚到坐标轴 p 的位置。
坐标轴的 k（ n <= k） 个不同的位置 {$b_i$} 处分别放有一把钥匙，每把钥匙只能被一个人捡起。
问所有人分别取得钥匙后到达指定位置，最优策略下最晚的人要多长时间抵达 $p$（已知每个人单位时间可以移动一个长度）。
## 题解
**贪心，枚举**。
我们当然可以二分最晚的时间，然后得到每个人可以取钥匙的区间，复杂度大概是 O(N * log)。
但是 N 和 K 这么小，这题可以做得更简单。
注意到：**存在最优方案使得所有人取钥匙的位置一定可以是一个连续的位置区间**（自行感受证明）。
那么排序后，我们可以枚举第一个人取钥匙的位置，然后 O(n) 计算每个人需要花费的时间，取 min 得到答案即可。
```cpp
i64 ans = inf;
for (int i = 0; i + n <= k; ++i) {
i64 tmp = 0;
for (int j = i, j2 = 0; j2 < n; ++j, ++j2)
tmp = max(abs(a[j2] - b[j]) + abs(b[j] - p), tmp);
ans = min(ans, tmp);
}
```
# [B: abc238e](https://vjudge.net/problem/AtCoder-abc238_e)
琦琦有私房钱，表示为一个秘密的数组$A$ 。存存不知道一共有多少钱，只知道这个数组 A 的长度是$N$ 。
韬韬搜集了$Q$ 个提示，第 $i$ 个提示是数组 $A$ 中 $l_i$ 到 $r_i$ 连续元素的区间和。问存存能否根据韬韬的这 $Q$ 个提示知道琦琦一共有多少私房钱（数组 $A$ 中所有元素的和）？
如果能，输出 Yes ；否则，输出 No。
## 题解
**并查集**。
我们对前缀和建点：对于知道 $[L_i, R_i]$ 的和，我们对 $L_i-1$ 和 $R_i$ 连边，如果 0 和 n 连通，则有解。
# [C: cf985e](https://vjudge.net/problem/CodeForces-985E)
给定一个数组 {$a_i$}，问是否可以切成若干组，保证：
* 同一组内的都是相邻的元素；
* 每个组内至少有 $k$ 个元素；
* 同一组内的差值不能超过 $d$，即同一组内任意 i 和 j 满足 $|a_i - a_j| <= d$。
## 题解
**dp**。
首先肯定是排序。
然后定义 $dp_i$ 表示排序后前 i 个元素的数组是否能被切分。
考虑组内差值不超过 d 的条件，对于每个元素 i 我们可以预处理出其对应的最晚位置（二分/双指针），$last_i$。
那么 $dp_i$ 可以通过 $[last_i, i-k]$ 转移过来，我们可以使用任意数据结构维护。
# [D: cf995a](https://vjudge.net/problem/CodeForces-995A)
停车场是如下图 4 行 N 列的形状。
上下两行是停车位，中间两行是待入库的车辆。
第 1 行和第 4 行描述的是车位的所属，用数字代表，其中 0 表示禁止停车。
第 2 行和第 3 行描述的是车辆的当前情况，用数字代表，其中 0 表示该位置无车辆。
我们的目标是在 20000 个步骤里把所有车辆入库。
每次操作我们可以指定一辆车移动到其附近可能的 4 个位置之一，当且仅当那个位置：
* 没有开出停车场；
* 没有其他车辆；
* 不是禁止停车位；
* 不是别人车辆的车库。
请输出任意一个可能的方案，或者对于不存在方案的情况，请输出 -1。
## 题解
**队列、模拟**。
无解当且仅当，第 2 行和第 3 行放满了车辆，且所有车辆都不在自己的车库旁边，动弹不得。
否则我们总是可以让所有车辆用环形队列连起来，然后按照顺时针方向旋转。
那么每个车辆最多不会转动超过 1 圈，就可以到达自己停车位旁边，然后入库。
# [E: abc247f](https://vjudge.net/problem/AtCoder-abc247_f)
N 张扑克，第 i 张扑克正面写了 $P_i$，背面写了 $Q_i$。
{$P_i$} 恰好是 1 到 N 的排列。
{$Q_i$} 也恰好是 1 到 N 的排列。
问有多少种选择扑克的方式，使得 1 到 N 都出现在选中扑克的正面或背面上。
## 题解
**dp**。
我们考虑虚拟 N 个点，每张扑克正面的 $P_i$ 指向 $Q_i$，由于 $P$ 和 $Q$ 都是排列，所以我们会得到若干个环。
对于每个环，相邻的两个节点必须选一个。
对于这个模型，我们可以建立 dp 处理。
$f_{i,1/0}$ 表示长度为 i 的环，首元素不选的情况下，这个元素**选/不选**，即 1/0，的情况，有多少种方案。
$g_{i,1/0}$ 表示长度为 i 的环，首元素被选的情况下，这个元素**选/不选**，即 1/0，的情况，有多少种方案。
那么对于长度为 len 且超过 1 的环，合法的方案应该是 $f_{len,1} + g_{len,0} + g_{len,1}$。
则 $ans = \prod\{f_{len_i,1} + g_{len_i,0} + g_{len_i,1}\}$。
# [F: arc138c](https://vjudge.net/problem/AtCoder-arc138_c)
两个人在玩游戏：
* 游戏共有 N（N 是偶数） 张扑克组成，第 i 张扑克上面有一个数 $A_i$；
* 先手每次可以任意选择一张还没有被选择的扑克；
* 后手每次会老实选择最上面一张扑克；
* 每个人会获得他选中扑克的分数。
先手为了扩大优势（游戏结束时分数尽量大），决定在开始游戏前，切一次牌：**把牌堆顶部任意 $k$ 张扑克放到牌堆底部**，即切牌后变成 {$A_{k+1}, A_{k+2}...,A_N,A_1,...A_k$}。
问当 $k$ 选择什么的时候，先手可以获得最多分数，以及该分数是多少。
## 题解
**贪心**。
首先先手肯定可以取得最大的 N/2 张扑克。
假设排序后的扑克，前 N/2 小的扑克我们赋值 -1，较大的扑克我们赋值 +1：
* 考虑对于输入的扑克序列的循环序列（展开成 N\*2)，那么一定存在一个长度为 N 的连续子序列，其前缀和均小于等于 0。
若我们取该连续子序列作为循环右移之后的 k 扑克，先手总是取最靠近牌堆顶部的 +1，则后手只能取得 -1 的牌。
故先手可以取得所有的 +1。
> 更严格的推广：
> 即 **raney 引理**：若一个序列 $\{x_i\}$，满足 $\sum{x_i} = +1$，则 x 序列的循环排列中有且仅有一种，满足前缀和均大于 0。
# [G: luoguP6672](https://vjudge.net/problem/%E6%B4%9B%E8%B0%B7-P6672)
游戏王黑暗大法师的背景。
你有 M+1 张牌，其中有 1 张关键牌，沉在牌堆底部。
另外有 N 张特殊牌，他们有过牌的能力：即抽中它之后你可以继续抽接下来的 $A_i$ 张牌，$\sum{A_i}$ 恰好等于 M，所以不会爆牌。
问有多少种牌堆的排列，可以使得你抽完第一张牌之后，可以顺利抽到牌堆底部的关键牌（即把所有牌抽光）。
## 题解
**raney 引理**
我们先不考虑最后那张关键牌，只把它当作普通牌，那么我们的目标是先求**把所有牌抽光的方案**，记作 ans2，则答案 ans = ans2/(M+1-N)，因为在定义下的所有方案里，这张特殊牌和其他 M-N 的普通牌是等价的。
现在考虑有多少种方案可以把所有牌抽光，类似 F 题：
* 对于特殊牌，我们赋值为 $b_i = A_i -1$；
* 对于普通牌，我们赋值为 $b_i = -1$。
则 $\sum{b_i} = -1$。
观察构造后的 $\{b_i\}$，显然，当且仅当前缀和都为非负数的时候，可以取多至少一张牌，由于 $\sum$ = -1，前缀和非负数，即后缀和均为负数。
考虑 F 题更严格的推广，即 **raney 引理**：若一个序列 $\{x_i\}$，满足 $\sum{x_i} = +1$，则 x 序列的循环排列中有且仅有一种，满足前缀和均大于 0。
前缀和和后缀和是一样的。
所以能把牌抽光的方案是圆排列的个数，即 $(m+1)! / (m+1) = m!$。
最终 $ans=m!/(m+1-n)$。
# [H: cf1523d](https://vjudge.net/problem/CodeForces-1523D)
有 m 种货币 n 个商人，已知第 i 个人是否喜欢第 j 种货币且每个人至多喜欢 p 种货币。
选择最多个货币种类使得有不少于 $\lceil \frac{n}{2}\rceil$ 个人喜欢所有选出的货币种类。
## 题解
**随机化 + fwt**。
由于 m 较大而 p 很小，考虑在 p 上下功夫。
假如我们知道某个人是 $\lceil \frac{n}{2}\rceil$ 个人中的一个，我们可以枚举他喜欢的子集作为答案，只需要计算出有多少个人满足该子集即可，可以使用 fwt 来求。
由于有 $\lceil \frac{n}{2}\rceil$ 个人必须喜欢，那么我们随便拎一个人出来，他会喜欢的概率有 p>=0.5。
那么我们可以随机拎 k 个人出来，答案正确性可以有 $1-0.5^k$，k 足够大即可。
随机化算法复杂度是 $O(k * p * 2^p)$。
# [I: arc139d](https://vjudge.net/problem/AtCoder-arc139_d)
给定一个长度为 N 的数组 $\{A_i\}$，值域 $[1, M]$。
执行下述操作 K 轮，我们仍然可以得到一个长度为 N 的数组 $A'$：
* 随机产生一个 $[1, M]$ 中的数；
* 把该数放到数组中；
* 去掉新数组中第 X 小的元素。
问所有 $M^{K}$ 种操作过程得到的 $\sum{A'_i}$ 的**总和**。
## 解法1
**计数**
假设在过程中我们不删除第 X 小的元素，而是先暂时保留，我们在所有操作完成得到 N+K 个元素后：
* 保留前 X-1 小的元素；
* 保留后 N-X+1 大的元素。
显然这 N 个元素和中间过程删除的效果是一样的。
那么问题变成了我们考虑有哪些元素能够出现在最终数组中。
根据对称性，解决**前 X-1 小的元素构成的数列和**的总和，和解决**后 N-X+1 大的元素的数列和**的总和，过程应该是等价的，那么我们只需要解决两次相同的问题即可。
现在考虑枚举第 X 大的元素为 v。
假设原数组中小于 v 的元素个数为 a，等于 v 的元素个数为 b，则：
* 过程中生成的小于 v 的元素个数 $i <= x-1-a$;
* 过程中生成的大于 v 的元素个数 $j <= k+a+b-x$。
我们不妨枚举 $i$ 从 $0$ 到 $x-1-a$，则大于 v 的元素的取值方案是 $C_i = \sum_{0<=j<=k+a+b-x}{\binom{k-i}{j} * (m-v)^j}$，若这个 随着 $i$ 变化的 $C_i$ 可以 $O(k)$ 的时间预处理出来（事实上由于 $\sum$ 上界是固定的 k+a+b-x，所以确实是可以做到的），则：
* 可以计算出小于 v 的数落在前 x-1 小的贡献是 $w1_i = \binom{k}{i} * C_i * f_{v-1,i}$，其中 $f_{v-1,i} = (v-1)^{i-1} * v * (v-1) / 2$ 表示 $i$ 个元素取值 $1$ 到 $v-1$ 时对答案的贡献；
* 可以计算出恰好是 v 的数对落在前 x-1 小的贡献是 $w2_i = \binom{k}{i} * C_i * v * (x-1-i)$；
* 第 X 小的元素恰好是 v 的时候的贡献是 $\sum{(w1_i+w2_i)}$。
枚举 v 是 $O(M)$ 的，枚举 i 是 $O(K)$ 的，总的复杂度是 $O(M * K)$ 的。
## 解法2
**期望dp**
[官方题解](https://atcoder.jp/contests/arc139/editorial/3860)似乎给出了基于期望的更简单的解答。