2026省选游记

Associate_Entropy · 2026-03-07 14:51:38 · 生活·游记

::::info[let it go]

It's funny how some distance

Makes everything seem small

And the fears that once controlled me

Can't get to me at all

Up here in the cold thin air

Where I finally can breathe

I know I left a life behind

But I'm too relieved to grieve

Let it go

Let it go

Can't hold it back anymore

Let it go

Let it go

Turn my back and slam the door

And here I stand

And here I'll stay

Let it go

Let it go

The cold never bothered me anyway ::::

最失败的地方

D1T3 和 D2T2.

我能说什么呢。

D2T2 爆炸真实原因：

不是你 div 3 的归纳构造都跳省选考了你不炸了？？？

Day ？

AH 依然参加省选联考。

Day 1

这个 \texttt{T1} 好长啊，诶怎么是签到题，1 秒想到计算每条边成为轻边的概率，这个直接树上背包保证 \mathcal{O}(n^2) 的时间复杂度就行了吧。

好像要撤销，让我想想记录每个子树的最短链就行了。

有点细节我写了 1\space \texttt{h}。/ll

这个 \texttt{T2} 怎么串长这么小。

Half an hour later...

我好像会时空复杂度均为 \mathcal{O}(nk^2) 的做法了，让我们先建 \texttt{ACAM}，然后在上面做这个复杂度的 dp，直接 bfs 实现就行。

诶怎么没有 checker，诶怎么我的输出和 .ans 相同。

我想冲正解了，上面那个做法要记录总共出现了多少个串以及已经出现了多少个不是 s 的前缀的比 s 小的串。

能不能少记一个量？

我想到 \texttt{IDA*}。

但枚举串长却提前到达 k 个子串就没招了。

折腾了将近两个小时挣扎着去打 \texttt{T3} 暴力，然后回来先把 \texttt{T2} 暴力打了再把 \texttt{string4} 从 13 s 卡到 0.7s。

（实际上卡常写 unsigned short 导致挂了，白卡了）。

我想着强行根号分治但是失败了，诶好奇怪啊这个做法没有自然根号怎么会是呢？\color{white} ps: 为什么不想想\space \texttt{KMP}\space w

不管了最后半小时研究 \texttt{T3}，那几个特殊性质愣是一个都没看出来。

最后 100+75+12 遗憾下播。

Day 2

我还要打至少 150 分，加油！！！

这个 \texttt{T1} 怎么是交互还是区间 mex，看一下操作次数要 \le n。1 秒想到 mex 就是补集 min，那只要前后缀最小值正确就行了。

没有细节我写了 20\space \texttt{min}。/ll

然后？？？