差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:i_dont_know_png:jagiellonianu2020 [2020/07/11 11:34]
nikkukun
+++ 2020-2021:teams:i_dont_know_png:jagiellonianu2020 [2020/07/20 22:21] (当前版本)
nikkukun add C
@@ 行 32: / 行 32: @@
+===== C - Bookface =====
+Upsolved by nikkukun.
+==== 题目描述 ====
+给 $n \leq 2 \times 10^5$ 个数 $x_1, x_2, \ldots, x_n$（$x_i \in [0, 3 \times 10^{11}]$）和一个参数 $d \in [1, 10^6]$，你可以将这个序列的值任意改动为其余非负整数，使得对任意的 $i \neq j$ 都有 $|x_i - x_j| \geq d$，代价为每个数的改变量绝对值之和。
+求最小代价。
+==== 解题思路 ====
+不妨考虑先将 $x$ 数组排序，并在维持相对位置的情况下，使得排序后数组 $x_{i+1} - x_i \geq d$，这样原题的条件便得到满足。
+先转化条件为非降序列：要求 $x_{i+1} - x_i \geq d$，则令 $x'_i = x_i - (i - 1) \cdot d$，就变成了令 $x'_{i+1} \geq x_i'$ 的条件。
+再保证所有数非负：对所有 $x_i' < 0$ 的数，都将其先改为 $0$，并将变化量统计在答案中。此时显然转化回 $x_i$ 的数组既非负，又满足了条件。同时，在 $x_i'$ 中由于所有数也非负，为了用最小代价将 $x_i'$ 变为非降，不会把某些 $x_i'$ 重新调回负数，这并不优。
+于是，现在问题变成让 $x'$ 数组非降，而这是经典 $L_1$ 问题，参考 [[.:nikkukun:isotonic_regression#l_1_问题 | 保序回归问题]]。
+===== E - Contamination =====
+Solved by Potassium.
+==== 题目描述 ====
+$n$ 个互相无交点的圆是原子弹伤害范围，有 $q$ 次查询，每次查两个位于 $x_1$ 和 $x_2$ 坐标，且 $y$ 坐标可以任意游走于 $[ymin,ymax]$ 的动物能否相遇。
+==== 解题思路 ====
+有显然结论：如果两动物不能相遇，一定有一个圆跨过 $[ymin,ymax]$ 且位于两点之间。于是将圆和动物都放在 $ymin$ ，从小到大枚举，遇到动物就查询中间能够到达的最大 $y$ 值，如果超过 $ymax$ 则无法到达；遇到圆就更新 $c_x$ 处的值为 $c_y+r$。
+===== F - The Halfwitters =====
+Upsolved by qxforever.
+==== 题目描述 ====
+给一个长度 $n$ 的排列，三种操作（交换相邻数字，反转序列，随机排列序列）分别对应花费为 $a$ , $b$ , $c$ ，要还原成元排列（$p_i=i$），问期望花费。对每组 $(n,a,b,c)$ 要回答 $d$ 次询问。 $n\le16$，$\sum d\le10^5$
+==== 解题思路 ====
+当不考虑第三种操作时，每个排列的花费是一定的，且只和这个排列的逆序对数 $inv$ 有关，为 $\min(inv\times a,(n(n-1)/2-inv)\times b )$。通过一个 $O(n^32^n)$  的 DP  预处理出长度为 $n$ 的排列中逆序对为 $inv$ 的方案数，记为 $num_{inv}$ 。
+现在考虑第三种操作，若当前排列对应的花费较高，我们应该考虑随机这个排列直到它的花费满足要求。因此首先将 $(cost_i,num_i)$ 按照第一维排序。设随机排列花费的期望为 $E$，则有
+$$
+E\times n!=(E+c)\times \sum_{i>j}num_i + \sum_{i\le j} num_i\times cost_i
+$$
+式子的含义是，若当前排列的花费大于 $cost_j$ 进行随机，否则取当前排列的花费为最终花费。 $E$ 的值与 $j$ 有关，遍历 $j$ 维护 $E$ 的最小值即可。
+问题的答案为 $\min(cost_{inv},E+c)$ 。
+===== G - Invited Speakers =====
+Solved by Potassium.
+==== 题目描述 ====
+签到构造题，跳了
+==== 解题思路 ====
+===== H - Lighthouses =====
+Solved by Potassium.
+==== 题目描述 ====
+给一个凸多边形以及一些顶点间的路，求最长不重复经过点的路径。
+==== 解题思路 ====
+区间 $dp$，考虑某个区间不能选和终点位置，向外转移即可。
 ===== I - Sum of Palindromes =====
@@ 行 48: / 行 126: @@
 观察发现这样操作每次会减少一半的位数，只要 $O(\log \log n)$ 次操作就能分解完毕。
+===== K - To argue, or not to argue =====
+Upsolved by nikkukun.
+==== 题目描述 ====
+剧场中有 $n \times m$ 个座位，有 $k$ 对双人组前来看剧，组中的两个人应当认为是不同的人。如果双人组相邻地坐着，他们会因为争吵影响别人看剧。现在已知一些位置不能坐，求让这 $2k$ 个人能好好看剧的方案数模 $10^9 + 7$。
+$n \times m \in [1, 144]$，保证有不少于 $2k$ 个空位置。
+==== 解题思路 ====
+容斥。令 $f(i)$ 表示取 $i$ 对双人组相邻地坐着的方案数，则答案为
+$$
+^k \cdot \left[ \sum _{i=0}^k (-1)^i \cdot \binom ki \cdot i! \cdot f(i) \cdot \binom {\mathrm{res} - 2i}{2k-2i} \cdot \frac {(2k-2i)!}{2^{k-i}} \right]
+$$
+其中 $\mathrm{res}$ 为空位置的个数。
+现在考虑如何求 $f(i)$，不妨假设 $m \leq n$（不满足时转置一下），则相当于在有禁位的棋盘上放 $i$ 个骨牌，可以类似插头 DP 一样用一个二进制保存 $m + 1$ 个位置的跨越状态。
+在某一行上，令 $g(\mathrm{pos},\mathrm{cnt}, \mathrm{sta})$ 表示当前处理到的列为 $\mathrm{pos}$、放置了 $\mathrm{cnt}$ 个骨牌、插头状态为 $\mathrm{sta}$ 的方案数，则处理到最后一行时有 $f(i) = g(m, i, 0)$。注意要用滚动数组，减少空间开销。
+单次时间复杂度 $O(nmk \cdot 2^{\min\{n, m\}})$。

CVBB ACM Team

用户工具

站点工具

差别

页面工具