CCPC 2024 哈尔滨区域赛（Harbin Regional）部分题解

注意

题解写得可能非常抽象。

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

A. Build a Computer

题意

给定 $L,R$ ，构造一个点数 $\leq 100$ 的 DAG，恰有一个点入度为 $0$ （起点），一个点出度为 $0$ （终点），每条边有字符 $0$ 或 $1$ ，满足：所有数值为 $[L,R]$ 的二进制数都恰好对应一条从起点到终点的路径（把字符相接后得到这个二进制数）。 $L,R\leq 10^9$

题解

先根据二进制表示的长度分段。给一对长度相等的 01 串 $l,r$ 建一个点，然后考虑最高位是否可能是 $0$ 和 $1$ ，连出去一条或者两条边，递归处理，带记忆化。正确性大概可以联想数位 DP 的状态数量。

B. Concave Hull

题意

给定 $n$ 个点，求一个凹多边形，使其面积最大。 $n \leq 10^5$ 。

题解

首先，答案一定是全集的凸包从一条边往里面凹进去。先求凸包，考虑每条边凹进去凹到哪个点最好，发现是在用这条边所在直线切内部的点集。从而在内部点集也求一个凸包，然后在外凸包上枚举边，内凸包上跟着旋转卡壳，找到离这条边最近的点。

C. Giving Directions in Harbin

签到题。

D. A Simple String Problem

题意

给定一个 $2 times n$ 的矩阵，每个格子有一个字符。你要找一条路径，起点终点任意，每一步向右或者向下，要求经过格子的字符串起来是某个串重复两次。求这样的路径的最大长度。 $n\leq 2\times 10^5$ 。

题解

先建出 SA。首先考虑只有一行的做法：枚举 $i$ ，考虑答案是 $2i$ 的情况，每 $i$ 个取一个关键格子。这样，每个合法的路径都包含恰好两个关键格子，且对应重复两次出现的位置。枚举一对相邻的关键格子，然后从这个位置开始向前、向后求 LCP，如果 LCP 能够接上，就能达成 $2i$ 的答案。

现在考虑有两行的情况。同样枚举 $i$ ，每行每 $i$ 个取一个关键格子（在第二行，关键格子比第一行靠前一格）。先假设下到第二行的时刻在后半段（可以将整个网格旋转 180 度求另一种情况），根据下到第二行时刻在两个关键格子之间还是之外可以分为两种情况，两种情况均可通过多个 LCP 求出是否能接上。

（队友写的，细节不懂）

E. Marble Race

题意

数轴上有 $n$ 个起点， $m$ 个球每个球独立均匀随机地选择一个起点，然后按照各自的速度向右移动。考察所有球的位置的中位数，恰好到达 $0$ 的时刻，求其期望。 $n,m\leq 500$ 。 $m$ 是奇数。起点 $<0$ ，速度 $>0$ 。

考虑第 $i$ 个球以 $j$ 为起点且通过 $0$ 时是中位数的概率，即通过 $0$ 时有 $floor(m/2)$ 个球在它右边的概率。这个概率可以 $O(m^2)$ 求出（可以当成一个 $m$ 个一次多项式相乘得到一个生成函数）。但是 $O(nm \cdot m^2)$ 无法通过。考虑将 $i,j$ 按照「第 $i$ 个球以 $j$ 为起点通过 $0$ 的时间」排序，依次求对应答案。注意到相邻两个生成函数只差了一个一次多项式，可以 $O(m)$ 除以这个多项式，再 $O(m)$ 乘上另一个多项式，从而 $O(m)$ 更新答案。复杂度 $O(nm^2)$ 。

F. 1D Galaxy

题意

数轴上有若干星球，各自有坐标和质量（质量可能为负）。每个时刻，每个星球会按照「如果左侧星球的质量之和大于右侧星球的质量之和，向左移动一格；右侧质量大则向右移动一格；相等则不动」的规则移动。多次询问某个星球在某个时刻的位置。 $n,q\leq 10^5$ 。

题解

首先两个星球到达同一坐标，可以合并。星球会产生若干段，每段会往内坍缩（或者向无穷远移动），每段的状态可能是：

核心没有星球，两侧往中间合并
核心有一个不动的星球，两侧往中间合并
核心有两个星球，位置交错，两侧往中间合并
全都向一个方向移动到无穷远在两侧到达中间时，状态可能变化；否则，每个星球都以固定速度移动（或者轮流在两个位置），可以直接算出坐标。用数据结构维护两侧到达中间的时刻。

（口胡的，没写）

G. Welcome to Join the Online Meeting!

题意

给定一个无向图，有的点是特殊点。找一个生成树，外向定向，特殊点必须是叶子。 $n\leq 2\times 10^5$ 。

题解

其基本等价于找一个生成树，特殊点度数为 $1$ 。令连接两个特殊点的边边权为 $\infty$ ，连接一个特殊点和一个非特殊点的边边权为 $1$ ，连接两个非特殊点的边边权为 $0$ 。求最小生成树即可，得到的即为尽可能满足条件的生成树。

H. Subsequence Counting

好像是类欧，不会。

I. A Brand New Geometric Problem

题意

给定一个可重集 $A$ ，给定 $S,M$ ；尽量少地对 $A$ 进行删去一个元素/添加一个元素的操作，使得 $A$ 的元素之和为 $S$ ，元素之积为 $M$ 。 $S,M\leq 10^{10}$

题解

好像官方题解要小质数 DP，大质数暴搜。但其实暴搜过了。

先 $M$ 每个约数求出其约数。搜索 $M$ 的（非 $1$ 的约数）拆法，要求新添加的数单调不增。考虑如何统计答案：以「把 $A$ 中的非 $1$ 项先全清空」为基础；记录每个约数的出现次数，与 $A$ 中这个数的出现次数作比较；如果当前这个数出现次数不小于 $A$ 中的出现次数，再加一个这个数，答案就会加一，否则减一；最后再加上 $1$ 对应的代价。考虑下标通过分 $\geq \sqrt{M}$ 和 $<\sqrt{M}$ 两种，可以实现简单的以 $M$ 约数为下标的 $O(1)$ map 状物。