联合省选 2025 游记

## Background

[去年省选](https://www.luogu.com.cn/article/r2gku3ia)标志着我 OI 新生涯的开始。今年省选标志着什么？

赛前思考：NOIP 二等奖如何在省选中翻盘？

答案：不需要翻盘，翻了也进不了。天哪这实在是太有道理了。

省选前一个月学习了网络流（是的你没看错这个时候才学的），封装了自己的 `mf_graph` 与 `mcf_graph`（当然都是 Dinic 实现，什么原始对偶算法我也不会）。这一个月内还学习了后缀数组等东西。~~当然最后一个都没用上。~~

## Day 0

到达北碚，和家人一起吃 KFC，把必应的 100 元消费券结算了。

下午去试机，做到的这台机子的键盘为什么是跷跷板？有点担心后面两天的键盘状态。

晚上复习了一下网络流和 SA，完成了 [\[CSP-S 2022\] 数据传输](https://www.luogu.com.cn/problem/P8820)，几乎清空了洛谷主页“尝试过的题目”，剩下一道题目因为 CF RMJ 坏了不能提交 /fn。

## Day 1

进场，键盘不是跷跷板，很好。

$10\mathrm{min}$ 写了个二分过了 T1，心想着好签啊，后面还有大把的时间做后两题，怎么输？

先看 T3，打完暴力后尝试 $\mathrm{ABC}$ 性质（就是链），做了 $30\mathrm{min}$ 屁都不会。转向 $n\le 2000$ 的 $\mathrm{C}$ 性质（一棵树），发现对于一个结点可以把所有儿子独立开——维护每棵子树的答案，合并时将这一堆序列按字典序排序（当然把根一起扔进去）；发现如果对于每个序列只记录头就能做到 $O(n\log n)$，特别好啊。接着来想森林，发现使用贪心的递归合并是对的，写一下发现大样例过了，哦哦哦那就是对的。$52$ 分到手。

附贪心递归合并代码：

```cpp
int pt=1;
auto dfs=[&](auto &&self,int u)->void{
  for(int i:V[u]){
    while(pt<V.size()&&i>V[pt][0])
      pt++,self(self,pt-1);
    p.emplace_back(i);
  }
  if(!u)while(pt<V.size())
    pt++,self(self,pt-1);
};
dfs(dfs,0);
```

剩下 $2\mathrm{h}$ 多做 T2，怎么输？

你还真别说，拼尽全力获得 $20$ 分，接下来屁都不会（写的 $20$ 分还是 $O(mq)$ 的，后面的点一个都不可能过）。~~到最后半小时急了，以至于忘记打假算了。~~

出场一问这个分数（$100+20+52=172$）不算太差，那就这样吧。

## Day 2

进场之后被告知座位跟 Day 1 不一样，急忙跑出考场再看了一下贴在外面的座位表。

赶回场地；键盘依然不是跷跷板，非常走运！

考虑到今天难度可能较高，使用八校模拟赛策略——倒开！后面的题目打完暴力就跑路，留下的时间全部用来冲签到。

上来开 T3，$1\mathrm{h}$ 狂砍暴力 + $\mathrm{B}$ 性质，有 $28$ 分，马上跑路。

接着开 T2，写了暴力 $12$ 分，然后 $\mathrm{B}$ 性质猜了个结论（输出 $\frac{n+1}{2^n}$）能过大样例了。获得 $24$ 分，做了一会儿 $\mathrm{C}$ 性质后意识到花了太久时间，果断跑路。

此时还剩 $2\mathrm{h}$ 给我做签到。想了想这个东西，是不是套个贪心就变成了 ABC371F？线段树二分一下就做完了！开始敲代码，$40\mathrm{min}$ 写 + 调完了，过了所有大样例、极限数据 $1.3\mathrm{s}$ 就没管了。

后面 $1\mathrm{h}$ 多猛冲 T2 仍然无果。省选两天都是败在了 T2 /tuu。

出场一问这个分数（$100+24+28=152$）不算太差，顺其自然吧。反正 NOIP 已经注定了结局。

## Day 3

文化课。

## Day 4

文化课。

意识到自己的 D2T2 结论可能是假的，估分 $-12$。

## Day 5

文化课。

## Day 6

文化课。

省选出分了，结论又变回真的了，分数 $+12$。最后 $324$，还可以的分数。应该有机会三倍队线吧。

分数被巴蜀 $532$ 老哥稀释没了。这下省选一分等于 NOIP 一分了 /ll。

## Day 7

文化课。