ICPC 2022 Regional 合肥站游记

今天本来会有一场大物的考试。还好我因为打 ICPC 申请了免考不然就要在大物考场上丢人了。

前 3h 写出来 6 题。最后 2h 我在写一道数学题，SHX 在写一道数据结构题，结果都没有写出来。

本来以为写出来 7-8 题可以混一块金牌的。结果赛后一查排行榜，8 题 42 队，7 题 67 队，结果金牌只有 35 块。

也就是说无论如何都没有大金牌了 /kk

最后 rank 72 拿了一块银牌。

这么说来上周的 CCPC 其实是最有希望拿金牌的。如果我能够少浪费一时间的话。

害群之马竟是我自己 /kk

我写出来的题

A. Welcome to USTC

给定一个字符串 $S$。保证 $S$ 中恰好包含 $\mathtt{U},\mathtt{S},\mathtt{T},\mathtt{C}$ 四个大写英文字母各一个，其他字符均为小写英文字母，且 $\mathtt{USTC}$ 在 $S$ 中作为子序列出现。

每次操作可以交换 $S$ 中的两个相邻字符。现要让 $\mathtt{USTC}$ 在 $S$ 中作为子串出现，试求最小操作次数。

$4\leqslant |S|\leqslant 10^4$。

$\mathtt{1s/256MB}$。

设 $\mathtt{U},\mathtt{S},\mathtt{T},\mathtt{C}$ 的下标依次为 $a,b,c,d$，答案显然为

$$(b-a-1)+2(c-b-1)+(d-c-1)$$

时间复杂度 $O(|S|)$，空间复杂度 $O(|S|)$。

G. Game Plan

您有一个集合 $S$。初始时 $S=\{0\}$。现在您可以进行 $t$ 次操作。在第 $i$ 次操作中，您可以在如下两项中任选其一：

1. $S\leftarrow S\cap\{a_i\}$
2. $S\leftarrow S\cap\{b_i\}$

（原题中还有一个值域上界，不过现在看来这个不重要）

试求 $t$ 次操作后 $\operatorname{mex}(S)$ 的最大值。

$1\leqslant n\leqslant 10^9$，$1\leqslant t\leqslant 10^6$，$1\leqslant a_i,b_i\leqslant n$。其中 $n$ 为值域上界。

$\mathtt{1s/256MB}$。

考虑建图。$n+1$ 个，依次标号为 $1,2,\dots,n+1$。对于每一个 $i$，我们连一条边 $(a_i,b_i)$。

现在问题转化为，在这张图上，对于每条边标记其中一个端，问未被标记过的标号最小的的标号最大是多少。

考虑到，如果一个连通块是一棵树，那么我们不得不放弃其中的一个不标记。那么显然放弃标号最大的是最优策略。

但是在树的基础上，再随便增加一条边，我们都能够做到标记这个连通块中的所有。

以上。时间复杂度 $O(t\log t)$，空间复杂度 $O(t)$。

H. Jackpot

黑板上写有 $n$ 个正整数 $k+1$。每次操作您可以选择一个大于 $1$ 的整数，令其为 $x$，然后它有 $\frac{1}{x-1}$ 的概率变为 $x-1$，$\frac{1}{x-1}$ 的概率变为 $x-2$……$\frac{1}{x-1}$ 的概率变为 $1$。

您的目的是让所有数都变为 $1$。试求期望操作次数。对 $10^9+7$ 取模。

多组数据。$1\leqslant n\leqslant 10^9$，$2\leqslant k\leqslant 10^3$。$T\leqslant 10^3$。

$\mathtt{1s/256MB}$。

容易发现这些数都是两两独立的。令 $E(i)$ 表示将一个数从 $i$ 变到 $1$ 的期望操作次数，可以直接得出答案等于 $n\cdot E(k+1)$。

$E(i)$ 也很容易计算。我们可以进行如下的预处理

$$E(i)=1+\frac{1}{i-1}\sum_{1\leqslant j\lt i}E(j)$$

时间复杂度 $O(k^2+T)$，空间复杂度 $O(k)$。

SHX 写出来的题

B. Genshin Impact

您可以释放一种火魔法。这种火魔法每 $y$ 秒可以释放一次，每次释放有 $\frac{1}{p}$ 的成功率，如果成功，会使得敌人在接下来的 $x$ 秒内进入燃烧状态。如果敌人已经处于燃烧状态，状态的剩余时间会被重置为 $x$ 秒。

现在您会一直不停地对着同一个血量无限的敌人释放这种火魔法。试求当经过的时间趋向于正无穷大时，

$$\frac{\text{ 敌人处于燃烧状态的时间 }}{\text{ 总时间 }}$$

的值（……大概收敛吧）。

多组数据。$1\leqslant x,y,p\leqslant 10^3$。$T\leqslant 10^3$。

Special Judge：相对误差不超过 $10^{-6}$。

$\mathtt{1s/256MB}$。

一看到题面很快啊，我就有了如下的一个看上去很真（大嘘）的想法

$$\frac{1}{p}\frac{\min(x,y)}{y}$$

这个东西显然是不对的。因为如果 $x\gt y$，上一次成功了这一次没有成功那么燃烧状态会持续。

不过算了，反正 SHX 写出来了。

无穷会把我们在有限的世界里积累起来的直觉打得粉碎。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　——関原みや

J. Produce the Problems

给定 $n,a,b$ 和两个长度为 $n$ 的序列 $d,c$。您需要构造 $n$ 个字符串 $S_1,S_2,\dots,S_n$，其中 $S_i$ 需要恰好包含 $d_i$ 个 $\mathtt{D}$ 和 $c_i$ 个 $\mathtt{C}$。并且，如果令 $S=S_1S_2\cdots S_n$，$S$ 中不能出现超过 $a$ 个连续的 $\mathtt{D}$ 或超过 $b$ 个连续的 $\mathtt{C}$。问是否能够做到。

$1\leqslant n\leqslant 10^6$，$0\leqslant a,b,d_i,c_i\leqslant 10^6$。

$\mathtt{1s/256MB}$。

构造题，一生之敌。

不过算了，反正 SHX 写出来了。

构造题是人类思维进步的阶梯。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　——関原みや

M. Mahjong

得。这题我连题意都不知道。只听说是个大模拟。

不过算了，反正 SHX 写出来了。

大模拟题就是 【ACM 粗口 】 题。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　——関原みや

没过的题

E. My friends’ friends are my friends

Warning：以下所用记号与原始题面存在出入。

Warning：以下文字已经经过了一定程度的转化，与原始题面想要表达的含义存在出入。

给定一张 $n$ 个和 $m$ 条边的无向图和一个特殊节点 $r$。点有点权 $a,b$，边有边权 $w$。

现在每个点上都站着一个人。对于一个点 $i$，如果您能够支付给这个点上的人 $a_i\cdot\operatorname{dist}(r,i)$ 元，那么 TA 就会对您产生 $b_i$ 点贡献。其中 $\operatorname{dist}$ 表示两点间的最短路。

现在您需要集齐 $S$ 点贡献，但是您的预算只有 $T$ 元。问是否能够做到。

$1\leqslant n\leqslant 10^4$，$1\leqslant m\leqslant 10^6$，$0\leqslant S\leqslant 10^4$，$0\leqslant T\leqslant 10^{12}$。

$0\leqslant a_i,b_i\leqslant 10^4$，$1\leqslant w_i\leqslant 10^4$。

$\mathtt{1s/256MB}$。

令 $f(i)$ 表示恰好获得 $i$ 点贡献至少需要多少钱。不过 $f(S)$ 比较特殊，它表示至少获得 $S$ 点贡献（即包括了 $S+1$ 点和更多的情况）至少需要多少钱。

那么我们可以写一个 $O(nS)$ 的背包 DP。

结果 T 了（悲

I. Counting Lines

给定 $n$。称平面直角坐标系内横纵坐标均为 $[0,n)$ 上的整数的这 $n^2$ 个点为标记点。一条直线是好的，当且仅当它满足如下两个条件：

1. 经过至少两个标记点
2. 与 $x$ 轴的夹角的绝对值小于等于 $\frac{\pi}{4}$

试求好的直线的数量。

多组数据。$2\leqslant n\leqslant 10^6$。$T\leqslant 10^3$。

$\mathtt{1s/256MB}$。

推了半天结果发现不对（悲

以下是考场思路：

我们把夹角在 $[-\frac{\pi}{4},0)$ 的部分逆时针旋转 $\frac{\pi}{2}$ 到 $[\frac{\pi}{4},\frac{\pi}{2})$，然后再减去夹角为 $0$ 和 $\frac{\pi}{4}$ 的部分（加起来一共是 $3n-3$），发现剩下的部分实际上是

$$\sum_{\Delta x=1}^{n-1}\sum_{\Delta y=1}^{n-1}[\Delta x\perp\Delta y]f(\Delta x,\Delta y)$$

其中 $f(\Delta x,\Delta y)$ 表示斜率为 $\frac{\Delta y}{\Delta x}$ 的好的直线的数量。

套路莫比乌斯反演

$$\begin{aligned} &\sum_{\Delta x=1}^{n-1}\sum_{\Delta y=1}^{n-1}[\Delta x\perp\Delta y]f(\Delta x,\Delta y)\\ =&\sum_{t=1}^{n-1}\mu(t)\sum_{u=1}^{\lfloor(n-1)/t\rfloor}\sum_{v=1}^{\lfloor(n-1)/t\rfloor}f(tu,tv)\\ \end{aligned}$$

然后就是这里。仔细思考我们会发现，$f(\Delta x,\Delta y)$ 与 $(\Delta x,\Delta y)$ 有关，因此不能直接套二者互质时的式子。

然后……然后就不会了（悲

K. Quarantine

现在有排成一条直线的 $n$ 个居民区，依次标号为 $1,2,\dots,n$。

有 $m$ 个时间，每次事件有如下 $4$ 中类型：

1. 给出 $l,r$。区间 $[\max(l-A,1),\min(r+A,n)]$ 内的所有居民区进入「被感染」状态。
2. 给出 $l,r,k$。如果区间 $[\max(l-A,1),\min(r+A,n)]$ 内处于「被感染」状态的最长连续段长度至少为 $k$，那么区间内的所有居民区进入「隔离」状态；否则，什么也不发生。
3. 给出 $l,r$。区间 $[\max(l-A,1),\min(r+A,n)]$ 内的所有居民区解除「被感染」状态和「隔离」状态。
4. 给出 $l,r$。查询区间 $[\max(l-A,1),\min(r+A,n)]$ 内有多少个居民区处于「隔离」状态。

其中 $A$ 表示上一次事件 $4$，即查询的答案，初始为 $0$。

$1\leqslant n\leqslant 10^9$，$1\leqslant m\leqslant 10^5$。

$\mathtt{1s/256MB}$。

抽象一下的话就是：

1. 区间覆盖
2. 查询区间最长连续段长度
3. 查询区间和

第一反应是珂朵莉树，但是细想发现需要手写平衡树维护，因为 std::set 在这道题中已经不够用了。

但是想了想觉得太麻烦了于是放弃了。

SHX 的写法是动态开点线段树，但是没写出来。

剩下的题

C 超级大模拟题（样例解释一页半）

D 看不懂

F 神仙计算几何题

L 神仙数学题