2024 ICPC Asia 昆明区域赛 VP 记
lmh_qwq
·
·
个人记录
省流：被 grg 和 irris 带飞。
THUPC 之前总得练一场吧。
约好了三个人按照题号 \bmod\ 3 的值分别开题，于是我分到了 B，E，H 和 K。一开始发现 B 体面很长像是什么奇异搞笑串串题，不会。刚打算开 E 发现已经有老哥过了 H（有实时榜单），于是去看 H。发现是个签到题，计算几何有点坑但是几分钟就做完了。与此同时 grg 和 irris 分别开了 J 和 M。irris 被 M 的 corner case 卡住了，帮他写了个搜，很快也过了。
随机想题的时候发现 G 似乎可做。想题。想不出。irris 也想不出。想出来了。感觉是个 O(n^2) 的 dp，写。写挂了。
很快拍出了挂掉的数据，发现这个做法好像不太有救。这时队友写完了 J 和 C，grg 过来之后发现这题答案上界很小，直接整了个迭代加深的搜就过了。（你还记得我们的模三开题法吗？反正我们已经忘干净了。）
这时感觉自己疑似有点太没用了，于是开 B。很快会了一个假做法（能处理块内的情况，但会把块间的 [(]) 判为合法），写完之后过不了样例，并且感觉做法有点没救，生气。
与此同时 grg 和 irris 在搞 F 并且似乎很有希望，觉得自己也得为团队做点贡献。开 E。是个线性基板子，开写。不到一刻钟就过了。
过程中几个人冲了好几次 L 但都遗憾离场，现在队友终于想明白了。这时候我看了两眼没人开的 A，D，I 和 K，发现了 D 的答案单调性但没啥想法。
irris 发现自己读错了 L 的题面，于是前去救急。irris 发现自己的做法假了，但同时我也差不多想出来了。一番交流无果之后决定自己写，很快就过了。
grg 啃了一会 I 之后会了奇异搞笑 poly 做法，但这玩意的实现难度和赛时通过人数显然不太匹配。irris 会了 B，我就去开有一点想法的 D。
不久之后就会了主席树做法，写写写，二分写挂了？改改改。赶在 3h 之前成功通过。
和 grg 一起冲剩下的三题，没啥收获。
irris 的 B 题矩阵做法假了，会把 )( 判成合法。此时我发现我的做法正好能处理掉这种情况，也就是说两种做法拼一起是对的。
从他那里抄了个矩阵板子，遂开写，整出依托史山。过不了样例，最后发现板子抄错了。
代码跑得很慢。最慢的一个点花了 2.3s，但距离 3s 的时限还是绰绰有余。
最后剩下 A，I，K，grg 提前走了，我和 irris 一点思路没有。
看不明白 grg 的 F 题代码。感觉数学还得多练。
倒闭了。
写一点解法吧。下文中题目以主观难度排序。
H
显然按照极角排序找最大的 \theta_{i+k}-\theta_i。注意使用 atan2(y,x) 简化计算。
J
(from Graygoo)
$n\ge 4$ 时，如果 `Alice` 无法一步完成排序，可以证明她就没救了。具体地，`Bob` 每一步都尽可能打乱序列使得至少三个位置有问题，但是 `Alice` 一步只能动两个数。
### M
如果 $m$ 是偶数的话直接按顺序排即可。注意到同一行的相邻项和都是奇数，同一列的相邻项和都是偶数，且显然它们互不相等。$n$ 为偶数的情况同理。
如果 $n,m$ 都是奇数的话就先按顺序排，然后把偶数行向左循环移位一格即可。证明是类似的。
### C
(from Graygoo)
真没啥好说的，就是个模拟。当然朴素的模拟过不了，所以要把淘汰人数相同的一系列操作捆绑到一起做。复杂度 $O(\sqrt n)$。排在这个位置主要是有一车细节。
### G
(from Graygoo)
发现一个显然的构造：考虑每次将 `gcd` 增大一倍，发现最多只需要两次操作（证明显然）。所以答案上界约为 $2\log a$，迭代加深搜索是 $O(a^2)$ 的，可以通过。
### L
每个人最多只能打一次，所以我们让尽量多的人打出来，最后触发一次爆炸的连锁反应。
先对双方血量进行排序。血量大于一的人显然都可以打一次，血量等于一的人加起来只能打一次。在最后一次之前我们让小朋友尽量打血量大于一的敌人，这样只要中途触发爆炸一定会把所有敌人炸似。
这样最后爆炸时所有我方小朋友的血量是确定的，模拟一下爆炸的过程就能算出对方对应位置每个人的最大血量，然后算一下要攻击几次即可。
### E
线性基板子。用 `bitset` 可以轻松做到 $O(\frac{n^4}{w})$，并且跑不满。实际上只需要 $n-1$ 次询问。。
### D
令 $f_i$ 表示前 $i$ 个数操作后最少可以只剩下 $f_i$ 个点。设 $f_0=0$。
首先证明一堆单调性。
Lemma 1：如果 $[L,R]$ 合法（能缩成一个数），则 $L\le l\le r\le R$ 的 $[l,r]$ 合法。
证明：直接把 $[L,R]$ 中不涉及 $[L,l)\cup (r,R]$ 中元素的操作拉出来做即可。
Lemma 2：$f_i\ge f_{i-1}$。
证明：假设一个取到 $f_i$ 的分段方式为 $[l_1,r_1],\cdots,[l_{f_i},r_{f_i}]$，把最后一个段往左缩一格即可构造出 $i-1$ 的方案。
Lemma 3：假设 $l$ 为使得 $[l,r]$ 合法的最小的 $l$，则 $f_r=f_{l-1}+1$。
证明：显然 $f_r$ 只能从 $f_{l-1}\sim f_{r-1}$ 转移过来，其中 $f_{l-1}$ 是最小的。
所以现在我们只需要快速找出最小的 $l$。考虑在枚举 $r$ 时动态维护。
Lemma 4：如果 $l<p<r$，$[l,p],[p,r]$ 合法且 $\forall i\in [l,p),a_i<\min_{j=p}^ra_j\vee a_i>\max_{j=p}^ra_j$，则 $[l,r]$ 合法且存在一种将 $[l,r]$ 缩成一个点的方案使得前 $r-p$ 步将 $[p,r]$ 中所有数缩成一个点。
证明：显然 $[l,p],[p,r]$ 都合法，把 $[p,r]$ 缩成一个点之后它和其他位置的偏序关系和单独一个 $a_p$ 等价，于是依然合法。
现在我们考虑 $r\to r+1$ 之后 $l$ 的转移。不妨设 $a_r<a_{r+1}$。
不妨设 $l$ 足够小。如果它比较大的话那么根本不会被下文的算法更新，也就无需考虑这种情况了。
令 $p$ 为使得 $a_p>a_{r+1}$ 的最大的 $p$。由于 $(p,r]$ 合法（$l$ 足够小），而 $a_{r+1}$ 大于 $a_{p+1}\sim a_r$ 中所有数，那么 $(p,r+1]$ 也合法。
现在考虑找出因为 $r+1$ 的加入变得不合法的最大的 $l'$。下证明 $l'$（如果存在）为使得 $\min_{i=p+1}^{r+1}a_i<a_x<a_{r+1}$ 的最大的 $x$。
首先对于 $y>x$，由 Lemma 4，可以证明合法。
假设 $a_w=\min_{i=p+1}^{r+1}a_i$。现在考虑 $x<p<w<{r+1},a_w<a_x<a_{r+1}<a_p$。
如果我们先把 $x$ 和 $p$ 缩到一起，那么 $a_{r+1}$ 就无处可去了；否则，如果我们把 $w$ 和 $r+1$ 缩到一起，那么 $a_x$ 就无处可去了。因此这种情况不合法。
找出 $p$ 是简单的。找出使得 $\min_{i=p+1}^{r+1}a_i<a_x<a_{r+1}$ 的最大的 $x$ 可以通过主席树和二分解决。
### B
把所有 $m$ 个子串进行垃圾分类：
`O`：子串本身合法。
`L`：子串不合法，但可以在右边拼接一个串使其合法。
`R`：子串不合法，但可以在左边拼接一个串使其合法。
`X`：其他垃圾。
答案就是 `O/2` 加上 `L,R` 尽可能匹配的结果。
显然 `(]` 之类的东西是不合法的，可以直接归为 `X`。具体地，开一个栈维护左括号的序列，就可以求出每个 $r$ 对应的最小的可能属于前三类的 $l$。每次如果找到一对不匹配的括号，那么更新 $l$ 并把栈清空即可。
现在子串内不会有稀奇古怪的东西了，就可以把四种括号拆开算简化问题。如果内部尽可能匹配之后，左边剩下几个右括号，右边又剩下几个左括号的情况属于 `X`，否则可以简单地把它们分成三类。
现在我们要把 `L,R` 内元素尽可能匹配。
(from irris) 给每种括号随一个矩阵，让左括号对应原矩阵，右括号对应它的逆，这东西满足结合律不满足交换律，就可以记录下剩下的单边括号的顺序，之后就简单了。这个玩意无法处理 `)(` 之类的情况，所以要先做分类。
剩下的题不会。倒闭了。