VP 记录

前言

从 2023.10.27 开始，每天 VP 一场 ABC / ARC / Div2 / Div1。要补题并写总结。

持续更新 ing...

2023.10.27 - ABC255

第一天先开一场 ABC 试试水。

A 题手速题，1 分 08 秒过，还是慢了点。

B 题被翻译诈骗了，还想了一手二分，但看到 \(n\le 1000\) 直接枚举。不过为什么 B 题会出一道不是计算几何的计算几何。5 分 26 秒过题。

C 题也被翻译诈骗，翻译把第一个条件翻译成了：将 \(1\) 加到 \(X\)。看了一手样例才发现是让 \(X\gets X+1\)。那么首先将大于最大值和小于最小值判掉，再二分找到等差数列中最接近 \(X\) 的两个数即可。不过二分要分 \(D>0,D=0,D<0\) 三种情况分类讨论，还有一些特判。吃了一发罚时。15 分 43 秒过。

D 题一开始看错题了，以为是每个数都要变成 \(X_i\) 中的一个，花了五分钟写了一个 set 后才发现看错题了。原题是 \(Q\) 个询问，那么直接将询问离线按 \(X_i\) 排序，\(A\) 也排一遍序，双指针求出当前小于 \(X\) 的数的和 \(s_1\)，大于等于 \(X\) 的数的和 \(s_2\)，小于 \(X\) 的个数 \(m\)，用 \(s_1-mX+(n-m)X-s_2\) 更新答案。29 分 19 秒过题。

E 题是简单题，只要确定了 \(A_1\) 就可以确定 \(A\) 的整个序列，设 \(A_1=a\)，那么容易推出 \(A_i=d_i\pm a\)，其中 \(d_i\) 可以递推出来，即 \(d_i=s_{i-1}-d_{i-1}\)，而 \(d_1=0\)，当 \(i\) 是奇数时取正号，否则取负号。那么我们只需要枚举 \(A_i\) 等于 \(X\) 中的哪一个，用 map 维护此时对应的 \(a\) 的出现次数。最后的答案就是 map 中的最大值。39 分 50 秒过。

F 也是简单题，我们在 \(l\) 中可以直接找到一个点的子树对应的区间，用 \(p\) 可以找到一个点的两个子节点，递归处理即可。56 分 07 秒过题。

G 题是博弈论，不会，直接跳了。

H 一看就是 ODT，我在每个节点上维护当前的值，每个时间段暴力更新所有区间，如果数据水时间复杂度期望是对的，但 T 了 4 个点。赛后发现可以直接维护最后一次被清空的时间，这样时间复杂度就是对的 \(O(q\log q)\) 了，只需要改一点点就可以。

最后 VP 榜上 rk 19，映射回原排名 rk 143，表现分 2335。（居然这么高，超常发挥了）

继续保持，不要降智。

不过 H 没切还是很可惜的，ODT 调久了。