The 3rd Universal Cup. Stage 1: St. Petersburg（暨 2024 LIX SPbSU Championship）部分题解

注意

题解写得可能非常抽象。

「如果一个题解你看不懂，那是题解垃圾而不是你垃圾。」

比赛链接：UCup

A. Element-Wise Comparison

题意

给定序列 $a$，正整数 $m$，统计有多少 $i<j$ 满足：$a_i<a_j,a_{i+1}<a_{j+1},\cdots ,a_{i+m-1}<a_{j+m-1}$。$5\times 10^4$，0.4s。

题解

bitset。先对于每个 $i$，统计有哪些下标 $j$ 满足 $j<i,a_j<a_i$，得到 $n$ 个 bitset。然后变换为统计有哪些下标差满足 $a_{i-j}<a_i$。答案为连续 $m$ 个 bitset 的按位与的 popcount 之和。

为了求出所有「连续 $m$ 个 bitset 的按位与」，可以每 $m$ 个 bitset 选一个 pivot，这样每个 bitset 段都会恰好包含一个 pivot。求 pivot 开始往前、往后一段各自的按位与，前缀后缀合并得到各个长为 $m$ 的段的按位与。

总复杂度 $O(n^2/w)$。

C. Cherry Picking

题意

某人参加了 $n$ 场比赛，第 $i$ 场比赛对手 rating 为 $a_i$，结果为 $b_i$（胜/负）。给定 $k$，求最大的 $x$，满足去掉所有 $a$ 小于 $x$ 想比赛后，剩下的比赛中，可以找到一段 $k$ 连胜。$n\leq 10^5$。

题解

从小到大扫 $x$，不断删除比赛。对每场比赛，用并查集维护其所在的连胜段、并在根记录连胜段的长度（对于胜场）；用双向链表维护前/后的连胜段或负场（对于负场）。同时维护段长的 multiset。于是可知每个 $x$ 对应的最大连胜段长度。

D. Dwarfs' Bedtime

题意

交互题。有 $n$ 个人（互相独立，下面只考虑一个）。每个人从一天的某一分钟开始睡觉，睡恰好 12 小时。你从 00:00 开始，每分钟可以去看这个人是否在睡着状态，直到当天 23:59 结束。在 $50$ 次询问内求出这个人开始睡觉的时间；你的每次询问要求时间单调。

题解

现在 00:00 询问一次，可以把睡眠开始时间分为两种情况：00:01~12:00 和 12:01~23:59+00:00。二者做法基本一致，以第一种为例：先等到 00:48，询问，由此可知睡觉时间是否在 00:01~00:48；若否，再等 47 分钟、46 分钟……直到确定睡觉时间在 p 到 q 内，则从 p+12h 开始每分钟询问，直到确定睡觉时间。

E. Fake Coin and Lying Scales

题意

有一个天平和 $N$ 个硬币，其中有一个假币，重量比真币轻。每次可以将一些硬币放在天平上，称重。你有 $n$ 次称量机会，天平会撒谎不超过 $k$ 次，最后有 $3k+1$ 次猜测机会。求最大的 $N$，使得你保证能够猜中，取对数并且绝对误差在 $10$ 以内即通过。$n,k\leq 10^9$。

题解

（队友做的，没有过掉）

估计答案差不多是

$$\frac{3^n}{\sum_{i=0}^k \binom{n}{i} 2^i / (3k+1)}$$

$\sum_{i=0}^k \binom{n}{i} 2^i$ 用最大的一项估计差不多。好像还有一些细节。

G. Unusual Case

题意

给定一张 $n=10^4,m=2\times 10^5$ 的随机生成的无向图，找出其中 $k=8$ 个不使用重复边的哈密顿路径。

题解

有论文 告诉我们，这个边数级别的随机图可以 $O(n)$ 找到哈密顿路径。然后用论文做法一条一条找即可，找不到就从头开始。

找一条的做法如下：随机选择一个起点开始，贪心地往前随机找一个未访问的点。如果找不到，假设路径现在长成 $1\to \cdots \to j \to \cdots \to i \dashrightarrow j$，尝试找到 $j-1$ 出发连向 $k(j<k<i)$ 的边，把路径变成 $1 \to \cdots \to j-1 \to k \to \cdots \to i \to j \to \cdots \to k-1$。找不到就重来。

J. First Billion

题意

给定一个长为 $N=2n$ 的序列，其构造方式为：随机选 $n$ 个数，其和为 $10^9$；再随机选 $n$ 个数，其和为 $10^9$；将两个序列合并打乱。其中随机指从所有和为 $10^9$ 的集合中均匀随机。求整个序列的任意一个和为 $10^9$ 的子集。$N\leq 100$。

题解

被智商锁了。

将序列分为两半，前一半随机选取子集，选 $10^6$ 个；后一半同理；尝试用前一半的子集和后一半的子集合并。感性理解，其从 $2\times 10^9$ 里面随机选了 $10^{12}$ 个数，大概率包含 $10^9$。

K. Tasks and Bugs

签到小模拟，Python 秒了。

N. (Un)labeled graphs

题意

通信题（Run-twice）。

编码时，输入 $n_1,n_2=n_1+\lceil\log_2 n_1\rceil+3$，输入一个 $n_1$ 个点的图 $G$，你要输出一个 $n_2$ 个点的图 $H$。

交互库会将 $H$ 的点的编号打乱为 $H'$。

解码时，输入 $n_2,n_1$，输入一个 $n_2$ 个点的图 $H'$，你要还原出 $n_1$ 个点的图 $G$。

图均为无向简单图。

$n\leq 2024$

题解

考虑 $H$ 的构造：

• 首先保留 $G$ 作为子图。将点从 $0$ 开始编号。
• 取 $\lceil\log_2 n_1\rceil$ 个点，记作 $u_0, \cdots u_k$。将它们串成一条链。
• 剩下三个点记作 $v_1,v_2,v_3$。
• $v_1$ 向除了 $v_2,v_3$ 的所有点连边。
• $v_2$ 向 $0$ 和 $u_0$ 连边。
• $v_3$ 向 $0$ 和 $u_0$ 到 $u_k$ 连边。
• $u_i$ 向二进制表示中第 $i$ 位为 $1$ 的点连边；但是不向（$G$ 中）度数为 $0$ 的点连边。

考虑解码：

• 此时可以验证，$G$ 中度数为 $0$ 的点在 $H$ 里度数为 $1$，其他所有点度数均不小于 $3$，唯一一个度数为 $2$ 的点是 $v_2$。先找到 $v_2$。
• 找到所有与 $v_2$ 不相邻的点中度数最大的，这个点是 $v_1$。（如果不排除与 $v_2$ 相邻的点，$u_0$ 的度数可能与 $v_1$ 一样大）
  • 注意到如果 $n_1=2^{k+1}$，那如果 $2^{k+1}-1$ 这个点与 $G$ 中左右其他点相邻，那么 $2^{k+1}-1$ 和 $v_1$ 的度数相同。但这没有影响，因为它们相连的都是同样的点，随便选一个作为 $v_1$ 即可。
• 与 $v_1$ 不相邻的点中，$v_2$ 已经被找到，另一个是 $v_3$。
• 找到所有与 $v_3$ 相邻的点，这些点是 $u_0$ 到 $u_k$ 和 $0$。$0$ 与 $u_0$ 到 $u_k$ 孤立，从而可以判断出谁是 $0$。
• 与 $v_2$ 相邻的点中，不是 $0$ 的那个就是 $u_0$，随后 $u_0$ 到 $u_k$ 的链可以理出来。
• 剩下的点都原本在 $G$ 当中；有的点是孤立点，其编号不重要；有的点与 $u_i$ 相连，由此可以判断原来的编号。