SX2021 游记

· · 个人记录

SX2021 游记

Day -1

直接从杭州飞到了南昌，到 jxsd 卡了半小时的门禁（氧化钙冻死我了,jxsd 保安真的是太极高手，懂得高深的交谈科技），到了会馆住下来，晚上打了打雀，没想到上了雀豪（好的开始！）。

Day 0

躺尸（睡）了一个上午+一个下午，晚上开始打了打板子，24:00 就睡觉了。

Day 1

早上 7:00 整起床，感觉良好，检查了一下笔、带的零食，最后在学弟的提醒下带上了身份证（qwq）。在 Uoj 和 LA 群 跟刷了 rp++。会馆吃了早饭（其实并不好吃），就去考场了。考场 8:10 进场。

找位置坐了下来，发现登录不了 noi linux，问了工作人员才知道密码是 1234567。

顺利登录了，打了 vim 配置、快读快写、对拍板子就差不多到 8:30 了。顺利下载了题目。

打开压缩包一看，很好，有大样例。一如既往的 B 卷。顺序浏览一遍题目，发现 A(pair) 是个 sb 题，B(card) 暂时没有思路， C(graph) 看起来很神。

花 5min 把 A 给切了，开始想 B 题。一开始想二分极差，钦定最小值，发现不可做。然后发现决策区间有单调性，可以直接 two-pointers 线性做掉，花 20min 打了正解。一测大样例，过了！

这时已经 9:40 了，赶紧打了两个拍，测了测 A 和 B，都过了拍；又测了测极端数据，都成功通过，放心地把 A 和 B 封印了。

10:10 开始搞 C 了，还剩 2 个小时零 50 分钟，时间充裕得很。

一开始觉得，这题好简单啊！然后才发现，我把 “路径” 看成了“直接相连”，好的，我重看。

发现所谓的 “从 u 到 v 的路径与从 v 到 u 的路径都存在” 等价于 u,v 在同一个强连通分量中，直接暴力重构 scc 可以做到 O(mn(n+m))。想到这已经是 2h 以后的事了。赶紧打了一个，打得太急，实现不够精细，希望可以给满 44 分吧。

预计分数 216~244。

出考场一问，好像大家都过了 C （瑟瑟发抖）。吃了个饭回到宾馆，打开群一问，还好还好 qwq。

下午写了写游记，继续打了打板子。

小插曲

晚上 01:00，肚子疼睡不着，起来吃了包药，惨。。

Day 2

噩梦的一天开始了。。

一大早起来，又吃了药，宾馆吃早饭，一样地去了考场。

今天进场早，昨天的模板还留着，于是打了个树剖lca，SA，SAM。

开题先看 A(mod)。。这怎么和某入门组的题目这么像啊，看来也是个sb贪心。。信心满满地敲了一发，一拍，WA了。然后冷静一下，发现不太对劲。然后。。我就只会 O(n^2\log n) 了，60pts。考场上脑抽，瞎搞都没写，已经9:30，爬了，去开 B。

B(gem)，感觉是个树剖啥的，然后发现一点也不好维护。考虑到序列上的做法，是找到前驱。在树上查询 (u,v) 时，可不可以拆成 (u,lca) 和 (lca,v) 两段，分别跳 pre 呢？前一个问题可以方便地用倍增 pre 数组维护，后一个呢？？想了 1.5h 没想出来，写了个 O(nq) 化链为序列，爬了。。25pts。

C(ranklist) 先信心满满地写了个全排列+贪心，然后怎么也过不去样例。。这样纠结了 2h，考后才发现读错题了qwq。0pts。

Day 2 预估： 60+25+0=85。

出考场时，心里只有两个字：完了。

下午就返程了，从南昌回赣州，水群。很难受，这可能是我心里最不好受的一天吧，想到了这篇文章：

如何优雅的和竞赛分手

唉。。

最后在群友的鼓励下，还是又有了希望。民间数据测了一下 329，noip 194，在 jx 还是可能进队的吧。

两个 if 线：

（完）