奶龙击败贝利亚，我纯躺赢 Rank.8。
本场比赛可以在 2024 ICPC Asia Taichung Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams) 参与。是 台中区域赛 的镜像赛。
我的队友分别是 夜明 和 IvanZhang2009。
游记
本来想单挑的，但是大家都组了队带队友来世贸打，夜明 老师也想给自己找个队友，就拉了我和 ivan 打。
我本来是一个大号两个小号组了一个队叫『我是奶龙』，加了新成员就还是叫『我是奶龙』了。
这个队名是我在上周一上课的时候偷摸打 2024-2025 ICPC, NERC, Southern and Volga Russian Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams)
的时候起的。
值得一提的是 KingPowers + 崔化博 + Svemit 的队伍名称是『我是贝利亚』，是看了我们的队名临时改的。
那么，接下来是，奶龙大战贝利亚的时间。
三个人临时组的队一点策略没有，反正就随机开题。我先随机开了 A,B,C,E,M，挑了个题面最短的 A 读了一下，发现是个签到。00:00:46 的时候提交了 A 题。结果我没测样例挂了。还好 WA on 1 不罚时。00:01:04 的时候顺利过掉 A。
接下来随便看看发现 E 似乎也是简单题，已经有队伍过了。读了一下发现不难，一定在 n=3 有解，直接输出就行。00:06:58 过掉了 E。
ivan 先开的 C，在 00:08:44 的时候过掉了 C。夜明 在看 B，00:14:01 的时候也过掉了。
此时我们光速 4 题。
队友写完 C,B 的时候我看到有队伍过了 D，读了一下发现是搜索题，我上手几分钟就写完了。00:17:55 过了 D。
此时光速 5 题！
在队友写 C,B 期间我读了 H，把题意报了然后我就润了去写 D 了。Ivan 听完就会了，00:33:18 的时候提交了一发 WA on 3 发现是两行写反了。00:34:37 的时候过掉了 H。
夜明在手玩 M。他好像意识到了 M 的关键性质，00:43:55 过掉了 M。
7 题。靠着巨大的手速和罚时优势成为了 rk.1。
接下来就要靠我们自己开题了。
我随机读了一点，发现 I 可能是个简单题。但是不是很好写，我一度以为自己假了。但是世贸的别的队伍『我是贝利亚』和『Zhang BlgorixthW』都在开 I。简单想了一下好像就是离线一下就做完了。
上了个厕所冷静一下开写。我感觉还有点难写啊？？？
写了一半发现排序方式优先取长度更大的，我看成长度更小的了。本来一个 Trie 上面 BFS 就解决的事情还得补点东西。
此时我像个 dinner 一样，愣是没想到长度就是 Trie 上的深度，我还把字符串拎出来在排序的时候判长度处理了。排序部分写了一坨。
然后我就死活不知道自己挂哪里了。看了一眼数据范围，id 的范围是 [0,n]。6。还没有保证编号连续，我开了个 vector 用 pair 存信息排序。
然后就莫名其妙 RE on 5 了。我觉得是字典树上 set 的删除问题，但是题目保证合法，为了验证我甚至我还在插入删除部分写了一个不合法就 exit(0) 的程序，发现没有异常，那说明不是这一段的问题。
查了半天我发现我从输入的 if 分支拷贝到离线的 if 分支的时候，由于我不需要处理 delete 操作，所以我把这个 if 删了，但是我判断操作最后一项写的是 else 不是 else if。导致我删除这个分支会让 delete 操作进入不该进入的分支执行。
这个真无敌了，谁看得出来啊？？？
改完就过了，这题纯纯我的锅，调了这么久还吃了一堆罚时。
02:05:37 的时候过掉了 I。此时排名十名开外了。
过掉之后我看 ivan 在贺 Miller Rabin。他说是判素数用的，然后说 F 自己复杂度是错的，不会求 [l,r],r-l+1\leq 10^5 的素数。但我记得我入门线性筛的时候做过这个模板啊？洛谷的 P1835 素数密度。我改了个线性筛上去，结果 TLE on 3 了。
然后发现记忆化搜索部分有一段可以预处理掉的二分，此时 ivan 已经开摆了，我帮他加了线性筛又改了预处理。结果还是 TLE 啊？测了一下本地发现线性筛部分是瓶颈，因为我在线性筛途中处理了素数，每次都做了一遍线性筛，测了一下线性筛耗时巨大，干脆这一部分也预处理了。把求区间内素数的再单独拿出来每组 case 算一下就行了。改了改过了，极限数据本地 500ms，稳了，交一发，过了，此时是 02:50:04。
在我改 F 期间夜明老师写了很久的 J。02:33:15 过掉了。此时的我还不知道这个 J 有多难，看榜发现 9 题和 10 题的 gap 就在这个 J 上。此时我们是 rk.5，和 kradcigam 捆包队贴贴了。捆包队以罚时优势领先我们。
ivan 说看了 G 很久不会，我看了 L 是计算几何，我们三个都不会，N 我很早就开了，报了题意都不会。此时 MatrixGroup 和 zhuzhu2891 和我们罚时相同，他们过的是 K 没过 J。ivan 去吃饭了，我读了 K 题意发现很难，也摆了，和 是青白呀 点了个外卖开吃。
吃着吃着我点开了好友提交界面，发现捆包队过了 K。我看了看榜不动了，应该是封榜了。诶不对，封榜了可以通过看好友提交记录然后知道别的队交题情况？？？逆天。
最后『我是奶龙』队以 10 题 851 罚时的成绩与 『shengqile.cpp』 队一起获得了 rk.8 的成绩。
是不是差在了我 A 不测样例直接交导致浪费了一分钟啊（？
不过奶龙队击败了贝利亚队，贝利亚队没过 J。高下立判，奶龙统治世界。
题解
无敌了，我写了俩小时然后没保存。小波发现了专栏编辑器的自动保存出 bug 了。
A. The Bento Box Adventure
给定 4 个整数 a,b,c,d。求 \{1,2,3,4,5\} 中没出现的那个数。
---
根据异或的性质 $x\oplus x=0,0\oplus x=x$。我们用把这 $4$ 个数和 $\{1,2,3,4,5\}$ 都异或起来就是答案。
也就是输出 $1\oplus 2\oplus 3\oplus 4\oplus 5\oplus a\oplus b\oplus c\oplus d$。
推荐相似题目：[P1469 找筷子](/problem/P1469)。
<https://codeforces.com/contest/2041/submission/293494235>
## B. Bowling Frame
给定 $w$ 个白点和 $b$ 个黑点，拼三角形，要求三角形第 $i$ 行有 $i$ 个**同色**的点，最大化三角形行数。
多测，$1\leq t\leq 100$。
$0\leq w,b\leq 10^9$。
---
赛时看了喜提第一眼不会。丢给队友去写别的题了。
结论题。
定义 $S(n)=\frac{n(n+1)}{2}$ 即行数为 $n$ 的三角形需要的点数，不难通过等差数列求和推出。
答案即为最大的 $n$ 满足 $S(n)\leq w+b$。
接下来开始证明。首先如果 $w'\leq w,b'\leq b$ 且有 $w'$ 和 $b'$ 就可以组成一个三角形，那么 $w$ 和 $b$ 一定也能组成这么大的三角形。因为可以有剩余。
所以我们证明恰好等于的情况就可以。。
数学归纳法证明。
$n=0$ 时，$w,b$ 取任何值都可以拼出大小为 $n$ 的三角形。相当于一个不用就可以了。
若 $n=k$ 时，对于 $w$ 取任意值，$b$ 取任意值，成立，则 $n=k+1$ 时，$w$ 取任意值，$b$ 取任意值，也成立。
考虑新加的第 $k+1$ 行填什么颜色。**只要能填上，就可以化到 $n=k$ 时的情况**。
也就是说我们只需要证明：在拼出行数为 $k$ 的三角形时，此时 $w,b$ 取任何值（满足 $w+b=S(k+1)$），他们的的最大值都会比 $k+1$ 大也就是可以拼出第 $k+1$ 行。
第 $k+1$ 行有 $k+1$ 个点，而 $k+1$ 行的三角形需要 $S(k)$ 个点，较多颜色的那个点**至少**有 $\lceil\frac{S(k+1)}{2}\rceil$ 个。
证明 $k$ 取任意值都有 $k+1\leq \lceil\frac{S(k+1)}{2}\rceil$ 即可。
~~仍然可以数学归纳法。~~
大力拆式子。
$$
\begin{aligned}
k+1 &\leq \lceil\dfrac{S(k+1)}{2}\rceil\\
k+1 &\leq \lceil\dfrac{\frac{(k+1)(k+2)}{2}}{2}\rceil\\
k+1 &\leq \lfloor\dfrac{\frac{(k+1)(k+2)}{2}+1}{2}\rfloor\\
2(k+1)&\leq \dfrac{(k+1)(k+2)}{2}+1\\
4(k+1)&\leq (k+1)(k+2)+2\\
2(k+1)+2k+2&\leq 2(k+1)+k(k+1)+2\\
2k&\leq k(k+1)
\end{aligned}
$$
这个不等式在 $k=0$ 和 $k\geq 1$ 的时候都显然成立。因此 $k+1\leq \lceil\frac{S(k+1)}{2}\rceil$ 就是成立的。
<https://codeforces.com/contest/2041/submission/293495113>
## C. Cube
有 $n\times n\times n$ 的立方体，选 $n$ 个点，使得没有任意两点在同一平面，最小化点权。
对于点 $(x_1,y_1,z_1)$ 和点 $(x_2,y_2,z_2)$，在同一平面当且仅当 $x_1=x_2\lor y_1=y_2\lor z_1=z_2$。
$1\leq n\leq 12$，$0\leq a_{i,j,k}\leq 2\times 10^7
敢写，敢交。
限制等价于所有点的 x,y,z 坐标互不相同。
把 x 互不相同拎出来，改成在 1 到 n 依次选择。
$f_{i,Sj,Sk}$ 表示 $x$ 坐标选到了 $i$，此时 $y$ 坐标集合为 $Sj$，$z$ 坐标集合为 $Sk$。
转移枚举合法的集合，枚举不在集合里的数即可。
看起来这非常的暴力，复杂度粗略一算是 $\mathcal O(2^{2n}n^3)$ 的。理论复杂度 $2\times 10^{10}$。
但其实精细表示一下，这个运算量其实是 $\sum \limits_{i=0}^n \binom{n}{i}^2 (n-i)^2$。当 $n=12$ 的时候其实是 $10^8$ 左右的运算量。3s 的时限随便过。
<https://codeforces.com/contest/2041/submission/294597429>
## D. Drunken Maze
有 $n\times m$ 的地图，`#` 表示障碍，`.` 表示空地，`S` 表示起点，`T` 表示终点。要求不能**超过**连续三步走同一方向，不可以通过障碍。起点终点视作一种空地。
问 `S` 到 `T` 的最小步数。无法到达输出 `-1`。
$12\leq n\times m\leq 2\times 10^5$，$3\leq n,m\leq 10^4$。
---
直接用 $4\times 3\times n\times m$ 的状态数的搜索是可过的。
$f_{i,j,0/1/2/3,1/2/3}$，表示这是从什么方向走到 $(i,j)$ 的，这是第几步。
转移枚举下一步的方向。如果相同并且已经走了三步就无法转移，否则就可以走。如果这个状态之前搜过就跳过。每个状态至多入队一次，更新 $\mathcal O(1)$ 个状态，复杂度是 $\mathcal O(nmAB)$ 的。其中 $A=4$ 表示方向的数量，$B=3$ 表示约束的步数。
关于实现：这类约束了 $nm$ 的题，开数组可以使用 vector 或者开局部数组然后清空。一些函数可以写成 lambda 表达式的形式。
<https://codeforces.com/contest/2041/submission/293536077>
## E. Beautiful Array
构造序列，满足序列中位数是 $b$，平均数是 $a$。
平均数：$n$ 个数 $A_i$ 的平均数是 $A_i$ 之和除以 $n$。即 $\dfrac{\sum\limits_{i=1}^n A_i}{n}$。
中位数：$n$ 个数 $A_i$ 排序后，若 $n$ 为奇数则为 $A_{\frac{n+1}{2}}$，否则为 $A_{\frac{n}{2}}$ 和 $A_{\frac{n}{2}+1}$ 的平均数。
$-100\leq a,b\leq 100$。
要求构造的答案序列长度在 $[1,10^3]$ 之间，答案序列元素均为绝对值不超过 $10^6$ 的整数。
---
考虑能不能用最朴素的构造求出来。$n=3$ 的时候不妨令中位数 $A_2=b$。然后调整平均数。
一开始令 $A=[b,b,b]$，但是可能不满足条件。
如果平均数 $\gt a$ 则 $A_{1}$ 减小 $1$。
如果平均数 $\lt a$ 则 $A_{3}$ 增大 $1$。
显然这样一定能出解。出解至多需要做 $|3a-3b|$ 次操作。而在本题的数据范围 $|3a-3b|$ 至多为 $600$。
<https://codeforces.com/contest/2041/submission/293511197>
# F. Segmentation Folds
给定 $[l,r]$，你需要选择以下操作任一执行：
- 选择一个最大的 $x(l\lt x\leq r)$ 满足 $l+x$ 是质数，$[l,r]\to [\frac{1}{2}(l+x),r]$。
- 选择一个最小的 $x(l\leq x\lt r)$ 满足 $r+x$ 是质数，$[l,r]\to [l,\frac{1}{2}(r+x)]$。
如果这个区间 $[l,r]$ 无法操作，则称这个区间为一个结束状态。否则继续递归。
问所有结束状态中，长度最小的有多少个。答案对 $998244353$ 取模。
多测，$1\leq t\leq 10$。
$1\leq l\lt r\leq 10^{12}$，$r-l\leq 10^5$。
---
为了规避浮点问题，我们把所有区间的 $l,r$ 都乘上 $2$。
我们首先要把 $[2l,2r]$ 之间的素数都筛出来。我们先预处理到 $\sqrt{2r}$ 的所有质数，然后把这些质数在 $[2l,2r]$ 内的倍数筛出来。具体参见 [P1835 素数密度](https://www.luogu.com.cn/problem/P1835)。
然后大力搜索即可。
搜索的时候可以通过二分找到第一个和最后一个合法的 $x$。但是这样复杂度多带一个 $\log$。我们把二分的内容拎出去，在预处理完质数之后，枚举所有的情况找到上一个下一个质数。
搜索的结束状态一定是两个相邻的质数。只有 $\mathcal O(\frac{n}{\log n})$ 个。而每个状态只有 $\mathcal O(\log n)$ 个前驱状态，所以直接搜索甚至不带记忆化的复杂度是 $\mathcal O(n)$ 的。
总复杂度瓶颈在筛质数的 $\mathcal O(n\log \log n)$。
代码写的有点丑了，丑在了：
>我们把二分的内容拎出去，在预处理完质数之后，枚举所有的情况找到上一个下一个质数。
这一部分。写的是二分，如果写双指针最后复杂度就是 $\mathcal O(n\log \log n)$。这份代码是 $\mathcal O(n\log n)$ 的。
<https://codeforces.com/contest/2041/submission/294604119>
## H. Sheet Music
定义两个序列 $a,b$ 是同一『类型』当且仅当对于所有 $i$，$a_i$ 和 $a_{i+1}$ 的大小关系与 $b_i$ 和 $b_{i+1}$ 的大小关系一致。
大小关系指：大于，小于，等于。
给定 $n,k$，求值域在 $[1,k]$ 的长度为 $n$ 的序列有多少个『类型』，答案对 $998244353$ 取模。
$1\leq n\leq 10^6$，$1\leq k\leq 10^9$。
---
等价于对符号序列计数，并且**删去等号后**满足不存在连续的 $k$ 个符号相同。
设 $f_{i,0/1}$ 表示第 $i$ 个位置填大于号或小于号的方案数。
初值 $f_{0,0}=f_{0,1}=1$。
转移为 $f_{i,0}=\sum\limits_{j=i-k+2}^{i-1} f_{j,1}$，$f_{i,1}$ 的转移同理。
显然这个式子可以用前缀和优化 DP。
之后对答案计数。枚举大于小于号序列的长度。等号可以随意插入，长度为 $i$ 的序列，插入方案数为 $\binom{n-1}{i}$，这就是系数。
答案为 $(\sum\limits_{i=0}^{n-1}\binom{n-1}{i}(f_{i,0}+f_{i,1}))-1$。
最后 $-1$ 是因为第 $0$ 个位置，就是不填符号，大于小于贡献一样，算一个的即可。
<https://codeforces.com/contest/2041/submission/293242222>
## I. Auto Complete
你需要维护一个搜索引擎。支持 $n$ 次操作。共 $4$ 种操作。
1. `add id str` 给搜索引擎插入编号为 $id$ 的内容为 $str$ 的『备选项』。
1. `delete id` 删除编号为 $id$ 的『备选项』。
1. `append str` 给搜索框后面继续输入 $str$ 的内容。
1. `backspace cnt` 给搜索框后面删除 $cnt$ 个字符。
每次操作后，你需要输出目前的『最优』的『备选项』。
『最优』的『备选项』定义为：
1. 搜索框内容是这个『备选项』的前缀。
1. 若满足 1 的有多个，选最长的。
1. 若满足 2 的有多个，选字典序最小的。
1. 若满足 3 的有多个，选编号最小的。
$1\leq n\leq 10^6$，$1\leq \sum |str|\leq 2\times 10^6$，$1\leq c\leq 2\times 10^6$。
保证字符串的字符 ASCII 码范围在 $[33,126]$ 以内。
`add` 操作的 $id$ 两两不同。
`delete` 操作的 $id$ 两两不同。
$id$ 范围在 $[0,n]$ 之间。
---
这个前缀很引导我们往字典树上想。前缀就对应着祖先。
把这些备选项判定拎出来，前缀就对应着必须是祖先，长度对应深度，字典序对应着 DFS 序。
先离线操作，把所有操作全扔到字典树上。删除操作就是跳若干次父亲，所以需要记录字典树每个节点的父亲编号。
这里保证操作合法，所以往下走几步就至多往上走几步，跳父亲暴力跳就行了。
操作离线完就做一次深搜。处理出 DFS 序。
这个编号不是连续的，范围是 $[0,n]$。处理的时候要小心点。
字符集大小很大，直接开数组会浪费很多空间，可以用 map 换空间。
赛时太急了没好好看条件，忘判长度了，最后硬加了一个/xk 写的有点丑。
<https://codeforces.com/contest/2041/submission/293614507>
## M. Selection Sort
给定长度为 $n$ 的序列 $a$，对长度为 $m$ 的序列使用一次 Alice-Sort 的代价为 $m^2$。
```cpp
int alice_sort(int *s, int n){
for(int i = 0; i < n; ++i){
for(int j = i + 1; j < n; ++j){
if(s[i] > s[j]){
int swap = s[i];
s[i] = s[j];
s[j] = swap;
}
}
}
return 0;
}
```
有两种操作：
可以使用 Alice-Sort 对一个前缀排序。
可以使用 Alice-Sort 对一个后缀排序。
每种操作**限用一次**。
问把序列排好序的最小代价。
$1\leq n\leq 10^6$，$0\leq a_i\lt 2^{31}-1$。
---
一共只排两次序，枚举先排前缀还是先排后缀。
不妨认为先排前缀。枚举前缀需要排序到哪里，然后算出后缀排到哪里。
重复值有点难搞（其实也不难搞，先处理了后面操作更顺利），我们把这个数组先改成 $[1,n]$ 的排列，相同值越前面的越小。
枚举前缀排序到了哪里，维护值的连续段。$lst$ 表示值在 $[1,lst]$ 的数都可以归为了。那么 $[lst+1,n]$ 的就是需要重排的。
$lst$ 可以直接维护。再维护一个小根堆，里面是已经在区间内但是连不起来的元素，$lst$ 每次根据堆里的元素尝试往后扩展。
但是这有个问题，我们无法判断那些，后缀无需排序的，和我们已经扩展了前缀的，但是没有必要把一些元素加进去排序的。
先处理第一个，我们找到原数组最后一个不合法（$a_i\neq i$）的位置记作 $r$，那么 $i=r$ 的时候不要加上后缀排序的贡献。
第二个，我们维护**上一个**需要排序的位置，就是无法直接加入的，即堆内有元素，或者 $a_i\neq lst+1$。记这个位置为 $pos$，那么前缀排序到 $i$ 的代价只为 $pos^2$。
以上是先选前缀排序的做法，先选后缀排序本质一样。代码复制一遍改一改就行了。
<https://codeforces.com/contest/2041/submission/294548198>
## N. Railway Construction
有一张 $n$ 个点的完全图，连接 $(u,v)$ 的边边权为 $a_u+a_v$。其中删除了 $m$ 条边。
你需要回答 $n$ 个问题。第 $i$ 个问题你需要回答，删除 $i$ 号点之后，使剩余节点联通的最小代价。若无法联通输出 `-1`。**问题互不影响**。
$2\leq n\leq 10^5$，$0\leq m\leq 10^5$，$1\leq a_i\leq 10^9$，$1\leq u\lt v\leq n$，保证无重边。