The 2024 ICPC Asia Chengdu Regional Contest (The 3rd Universal Cup. Stage 15: Chengdu)

• The 2024 ICPC Asia Chengdu Regional Contest
• The 3rd Universal Cup. Stage 15: Chengdu

Link

#	Problem	Coding Status	Document Status
A	Arrow a Row	Planned	Unavailable
B	Athlete Welcome Ceremony	Accepted	Finished
C	Chinese Chess	Planned	Unavailable
D	Closest Derangement	Planned	Unavailable
E	Disrupting Communications	Accepted	Finished
F	Double 11	Accepted	Planned
G	Expanding Array	Accepted	Planned
H	Friendship is Magic	Planned	Unavailable
I	Good Partitions	Accepted	Planned
J	Grand Prix of Ballance	Planned	Unavailable
K	Magical Set	Accepted	Planned
L	Recover Statistics	Accepted	Planned
M	Two Convex Holes	Planned	Unavailable

B. Athlete Welcome Ceremony

给定一个长度为 $n$ 的字符串 $S$（由 $\texttt{a},\texttt{b},\texttt{c},\texttt{?}$ 组成）。有 $q$ 次询问，每次询问给出 $x,y,z$，要求用不超过 $x$ 个 $\texttt{a}$，$y$ 个 $\texttt{b}$ 以及 $z$ 个 $\texttt{c}$ 替换 $S$ 中的 $\texttt{?}$，使得字符串中相邻两个字符不同。求方案数，答案对 $10^9+7$ 取模。

$1\leq n\leq 300,1\leq q\leq 10^5$。

Difficulty：Easy (traditional dp, 3-dimensional prefix sum).

dp，设 $f(i,x,y)$ 表示对于字符串的前缀 $S[1,i]$，填入了 $x$ 个 $\texttt{a}$，$y$ 个 $\texttt{b}$，剩余的 $\texttt{?}$ 全替换为 $\texttt{z}$ 且相邻字符不同的方案数。转移就是枚举下一个字符填什么，比较平凡，时间复杂度 $O(n^3)$。然后我们要求的就是：

$$\sum_{i\leq x,j\leq y,C-i-j\leq z} f(n,i,j)$$

其中 $C$ 表示 字符串中 $\texttt{?}$ 的个数。这是一个三维前缀和的形式，模拟一遍三量容斥即可，这样查询就可以 $O(1)$ 了。

时间复杂度 $O(n^3)$，Submission。

E. Disrupting Communications

给定一个 $n$ 个点的树，有 $q$ 次询问，每次询问给出一个路径 $(u,v)$，你需要求出有多少个与 $(u,v)$ 有交的连通块。答案对 $998,244,353$ 取模。

$1\leq n,q\leq 10^5$。

Difficulty：Medium (tree dp).

我们不妨先钦定树以 $1$ 为根，并且 $u=1$，此时如果一个连通块与 $v$ 有交，那么它的根节点一定在路径 $(u,v)$ 上，这是毫无疑问的。那么设 $f(u)$ 表示以 $u$ 为根的连通块数量，转移是非常平凡的。那么回答询问时只需要做一遍链求和即可。

但是注意到 $u=1$ 不一定成立，所以我们可以换根 dp，然后将询问离线，挂到路径的任一端点上即可。注意换根时可能需要除以没有逆元的数（$0$），这也是一个常见 trick，只需要用一个结构体记录一下有多少个零因子即可。

时间复杂度 $O(n\log^2 n)$，Submission。

F. Double 11

有一个长度为 $n$ 的序列 $s$，你需要将其分成 $m$ 个部分，令 $s_i$ 归属部分 $c_i$，你需要为每一部分指定一个实系数 $k_i$ 满足：

• $\sum\limits_{i=1}^{n} k_{c_i} s_i\leq 1$。
• 最小化 $\sqrt{\sum\limits_{i=1}^{n} \frac{1}{k_{c_i}}}$。

输出这个最小值即可。

$1\leq n,m\leq 2\times 10^5,1\leq s_i\leq 10^5$。

Difficulty：Medium-Hard (dp, wqs binary search, decision monotonicity optimization methods, inequality)

先假定我们固定了序列的划分方案，专注于如何选择合适的 $k$，。