统一省选 2023 游记

· · 个人记录

乐。
统一省选。
凭什么是统一？
看不起康师傅？
喝冰红茶，我只喝康师傅。
？
统一老坛酸菜面。

春季测试 2023

这是我第几次　又提起「悲伤」
词汇的汪洋干涸　只剩「绝望」

去 \text{CTT} 挺有意思的，认识了牛逼室友 \text{mwr}。之后一直疫情闷在家里特别无聊。\text{WC} 状态不好不会 \text{A}，0+44+76。2 月初完全做不动题了，休息了 2 个星期才复健。做不动题没有有建设性的思考，没法思考难题，事倍功半只能摆。

在莫比乌斯环上随波飘荡
荡出一地的陈词滥调

休息的时候 3 天推完了《三色绘恋》，心疼墨小菊。文芷也有些心疼。差不多状态恢复了，训练比特智慧做得很是顺利。

曾说好要永远在一起
躺着看雪直到天晴

春测就在人大附考，好耶。\text{AB} 简单的，很快交了。\text{C} 线段不自交，区间 \text{DP}。9:25 交了 \text{C}。

$k=4$ 二元组集合 $S_i=\{(x,y)\}$ 各选 $1$ 个对满足 $x,y$ 极差均 $\leq\text{mid}$。对 $x$ 双指针，线段树维护 $y$。每个 $i$ 可行的 $\text{mid}$ 集合是 $\leq4$ 段区间的并，区间 $+1$ 问全局最大值是否 $=n$。存在 $1$ 时刻 $=$ 则 $\text{mid}$ 合法，一直 $\neq$ 则 $\text{mid}$ 不合法，$2\log$ 的。写了 $\text{zkw}$ 线段树。$11:50$ 交了 $\text{D}$，剩下的时间拍 $\text{C}$。$12:59$ 发现 $\text{B}$ 枚举上界只 $70$ 会忽略 $1$，$12:59:11$ 改到了 $110$ 交了上去。 > 而我如今 独自在叹息 你们又在哪里 最终 $\text{B}$ ```sqrt(n)``` 挂了 $5$ 分，其他没挂 $\text{D}$ 也没被卡常。$100+95+100+100=395$。 ## 统一省选 2023 Day 1 > 我想逃　逃到天台上 将与你初见时的第一首歌丢掉 考试周。周一去机房树上邻域数点。周二早上卡常过了，中午吃辣，下午嗓子不舒服，晚上感冒了。之后不去机房在家了。听说甲流恢复得快不是很慌，不过 $270$ 块钱买了 $2$ 包奥司他韦。周三一天都没发烧，周四喉咙就不疼了，周五完全好了。 > 越是因心有灵犀爱过的诗行 空旷的梦里越痛得荒唐 周三周四 $2$ 天《恋爱绮谭～不存在的真相～》。推理向 galgame，质量很高，推荐！废寝忘食从早玩到晚，眼睛直疼。这游戏很怕剧透，我就不发表评论了，只发癫。对不起我是陈墨单推。陈墨我的陈墨你带我走吧。《不存在的真相》不是大团圆结局，因为要出 $2.5$ 和 $3$。不过真的会有大团圆结局吗。我只认陈墨顾真真后宫。双倍的苦，当值双倍的甜。 > 白色宫殿 你的容颜 无法分辨 我看不见 前一天没背任何板子，晚上 $20:15$ 睡的。早上 $8:25$ 到 $8:40$ 先通读题目。$8:55$ 交了 $\text{A}$。 $\text{B}$ 每个连通块 $1$ 个界点。先做 $k=0$。直接枚举 $n$ 的因子 $d$，在 $d$ 的倍数 $\text{siz}(u)$ 处切，判一下连通块 $\text{siz}=d$ 和界点个数 $1$ 即可。每个 $d$ 答案 $0/1$。$m\geq n$ 时取出 $\text{DFS}$ 树，连通块一定是树连通块，仍在 $d$ 的倍数 $\text{siz}(u)$ 处切判一下。 > 回忆碎片 要怎么捡 > 才能重新回到那个冬天 再做 $k=1$。发现界点一定是树连通块，连通块则是 $u$ 并若干棵子树。$m=n-1$ 时树形 $\text{DP}$，$F_{u,x}$ 表示 $u,\text{Fa}(u)$ 都是界点将 $u$ 子树划分为 $x/x+1$ 的方案数。子树按 $\text{siz}$ 排序后，$u$ 带上的要么是一个前缀要么恰带 $1$ 棵。因此有值的 $x$ 是 $\mathcal{O}(\deg u)$ 的，计算答案也是 $\mathcal{O}(\deg u)$ 的（同时还是 $\mathcal{O}(\sqrt{\text{siz}(u)})$ 的）。 > 我的思念 化作诗篇 你的笑脸 要怎么能重现 $m\geq n$ 时仍取出 $\text{DFS}$ 树，$\text{Tarjan}$ 计算 $\text{dfn}$ 和 $\text{low}$。非树边的限制在界点连通块的头部和尾部判一下 $\text{low}$ 即可。整个题可以 $\mathcal{O}(n+m)$。不过场上实现简单一点。 $10:45$ 会了上述所有东西开始写，$11:15$ 调出了 $k=0$，$12:30$ 拍过了 $m=n-1$。然后一直在改 $m\geq n$，改到 $12:55$ 发现 $\text{lca}$ 没带上的那些子树忘了判 $\text{low}$ 了。没时间改了，$60$ 交上去坐以待毙。 > 在记忆的迷宫里我却找不到 当年和你一同刻下的约定 吃巧克力，喝红牛。场上键盘声有点吵。集中精神莽 $\text{B}$ 的时候脑海里就浮现陈墨和顾真真。陈墨。顾真真。出考场发现 $\text{C}$ 没开亏大了，大家都 $48$。今天 $100+60+0=160$ 很不理想。晚上我爸请我吃了湖南菜，$20:50$ 睡了。 $\text{upd}$：$\text{B}$ 初评成绩 $70$，反向挂分，开心。 ## 统一省选 2023 Day 2 > 我好恨　恨这脆弱得不堪一击的人 竟和曾经幸福的我同个模样 今天需要翻 $20\sim30$ 分，比较紧张。昨天的策略问题很大，今天不能再不打暴力了。看来我还是没有吸取教训！ > 从心到手到脚到最末节的发梢 每个细胞都在呐喊着念念不忘 $8:25$ 到 $8:40$ 先通读题目。$\text{A}$ 二维棋盘带障碍，红方 $2$ 枚棋子黑方不能后退还比较平衡，估计不是让你挖掘性质。果然 $n,m\leq10$，直接建出有向二部图。类似拓扑排序一下就做完了，自认为代码比较优美。$9:30$ 过了样例交上去了。 > 又是初春 岁月无痕 等待的人 消失无声 太喜欢 $\text{Alice}$ 和 $\text{Bob}$ 了。$\text{B}$ 是（一侧）$\text{deg}\leq2$ 的完美匹配，$\text{LOJ}$ 上见过，一眼树和基环树。按照特殊性质 $\text{ABCD}$ 思考。基环树 $2$ 种定向方式，$\text{Alice}$ 统计 $3$ 个值即可。树 $\text{Bob}$ 的决策是选 $1$ 个根定向，$\text{Alice}$ 每条边相当于子树 $+1$/子树补 $+1$，有些边需要决策，最大化点权最小值。 > 红色的线 划过指尖 让不存在的谎言都变成真 我赛时用的是 $\text{Arranging Tickets}$ 的做法，枚举 $\text{mid}-\text{cnt}$ 的值，每次每个点所需被覆盖的次数全局 $+\dfrac12$。当 $u$ 的次数 $>0$ 需被覆盖的时候贪心选覆盖 $u$ 的最大区间覆盖。不太会处理基环树，代码丑陋写得慢，调过平方交上去就到 $12:30$ 了。继续优化可以轻重链剖分每条重链双指针找最大区间做到 $1\log$，没时间写了，想着昨天的教训赶快开 $\text{C}$。 > 纵然只剩 短暂余生 愿你留下 痛彻心扉的吻 $12:45$ 会了 $\text{C}$ 的 $10$ 分暴力，$12:55$ 交了上去。$12:59:46$ 的时候发现数组开小了只开到了 $50$，$12:59:57$ 交了最后一发改到了 $300$，有惊无险。出来的时候最关心 $\text{C}$ 怎么样，发现大家都只会 $10$ 分松了一口气。 邻座缺考，比较清静。$100+72+10=182$ 貌似不错，应该翻进 $\text{B}$ 类了。 > 将有你的这一瞬凝结成永恒 一起迎接 下一天的清晨 下午一直在等估分，什么都干不了。云斗学院好像比有道小图灵快，哈哈。省选的难度还是在线的，感觉 $\text{Day 1 B}$ 有 $15$ 级，$\text{Day 2 A}$ 是 $12$ 级，$\text{Day 2 B}$ 是 $14$ 级。接下来一是需要提升水平提升代码速度，争取赛时做出这些题。二是需要多打模拟赛锻练比赛策略，学会在 $2$ 道困难题中取舍分配时间，尽量获得性价比高的分数。