2021牛客暑期多校训练营1

Comment:

• O for passing during the contest
• Ø for passing after the contest
• ! for attempted but failed
• · for having not attempted yet

A Alice and Bob

有两对石子 n,m ，每次选其中一堆，取 k<=n,m 个石子，在另一堆取 s*k 个石子（s >= 0）。问先手胜还是后手胜。

n,m <= 5000 。

博弈问题可以从求取 sg 值，利用 sg 定理解决；对于单个问题也可以从已确认的必败态转移到能到达的必胜态来确定所有状态。正确性是显然的。复杂度如果不对，则打表，看 必败状态个数 or 必胜 / 必败状态是否存在规律。

那么这道题令 \(f_{i,j}\) 为两堆石子剩余 i,j 时的胜负态。从必败态转移到必胜态，即假设 \(f_{i,j} = 0\) ，转移到 \(f_{i+k,j+s*k} = 1\) 上，看似复杂度为 \(O(n^3\log n)\) （存在一个调和级数求和）。打表发现，令 \(f_{i,j} = 0\) 的 j 仅存在唯一解，复杂度降至 \(O(n^2\log n)\) 可以通过。

B Ball Dropping

简单计算几何题目。

D Determine the Photo Position

水题。

E Escape along Water Pipe

状态设计很重要。

记 \(f_{i,j,k}\) 为处在 i,j ，从 k 方向转移而来的。如图所示：

同时令

const vector<pii> move = {{0,1},{-1,0},{0,-1},{1,0}};//右下左上

会方便访问进出的方向。

证明：

对于一个方向 d ，当 d ^ 2 是往 d 的反方向，而 d ^ 1 or d ^ 3 则是往 d 的左右侧方向。由于 ^ 1 或者 ^ 3 时值变化奇数，而 ^ 2 值变化偶数，证毕。

还可以写多个函数，通过两个 d 的方向确定图形的编号。方便性显然。

get(pair<>(d1,d2)){
    return pattern.id;
}

确定好编号，只需要 (cur – ori) * 90 方便得到旋转角度。

F Find 3-friendly Integers

在数位 dp 时，先去考虑有多位时，要满足约束的条件会不会很严格。这道题当位数 >=3 时，都满足 3友好 。正确性显然。

G Game of Swapping Numbers

对于 \(|A_i – B_i|\) 的形式，可以视作一维数轴上的两个点 \(A_i(B_i)\) 所构成的线段长。正确性显然。

那么首先，对于 \(|A_i-B_i|,|A_j-B_j|\) ，考虑什么时候会使答案增加：分几种情况讨论，发现当 (A_i < B_i) * (A_j < B_j) > 0 时，交换 A_i,A_j 都不会使答案更劣；且当两线段不交时，交换后则会增加值的大小。

增加多少？ \(\min(A_j,B_j) – \max(A_i,B_i)\) ，假定 j 线段在 i 线段右侧。 那么则考虑优先选最大的 \(\min(A_j,B_j)\) ，和最小的 \(\max(A_i,B_i)\) 交换，一定是当前可交换最优的一个（可以用反证法证明）。

这道题恰好交换 K 次，似乎有点棘手。

不如从小数据出发，当 n=2 ，交换 K 次应该是答案唯一的，仔细想想确实如此。而当 n>2 时，由于上面观察到的性质： (A_i < B_i) * (A_j < B_j) > 0 时交换不会更劣，根据鸽巢原理，至少存在一对同号的 A_i 满足。那么不断交换这对 i,j 做无用功即可。

H Hash Function

给定 n 个数，要求一个最小的模数 p ，使得 \(a_i \neq a_j(\bmod p)\) 。

条件是什么？ \(a_i\neq a_j(\bmod p)\) ；未知量是什么？最小的模数 p 。

如何满足这个条件？将条件变换一下：\(a_i-a_j\neq0(\bmod p)\) ，即 \(a_i-a_j\neq kp,k\geq0\) 。

得到这个就很显然了，对 {a_i} 进行减法卷积，要求一个模数 p 的倍数不能等于 \(a_i-a_j\) 。那么从小枚举 p ，然后枚举 k 判断 p 是否合法即可。正确性显然。

复杂度 \(O(n\log n)\) 。

I Increasing Subsequence

令 \(f_{i,j}\) 为 A 走到 i ，B 走到 j 时，走到不能走的期望步数。由于 A，B 只能向前走，所以状态满足无后效性，可以尝试做下去。

那么未知量即为 \(f_{0,0}\) 。

仔细分析，可以根据当前 A，B 的 i,j 位置判断这个状态应该是 A 走还是 B 走（分类讨论即证得）。假设 i 走， i 可以走到 [i+1,n] 比 p_j 大的所有位置。

证明：对于 j ，必然上一步是比 i 小的（需要满足条件），所以走到了 p_j > p_i 的 j 位置上，也代表了 [i+1,n] 中其他 > p_i 的位置没走过；由于 i 不能往回走，所以只能从 i+1 开始选择。所以 i 可以走到 [i+1,n] 比 p_j 大的所有位置。

发现从 \(f_{0,0}\) 开始刷表 dp 复杂度很高（要更新后面 On 种状态值），那么就考虑倒过来更新。复杂度的正确性是显然的，由于对于 \(f_{i,j}\) ，要是能快速统计能到达 i,j 的状态来更新 \(f_{i,j}\) ，就可以 \(O(1)\) 更新了。

具体来说，当 \(p_i > p_j\) 时，将统计好的 \(f_{i,j+k} ,p_{i+k}>p_i\) 的 f 和满足这个条件的 f 的个数加给 \(f_{i,j}\) 。那么只需要倒着 dp 时统计这两个值即可。

K Knowledge Test about Match

给定 \(a=\{0,1,2, \ldots, n-2, n-1\}, b=\left\{b_{0}, b_{1}, b_{2}, \ldots, b_{n-2}, b_{n-1}\right\}\) ，要求 \(f(a, b)=\sum_{i=0}^{n-1} \sqrt{\left|a_{i}-b_{i}\right|}\) 最小化，仅要求与最小化的值差别不超过 4% 。T = 500，n <= 1000 ,\sum n <= 1e4 。

匹配问题， KM or 费用流都是最优解，只不过复杂度不通过。

如果按照当 \(f\{a_i,b_i\} > f\{a_i,b_j\}\) 进行 b_i 的交换的话，得到的结果不一定最优。

考虑 a = {1,3}，b = {3,4} ，按上面应该 <1,3>,❤️,4> ，而实际上 <1,4>,❤️,3> 会更优。这里感性证明，由于估价函数是上凸函数，自变量增大，应变量增大的量没有期望中的那么大。

这里由于允许 \(O(n^2)\) 的复杂度算法，对于冒泡排序能够充分交换两个元素，所以冒泡排序几次，就能在误差 1% 以内。挺神奇。

function<double(int, int)> ck = [&](int x, int y) {
    return sqrt(abs(x - y));
};
for (int k = 1; k <= 4; k++)
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            if (ck(a[i], i - 1) + ck(a[j], j - 1) > ck(a[j], i - 1) + ck(a[i], j - 1))
                swap(a[i], a[j]);