2021牛客暑期多校训练营1

队友跑路，痛苦单打。

AC Codes

A. Alice and Bob

Alice和Bob从两堆石子（石子数分别为 $n,m$ ）中取石子，Alice先手选择一堆，从中取 $k(k>0)$ 个；Bob后手只能选择另一堆，从中取 $sk(s\geq 0)$ 个，谁不能取就输了。询问谁必胜？

$T(T\leq 10^4)$ 组询问，$n,m\leq 5000$ 。

注意到Bob的必胜态很少，大力出奇迹，直接sg打表+剪枝。

B. Ball Dropping

球和等腰梯形相切的模型。

相似三角形推一下公式。

D. Determine the Photo Position

签到。

E. Escape along Water Pipe

显然是个模拟，所以我写不动了。

不论管子长什么样，我们从某一个单元格走出只有 $4$ 种情况，因此只需要存 $4nm$ 种状态，直接暴搜所有情况。

F. Find 3-friendly Integers

$T$ 组询问，每次询问区间 $[L,R]$ 中的3-friendly数字数量，3-friendly数字指的是：该数字中存在一段连续子串为3的倍数。

$T\leq 10^4,L\leq R\leq 10^{18}$ 。

数位dp硬草过去，不过这样不够优秀。实际上 $n\geq 100$ 时由于抽屉原理必定是3-friendly数，因此暴力一下就行。

G. Game of Swapping Numbers

给定数列大小为 $N$ 的数列 $A,B$，需要恰好交换 $K$ 次数列 $A$ 中任意两个不同的数，最大化 $\sum_{i=1}^N |A_i-B_i|$ 。

$N\leq 5\times 10^5;K\leq 10^8;|A_i|,|B_i|\leq 10^8$ 。

先不考虑 $K$ 次的限制，那么最大值就是：$A,B$ 这两个数列中较大的 $n$ 个数减去较小的 $n$ 个数，这步转化有点像ARC120 D – Bracket Score 2，因此并不难以想到。然后再考虑加上 $K$ 次限制，如果我们将 $A,B$ 这两个数列中较大的 $n$ 个数染成黑色，较小的 $n$ 个数染成白色，那么一黑一白的 $(A_i,B_i)$ 对就不需要变换了，只需要交换二黑或者二白的 $(A_i,B_i)$ 对。

然后考虑：我们应该优先交换哪些同色的 $(A_i,B_i)$ 对？如果我们恰好需要交换这样四个数 $A_i,A_j,B_i,B_j$ ，同时假设 $A_i,B_i>A_j,B_j$ ，不难计算出进行了一步交换后，$\sum_{i=1}^N |A_i-B_i|$ 的变化是 $2\min(A_i,B_i)-2\max(A_j,B_j)$ 。因此我们需要做的就是最大化 $2\min(A_i,B_i)-2\max(A_j,B_j)$ ，由于 $i,j$ 下标分离，因此只需要对 $\min(A_i,B_i)$ 和 $\max(A_i,B_i)$ 分别排序并贪心匹配。

虽然题目中要求我们恰好 $K$ 次变换，但是实际上可以直接转化为至多 $K$ 次变换：因为如果变换到最优解的最少步数小于 $K$ ，那么我们可以选择两个无关紧要的位置交换（两个同色的位置），就可以浪费一步了。注意这对于 $N>2$ 的所有情况均成立，但是需要特判 $N=2$ 。

H. Hash Function

给定一个大小为 $N$ 的数组 $A$ ，找一个最小的随机种子 $x$ 使得 $A_i\pmod{x}$ 互不相同。

$N\leq 5\times 10^5, A_i\leq 5\times 10^5$ 。

$A_i \pmod{x} \neq A_j\pmod{x}$ 的充要条件是 $|A_i-A_j| \neq 0\pmod{x}$ ，也就是说，对于所有的 $|A_i-A_j|$ 而言，$x$ 不能成为他们的因子。

如果已知所有的 $|A_i-A_j|$ ，求这样的 $x$ 可以在 $O(N\log N)$ 的时间复杂度下筛出，因此我们需要做的就是求出所有的 $|A_i-A_j|$ 。由于 $A_i\leq 5\times 10^5$ ，所以直接开一个 $500001$ 大小的桶，然后通过减法卷积求解。如果不知道减法卷积，请参考多项式的各种操作。

I. Increasing Subsequence

给定一个大小为 $N$ 的排列 $P$ ，Alice和Bob轮流取数，并且两人各自满足它后一轮取的数一定在前一轮取的数右边（比如Alice前一轮取了 $P_i$ ，后一轮取了 $P_j$ ，那么 $j>i$ ，该条件对Bob也单独成立），两人同时满足后一轮取的数一定比前一轮取的数大（比如某一轮中Alice取了 $P_i$ ，那么Bob下一轮取的数必须 $>P_i$ ）。

有多个合法的取数情况时，所有合法的数被选中的概率相等，询问取数的期望轮数。

$N\leq 5000$ 。

反正比赛的时候没看懂，看了直播才听懂题意。

K. Knowledge Test about Match

给定大小为 $N$ 的数组 $A=[0,1,2,\ldots,N-1]$ 和数组 $B$ 。重排数组 $B$ 使得 $\sum_{i=0}^{N-1}\sqrt{|A_i-B_i|}$ 尽可能小。要求你给出的排列与最优解的平均误差不超过 $4\%$ 。

$T(100\leq T\leq 500)$ 组询问，$N\leq 1000,\sum N \leq 4\times 10^4$ 。数据随机。

首先，这个问题显然可以看作完全二分图的最小权匹配，如果不考虑数据范围可以直接KM。

但是由于时限仅为1s，所以全部KM肯定不行，因此考虑：小范围KM，大范围贪心。提交了几十发才AC了本题，截断点是 $N=50$ 。贪心的正确性纯脑补，我采用了一个冒泡排序的贪心策略，但并不能解释为什么是对的。