Contest Info

practice link

Solutions

A. Valeriy and Deque

题目大意：给你一个长度为 \(n\le10^{5}\) 的 deque，每次操作 pop 开头的两个元素，把较大的放回队首，较小的放回队尾，问第 \(m\le10^{18}\) 次操作时 pop 了哪两个数。

题解：有点意思。

注意到如果最大值在开头，那么它就永远都不会动了，后面相当于 \(2\sim n\) 一直循环。暴力模拟 \(\mathcal{O}(n)\) 次即可。

B. Tolik and His Uncle

题目大意：你在一个 \(n\times m\) 的网格上，从 \((1,1)\) 开始走，遍历每个格子各一次，但是要求每次走的位移向量要两两不同。

题解：每次先跳到关于当前点中心对称的点，然后再跳回当前点的下一个点即可。如果到了行尾就跳到上一行。

C. Serge and Dining Room

签到题。

D. Fedor Runs for President

题目大意：给你一棵树，让你选两个点连一条边，使得简单路径的数量最多。

题解：\(u,v\) 连一条边之后，增加的简单路径数量相当于：\(\frac{n(n-1)}{2}-u,v\) 路径上的每条边断开后，\(u,v\) 路径上的每个点的 \(\frac{sz(sz-1)}{2}\) 之和。所以相当于我们要让后面一项尽可能小。由于 \(\sum sz=n\) 是定值，我们相当于要最小化 \(\sum sz^{2}\)。当然还可以注意到 \(u,v\) 一定都是叶子，否则不会最优。

枚举每个点作为 LCA，显然每个子树只有一个叶子是最优的，然后就能得到一个形如 \((n-sz_{1}-sz_{2})^{2}+ans_{1}^{2}+ans_{2}^{2}\) 的最优化问题。那么容易观察到这可以用斜率优化解决，将 \(sz\) 排序后即可用单调栈解决。

E. Alesya and Discrete Math

题目大意：有 \(n\le10^{3}\) 个函数，每个函数定义域为 \([0,10^{18}]\cap \mathbb{Z}\)，且满足 \(f_{i}(x+1)=f_{i}(x)\) 或 \(f_{i}(x+1)=f_{i}(x)+1\)，\(f_{i}(0)=0,f_{i}(10^{18})=L\)。\(L\) 是 \(n\) 的倍数。你可以询问至多 \(2\times10^{5}\) 次某个函数某个位置的值。你需要对每个函数求出一个区间 \([l_{i},r_{i}]\)，满足 \(f_{i}(r_{i})- f_{i}(l_{i})\ge\frac{L}{n}\)，并且任意两个区间至多交于 \(1\) 点。

题解：考虑分治。不妨设 \(n\) 为偶数，我们希望找到一个位置 \(P\)，使得该位置第 \(\frac{n}{2}\) 小的 \(f_{i}(P)=\frac{L}{2}\)，之后我们就可以将问题分为 \([0,P]\) 和 \([P,10^{18}]\) 解决了。

找到这个位置，很容易联想到随机快排。我们随机选择一个函数，二分找到它的某个取值 \(\frac{L}{2}\) 的位置 \(P'\)，然后把所有函数在该位置的值求出。如果第 \(\frac{n}{2}\) 小的 \(f_{i}(P')<\frac{L}{2}\)，那我们需要向右移动 \(P'\)，注意到所有 \(\ge\frac{L}{2}\) 的函数在右移后仍一定 \(\ge\frac{L}{2}\)，因此我们不需要再询问它们。这样期望的复杂度是 \(\mathcal{O}(n+60\log n)\)。

总复杂度为 \(\mathcal{O}(n(\log n+60))\)（需要一定的计算）。