XCPC武汉游记

Jr_Zlw · 2025-11-05 14:54:22 · 生活·游记

武汉

Day -1

学了整天MAT3007，但是学习五分钟，划水两小时。

晚上考CSC4120，发现不会算时间复杂度，前面题大量宕机，好在后面的算法题很水，一个堆上bfs的作业题，一个分治双指针，一个2-SAT。过程写的很屎，光写写写了2h。但是有大四老登半小时就交卷了，畏惧。

Day 0

MAT3007不出所望的炸了，准备late drop。还好没有转移这门课的权重到期末，不然到期末直接一考挂科。

考完赶紧出考场找sky，结果sky才刚出宿舍（邪恶sky）。坐地铁赶到机场，卡着点上了飞机。

sky的同学开车来接我们。我社恐发作瑟瑟发抖，sky同学跟他讲话，sky竟然还在玩手机，太邪恶了。

在武大转了一圈，本来以为马上到酒店了让孙✌下来帮忙check-in，结果预错了时间让孙✌等了好久，邪恶sky。

总之在房间里孙✌拿了3大袋物资来分赃，然后洗洗睡准备第二天比赛。

Day 1

早上起来往体育馆去，走了一会看到有公交车顺路就直接坐了两站到西门，到体育馆的时候时间差不多，上了个厕所就开考了。

开局先看了 A，猜测是否是找循环节然后通过某种方式离线所有询问，但是并未进一步想法，感觉像是类欧的形式，但是就算真的是也不会写也没有板子，遂只能往其他方向看看有没有乱搞做法，但最后也没搞出什么来。

孙✌中间还把 J 丢给我看，以为是什么神秘哈希题，结果到最后鉴定为0人题，邪恶孙✌。

看得差不多发现F开始过的人多了，想到如果根据典中典贪心找到最少的点覆盖区间，然后直接在这些关键点上 \log_2 即可。写了写过了。

EM两道题孙✌和sky很快秒了。他们在看M的时候我看了下K，分析了一下答案的下界一定是考虑每种颜色，每种颜色内按位置排序，然后相邻两个匹配的总和（再除2，因为可以在往左边换的时候顺手把一个前面的东西换到后面去）。再拿样例验证了一下发现都是下界，猜测这道题一定能构造出下界的结果。又分析了一下 \sum |p_i-p_j| 一定是偶数，更加确定。于是考虑了一下会使得答案高于下界的情况，一定是把同位置的另一个数换到了比匹配位置更远的地方，于是发现如果从左往右左，每次只取下一次出现位置更近的那个数换过来就可以避免上述情况，然后拿multiset随便维护了一下就过了。

过完这题以后孙✌在看他最喜欢的纯血构造题C，我和sky在想H，但是交互题一直没对上脑电波，虽然想过 01trie 但是觉得 2n-2 的询问次数并不像是有 \log 在里面，于是直接抛弃了这个想法（可恶），然后宕机了很久。孙✌的C暴力打表出一个很优美的 3\times 3 矩阵，然后发现了规律，我和他验证了一下发现确实可行，考虑到我不擅长H这类的猜猜题，孙✌让我上机写代码，然后他帮忙想H。我写了一会能过大部分情况了，但是经过孙✌的验证被 3n+1,4n 等情况卡了，于是又调试了很久，找了很多个hack，最后才蠕动着过了。

最后半小时对着H还是没有想法，遂倒闭。本来还看了B，觉得是某种优化建图，但是神秘的是当时只想到怎么用单点建图而没有想到 2-SAT，而且B过的人少没敢继续想，赛后听到 2-SAT 线段树优化建图恍然大悟，但是回到深圳补题的时候发现各种各样的算法叠到一起写了一个半小时，仍然倒闭。