七夕节快乐{\color{white}\Huge\text{七夕节快乐}}

比较神秘的一场比赛，感觉四道都能算图论。

还有，考试把 continue 写成 return 0 了！！！（甚至能过大样例和几万组我的对拍）

大样例是真的水，除了第一题，全是 1010 以内的。

感觉整体难度比昨天高，题目质量也许高一点吧，除了 T3 这个神秘的题。

用时分数正解我的思路问题方案
T11010 min100100入门模拟入门模拟无无
T2120+120+ min6060树上倍增树上倍增 + 乱搞想错了，否定正解 / continue 写成 return 0 从 96 10096~100 挂到 6060想出来的 Hack 写纸上 / 想久了出去上个厕所再写 / 找老师要大样例（可惜这次没有付诸行动）
T35050 min44欧拉定理（图）暴力没有想到欧拉定理，去想别的 trick 了记住每一个结论
T43030 min44神秘图论暴力暴力挂了？

考试时间分配

感觉时间完全乱掉了。

先读了 1010 分钟的题。

8:30：T1 水题 1010 分钟。

8:40：T2 感觉做题的时候很有问题。当时想了 2020 分钟想出出了 a=ba=b 的情况，然后在 a=ba=b 且同层的情况卡住了。

正确的做法是二分，而我认为相遇了可能分开，事实上相遇了由于同层同速度，不会分开。于是我又被卡了 4040 分钟。

考试想着如果 T2 做不出来就真废了（事实上也是如此），然后就开始死磕了。结果发现如果我重新想一下，把 Hack 写纸上就会发现直接二分是对的。

9:45：发现时间已经快十点，赶紧写骗分程序乱搞那种情况。然后赛后发现原本这样有 9696，但是我把 continue 写成 return 0 了，只有 6060。

10:05：写完之后立刻写对拍，发现很难造数据，于是写了将近 3030 分钟构造各种数据，发现卡不掉我。也拍了几万组，没有问题。

（哦哦，还有一个提示，根据我们昨天的研究，奇安信会严重拖慢对拍速度，记得把 Qianxin Tianqing 关掉。我真的不知道为什么，当时只是 asa 尝试关掉奇安信，然后真变快了。）

10:40：于是还剩一个小时多一点，去看 T3，没有思路，感觉像性质题，但是我没有想欧拉定理（虽然前几天才做了一道欧拉定理的题，但是我认为这个不会考），只是思考各种 trick。

11:10：还剩一个小时，写暴力，发现会 TLE。于是写 T4 暴力。

12:00：写完暴力还剩 2020 分钟，放弃了。最后甚至 T4 暴力从 2020 挂到了 44。

不要死磕题了，如果没有思路就先去做后面的。回来看可能会有一些不一样的思路，或者单纯是从自己给自己设的圈里面走出来了。

考后 T2 可以 log2log^2 通过，事实上因为我懒（考试时间不够），不想写好几个函数，于是就写了两个 log⁡\log 的。

（甚至很多时候，特别是在 本地 / bbc，不知道为什么 long long 比 int 快）。

T1

题目概括

数轴上有 NN 个设备，坐标为 X1<X2<⋯<XNX_1 < X_2 < \cdots < X_N。需要建恰好 KK 个基站，每个基站可任选位置 PP 和半径 R≥0R\ge 0，覆盖区间 [P−R,P+R][P-R, P+R]。求覆盖所有设备的最小半径和的两倍，即 min⁡2∑Rj\min 2\sum R_j。保证答案为整数。

水题，不要想 dp。

T2

题目概括

给定一个分层有向无环图，每个点有层数 huh_u，每个非终点有 kk 个有序出口，移动一步后指针 pp 循环加 11（0∼k−10\sim k-1）。终点则原地不动。qq 次询问，每次两台机器人分别从 x,yx,y 出发，指针初值 00，每秒分别连续走 aa 步和 bb 步，仅每秒末检查位置。求最早相遇秒数 tt，若永不遇则输出 −1-1。

再也不敢死磕了。

当时想了 2020 分钟想出出了 a=ba=b 的情况，然后在 a=ba=b 且同层的情况卡住了。

正确的做法是二分，而我认为相遇了可能分开，事实上相遇了由于同层同速度，不会分开。

T3

题目概括

无限平面按单位方格划分，初始全白。每次操作将某格 (x,y)(x,y) 涂黑（重复无效）。所有黑色格子的并集视为带边界的封闭图形，平面补集中的有界连通白色区域称为“湖泊”。每次操作后输出当前湖泊数量。n≤2×105n\le 2\times10^5，坐标范围 ±109\pm10^9。

欧拉定理结论。考试前我几天才做过，但是以为不会考这种东西就没认真记下来，考场也没有想...

F−1=C+E−VF-1 = C+E-V

动态维护 C,E,VC,E,V。

VV：点数，EE：边数，FF：面数，CC：连通块数。

T4

题目概括

给定一棵 nn 个点的树，每个点 ii 有参数 (ai,di)(a_i, d_i)。进入点 ii 时要求当前体力 ≥ai\ge a_i，然后体力变为 min⁡(C,  E+di)\min(C,\; E+d_i)，其中 CC 为体力上限。qq 次询问，给定起点 uu、终点 vv 和初始体力 EE，可任选整数上限 C≥EC\ge E，且全程至多使用一次紧急补给（在进入某点前将体力补到 CC）。求：① 最小可行 CC；② 在该最小 CC 下，最晚的补给位置（若无需补给则输出 00）；③ 按该方案到达终点后的体力。

正解其实是能想的，但是考试能不能成功写出来我就不知道了。

整体思路就是倍增维护一个四元组，记录：

  • 进入所需的最小初始体力
  • 所需的最小体力上限
  • 不考虑上限时的体力净变化
  • 体力被上限截断后，最终体力等于上限减去多少。

然后进行 C 的二分和位置的二分。

C 的二分利用二分补给点的下标，然后找到左边的值和右边的值尽量平衡的点，即 A(x)>B(x+1)A(x)>B(x+1)。

补给点确切的坐标还需要一次二分才准确。