SXOI2025 游记
yshpdyt
·
·
生活·游记
DAY ?
省选前两周开始恢复训练。主要打了去年买了没做的正睿的模拟赛，看了看去年省选计划的课程，被正睿题打爆了，自信心减减。
期间做不动题转化心情去参加了文化课考试，喜提年级 $\text{rk308}$。
考完加吃湖北模拟，$\text{T1}$ 有个看上去最坏复杂度 $O(n^2\log n)$ 但常数很小的做法，代码难度不大就先写了，一测跑的飞快就没在意，$\text{T2}$ 字符串不会跳了，$\text{T3}$ 感觉很树上 $\text{dp}$，刚好省选计划作业里有类似题目，很快打出了 $\text{45}$ 分做法，尝试卡常，然后开摆，最终 $90+0+45=135$，感觉自信心恢复了些，并祈祷省选不出串串题。
# DAY 0
睡了个懒觉，下午坐高铁去太原，住在山西大学对面的某宾馆，酒店质量比较差评。
加吃了阎锡山菜，感觉一般，随后回酒店敲版子去了。
分析了一下局势，考虑三分之一队线，$\text{NOIP}$ 标准分低了 $\text{9}$ 分，感觉每天做完 $\text{T1}$ 然后多打打暴力就可以了，和学长同学聊了聊尝试放松心态，起到了短期作用。
但还是紧张，晚上睡不着，半夜一直上厕所，到了两点多才睡着。
# DAY 1
熬夜完早上并不怎么困，困的是下午，起床还算精神，喝了杯咖啡就直奔考点了。
进场改完 $\text{Sublime Text}$ 的配置，敲了下预处理组合数的公式，~~扫雷~~。
只有解压密码没有试题密码。
$\text{T1}$ 是个中位数的题，做过类似套路很容易想到二分 $x$ 转化为 $01$ 然后判定，进一步发现对于一个 $x$ 可以分为 $r_i<x$，$l_i\le x \le r_i$，$x < l_i$ 三部分，用线段树可以维护前两个值，第三个可以根据前两个算出来，将 $x$ 离散化扫描线，讨论一下中位数在哪即可。
$\text{T2}$ 是个图图题，$\text{20}$ 暴力很水，看其它性质感觉是什么神秘树剖+可持久化线段树，但是合并起来复杂度一坨，写起来也一坨，把暴力打完就跳了。
$\text{T3}$ 是个构造题，相当于最后的排列连边不能交叉，观察发现大样例开头都是 $1$，进一步猜想肯定是贪心放，考虑树的情况，维护每个子树内的最小编号，用链表维护即可，但是死活调不过森林的最后一个样例，一通乱改加了一堆特判，感觉可能挂。
回去看 $\text{T2}$ 找能不能水更多分，发现可以用 `bitset` 啥的预处理优化，但是估计写不完了，太失败。
预计得分 $100+20+[28,52]=[148,172]$，出考场听说大众分是 $128$，感觉还不错，但是有个 $200$ 分的是什么逆天。
昨晚睡得太难受于是搬去了隔壁刚装修的酒店，中午吃了美式烤肉，很香，但是吃完肚涨一下午，下午看了看常用 $\text{trick}$ 就开摸了，输了一下午差分宇宙，很红温，耻辱下播。
# DAY 2
睡了 $\text{12h}$，太原下大雨了变得很冷，~~这种环境不用来加睡太可惜了。~~
根据去年和前年的经验，感觉分数趋近于 $100$ 就稳了。
开 $\text{T1}$，看到 $\text{C} $ 性质就发现两种方向可以拆开来，手摸发现每次操作形如将一段区间挖空，放到该区间后面，想到了脑洞治疗仪，上个线段树二分即可，写起来比较史，最后写了 $250$ 行，$n=2e5$ 死活过不去，仔细阅读代码逻辑没什么问题，一测是 $\text{RE}$ 了，此时已经过去了三个小时，我有两种选择，卡动态开点空间获取可能的 $\text{100}$，或者暴力已有的 $\text{80}$ 分去打后两题暴力，结合早上的分析，我选择了后者。
对于 $\text{T2}$，看范围一眼指数级算法，考虑枚举，前 $12$ 分是简单的枚举所有边的选择情况。对于边权不同的情况，最小生成树一定，对 $n-1$ 条边枚举方向，其余边乱选即可，也比较好写。$w_i=1$ 的情况只需要保证有一个点入度为 $0$ 即可，推着推着发现需要容斥，看了下剩余的时间，先跳过去了。
$\text{T3}$ 完全没有思路啊，时间剩的也不多了，输出一跑路了。
预计得分 $[80,80]+[12,24]=[92,104]$。出考场发现人均 $\text{100}$，打的太保守了，有可能因为 $\text{Day 2}$ 不够高而挂出去省队。
由于可能下暴雪，所以吃完饭就润了，下周要考中科大少年班，物理咋考这么难。
# DAY 3
上封面了：
正在享用 $\text{d2t1}$ 的大样例：
