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。 出考场时，心里只有两个字：完了。 --- 下午就返程了，从南昌回赣州，水群。很难受，这可能是我心里最不好受的一天吧，想到了这篇文章： [如何优雅的和竞赛分手](https://littlered.blog.luogu.org/ru-he-you-ya-di-hu-jing-sai-fen-shou) 唉。。 最后在群友的鼓励下，还是又有了希望。民间数据测了一下 329，noip 194，在 jx 还是可能进队的吧。 两个 if 线： - 如果我进队了，我就继续冲 noi，去见见余姚的美好风景，去见见全国各地的大牛们； - 如果我没进队，那么下一篇文章（可能也是发在博客里的最后一篇文章）将是《OI生涯回顾》，以及：  （whk万岁！！！） （完）