专栏文章

2025 XCPC 游记合集

__mi_ka_
生活·游记参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mjojvgvr
此快照首次捕获于
2025/12/28 01:04
2 个月前
此快照最后确认于
2026/03/08 01:30
3 天前
查看原文
可以点击这里以获取更好阅读体验。

人物介绍

这里面能出现的人物基本上只有我们队，我来简单介绍一下我们队吧。
我们队：弱省弱校 ACM 队：内蒙古大学 等我长小了也要打OI。
YZB\text{YZB}：主包本人，一个蒟蒻 OIer，现役 ACMer，队长，在队中任 Coder 一职。
David\text{David}：队友，浙✌🏻一枚，无 OI 基础，比我还清楚我代码的旁观者，在队中任 Hacker 一职。
小登：队友，虽然叫小登，但是我们仨都是一届的，也无 OI 基础，思路清奇，在队中任 Ideaer 一职。

5.24 CCPC 东北赛 热身赛\text{CCPC 东北赛 热身赛}

我们学校每年一度的运动会又又又又下雨了！！！
由于我是 23 号下午的飞机，所以我找班长把我的运动会志愿者任务调到了 22 号。不出意料的是 23 号真就下雨了，我们学校能够在提前半个多月精心选择一个下雨的天气用来开运动会，有心了 (bushi。
呼市下着雨，两个小时后到达了长春龙嘉机场，反而是晴天，并且还伴有落日。于是我第一次来到了东北，来到了这个遍地东北人的城市。
一行 12 人，分批次到达。我到达时我在这次比赛的室友已经提前到了，于是我便直接登记入住了。
晚上跟他们一起去吃了酒店旁边的一家烧烤，当时是 9 个人，因为剩下三个人还没到，那家很好吃，价格也很实惠。
时间到达了 24 号，热身赛日，我们先去拿了资源，每人一个编织袋，里面是赛服、胸牌和饭票，还有一个长春理工大学的茶杯。
由于饭票是每人每顿饭 20 元，我们 12 个人就是每顿饭 240 元，显然花不完，但是饭票又是限制于当前那顿饭的（饭票上有写哪一天的哪顿饭），所以我们把剩余的饭票集中到我和我室友的身上，我们去代为买饮料和面包，他们先去热身赛赛场了，我们买完去赛场分给他们。
等我们到达了赛场，热身赛已经进行了 40 分钟了，我的两个队友都没来打热身赛，派我过来看环境。
说起队友，这里我的队友还不是开头介绍的那两位，原因是报名东北赛时，我们队本来是报了的，但是我们三个都是大一，并且我们三个中只有我一个人在今年天梯赛中获得国奖了，所以教练不允许他们两个跟我组队打东北赛。于是，把我单独拉了出来，跟两个大三的老登组队（虽然我不知道能不能跟他们打出配合），队名也不是我们原本的队名。
在 A 了两道题拿了两个气球之后，我也就离场了，回去听铁匠他们队说这四道热身赛的题都是去年东北赛原题，于是他们速通了。

5.25 CCPC 东北赛\text{CCPC 东北赛}

正赛日。
我们四个队也是早起来到了赛场，但是因为赛方一些小 bug，比赛延时了 25 分钟，25 分钟之后，比赛正式开始。
G\text{G}：我掌 coding。于是比赛开始之后我先找签到题，看到了 G\text{G} 题比较短，于是直接读，读完发现是签到，上机直接打，0:05 AC\text{0:05 AC}。这时排名全场第 13。
A\text{A}：把 A\text{A} 题看完之后，看着不像很难的亚子，于是我想到了一个双指针的思路，显然这个思路我不会打，于是我把这个思路告诉了队友，让他上机去打。他若有所思的把这道题打完之后，交上去 WA\text{WA} 了一发。之后他仍然若有所思，然后推翻了我的双指针思路，无果。
K\text{K}：在队友打 A\text{A} 的时候另一位队友告诉我 K\text{K} 是签到，于是我拿着 K\text{K} 端详了一会，就有了思路，于是上机去打。打完了之后发现 K\text{K} 很自然的 WA\text{WA} 掉了，于是我拿着我的 K\text{K} 题下机，继续让队友打 A\text{A}。后来快两个小时的时候，打 A\text{A} 的队友告诉我，是不是最后那里 ii 和 jj 写反了，这个时候我才注意到确实是。改完之后 AC\text{AC}。要是 David\text{David} 在，他估计一眼就能看出来我的低级错误，这里卡了这么久。
F\text{F}：队友发现 F\text{F} 是签到，于是这道题就是他的了，我想 I\text{I} 题，但是后来我一看 F\text{F} 题没绷住，只见在黑白印刷的题面上赫然写着：
……可以发现，当指针转动到红色位置，……
这道题是一道小模拟，但是我队友没看出来，于是他想了一个神奇的小贪心去做这道题。然后就开始了他的石山代码之旅。这道题他打了很久，打的也很长，我在旁边看着他码，他说：
马上你就能看到这坨石山的的最终形态了。
—— cxy\text{—— cxy}
不出意外的出意外了，在很长时间的编写之后，这坨代码形成了，但是没有过样例。然后就是漫长的调试代码环节，另一个队友由于跟他经常组队，也跟他一块调了起来，我还在旁边看 A\text{A}。后来他俩不知道因为什么吵了起来，我作为队友，尴尬的用脚趾头扣出了三室一厅。后来快到比赛结束的时候，另一个队友上机重新打这个题，然后由于剩的时间太少了吧，他到最后一直在 WA\text{WA}，最后也没开掉。
H\text{H}：显而易见的是，H\text{H} 是二分答案，但是对于这个二分答案的 check 我不知道该怎么打，所以在这个地方我卡了很长时间，虽然有点小想法，但是不保真。快到比赛结束的时候，我们斜对面的一个队把这个题过了，然后说什么果然猜的这个结论是对的，我有了想尝试一下我的想法的想法，但是这个时候队友们在做 F\text{F}，我还是放弃了这个想法，毕竟时间也没剩多少，就算能打完，万一错了也没时间调了，更况且最后十五分钟我的脑子压根不知道我的手在打些什么东西。
本来以为这场没牌子了，毕竟就做了三道题，罚时还巨高，在我们一块去的四个队中排名最低，但是发牌子的时候发现，虽然我们没有邀请赛的牌子，但是有一个四省的铜尾：
拿过牌子晚上匆匆就走了，来回坐了两趟春秋航空晕的我第二天早八都没起来。

6.21 18th NMCPC 热身赛18^{\text{th}}\ \text{NMCPC}\ 热身赛

经过上周骑车来农大南校区误入东影南路神秘隧道导致走过的教训后，这周选择打车来农大。
也是轻车熟路的找到了农大计算机学院。发了物资，是浅蓝色 T-shirt 和农大计算机学院的宣传手册，还有参赛手册。
看了看，分为 105 和 203 两个机房来打，我们在楼下，我们学校的其他队伍都在楼上。
热身赛的题目很简单，让队友简单签完到之后，我就上场了，最后在 24min24\text{min} 成功 AK\text{AK} 走人。
里面有一道简单交互题，这给我一种明天要考交互的错觉，然鹅正式赛并没有交互。
走之前看了看其他队伍，听到别的学校惊讶于他们还没读完题我们就做完了，感叹于 NM\text{NM} 的算法竞赛的落后。

6.22 18th NMCPC18^{\text{th}}\ \text{NMCPC}

本部分内容抄自知乎我的回答。
比赛外榜
题目依旧是不难，但是实力不足，季军遗憾离场。
题目大致难度：CAK/EG/IBHF/DJ\text{CAK/EG/IBHF/DJ}
比赛开始时才开始发题册，还因为题册数量是一人一份还是一队一份耽误了一点时间。
C\text{C}：我是先根据题名找到的签到题，很签，0:03 AC0:03\text{ AC}，但是没有铁匠快；
K\text{K}：然后队友给我说 K\text{K} 题是差分，我看了一眼开始打差分，打了一半发现数据范围太小不用差分，暴力就能 AC\text{AC}，手忙脚乱中 WA\text{WA} 了一发，好在 0:08 AC0:08\text{ AC}，一血；
A\text{A}：另外一个队友说 A\text{A} 题是纸老虎，题目很高端，但是思路很简单，手忙脚乱又 WA\text{WA} 了一发，0:13 AC0:13\text{ AC}，又是一血；
队友让我去看 F\text{F} 题，我一看 F\text{F} 题好像是 DP\text{DP}，先跳了；
E\text{E}：又把题目看了一遍，再看还是没有其他队伍开掉其他题目，我去思考 E\text{E} 题，发现根号复杂度能处理，完事让 Hacker 造了几个数据测了一下，0:28 AC0:28\text{ AC}；
队友给我说让我看 B\text{B}，说 B\text{B} 好像是线段树，我试着打了一下 B\text{B}，然后发现题读错了，这道题长的像主席树，板子有点长，也不好套，先跳了；
G\text{G}：我去思考 G\text{G}，灵机一动发现这道题挺简单，前缀和+二分 1:04 AC1:04\text{ AC}，一血；
这个时间在榜单上还是第一，于是又不知道开什么题了，我这一个机房 105 还没有大佬，回头一开气球寥寥无几，于是很长一段时间卡在了五题；
H\text{H}：看到学长队开掉了 H\text{H}，发现 H\text{H} 好像可以离散化之后用线段树维护，两个多小时的时候被打假了，很难受，于是先吃发的面包火腿，让小登先打 I\text{I}；
B\text{B}：看到铁匠队优先开掉了 B\text{B}，我转念一想这题应该不会是主席树，于是另辟蹊径，队友告诉我可以统计每个操作所执行的次数，我想到了这个东西可以用线段树维护，最后用差分求出答案，因为一些细节 WA\text{WA} 了两发，3:31 AC3:31\text{ AC}；
I\text{I}：我开 H\text{H} 无果之后就让小登去开 I\text{I} 了，我去想 BDF\text{BDF} 这三道题，小登说 I\text{I} 题可以暴力，于是他就去打 I\text{I} 题了，但是非常恶心，题意中有一点小细节都没弄明白，于是越调越长，越调越 WA\text{WA}，最后也没 A 掉；
在这期间没有其他题被其他队 A 掉，于是我一直在思考无人问津的 D\text{D}，无果，F\text{F} 是 DP\text{DP}，不会写，摆烂了；
最后十几分钟队友要调我的 H\text{H}，但是时间剩的太少了，最终 66 题遗憾离场，好在做的 66 题里面有 33 道一血。
比赛完事跟同校其他队讨论了一下，发现我们学校包揽了冠亚季军，简单合了个影，去闭幕式了。
今年有滚榜，节目效果给足，闭幕式也是开的很成功。有一瞬间我是有一点沮丧的，但是转念一想我们三个都才大一，又欣慰起来了，大不了明年再战！

9.7 ICPC EC Online I\text{ICPC EC Online I}

第一场网络赛。
经过了暑假牛客多校和杭电多校的摧残训练，我们队的水平相对上个学期也有了不小的提升，这几场网络赛便是检测我们进步的第一弹。在这场网络赛前后，我们每周的周末大大小小有着十几二十场的区域赛真题 vp，我们的感悟是：还是区域赛真题卡手一些。所以我们对网络赛充满了期待的，期待我们队能拿到名额。
A\text{A}：一眼我就看到了 A\text{A} 题，这是一道大模拟，但是因为英文题面长，我也看不太懂英文，但是我可以很清晰的知道它讲的是 ACM\text{ACM} 赛制，所以我就按我打 ACM\text{ACM} 一来所了解到的规则去做了这道题，但是由于不好实现，所以是在队友把 G\text{G} 题过了之后我才去敲的这道题的代码。
G\text{G}：看到这个题过的比较多，翻译娘给出了这道题的翻译给小登，小登很快就出了思路，然后在得知我 A\text{A} 题还不会实现的时候，David\text{David} 就上机把 G\text{G} 题开了出来。
A\text{A}：然后我就上机去磕这道题，一个小时的时候就出了代码，也是不出意料的 WA\text{WA} 了，然后让 Hacker 给我出 hack 数据，出了几个数据，除了一个字符串输出的有问题之外（多输出了一个空格）我也没找到别的问题，但是这里我没当回事，在一次次修改代码，重新提交之后，我陷入了红温状态。
B\text{B}：知道 B\text{B} 是签到，但是交了好几发都是 WA\text{WA}。直到我红温了之后，我一气之下猜了一发 B\text{B}，居然意料之外的过了。
把人逼急了什么都能干出来的，过题也是。
—— YZB\text{—— YZB}
A\text{A}：David\text{David} 说要重打我的 A\text{A}，但是由于先入为主的缘故，他上机之后也没有更好的思路，于是还是放弃了，继续调试我的代码。时间来到了四个小时，我发现了我的代码里面隐藏的一点小错误，原来之前那个多输出的空格并不能忽略，那就是问题的隐藏所在，并不是字符串输出问题，而是我的代码里面出现了一个缺省值，字符串为空的一个变量混进去了，导致输出的时候先输出的字符串又输出了一个空格。改过来交上去过了。
I\text{I}：A\text{A} 题过了之后时间已经来到了 4:20\text{4:20}，这个时候我已经不太想继续开新题了，我开始摆烂了，直到大概 4:40\text{4:40} 的时候 David\text{David} 给我提出了 I\text{I} 的思路，是一个 Dijkstra\text{Dijkstra} 变种，这个时候我拿着试试的心态去打这个题，这个时候我根本就没想着要把这道题过掉，打了一个，交上去 WA\text{WA} 掉了，我开始质疑这个做法的正确性，然后 David\text{David} 发现了我的代码错误，更正之后 4:58 AC\text{4:58 AC}，意料之外，极限四题。
但是我们还是这场比赛的一队，只可惜我们的校排到达了恐怖的 346，与名额无关了。
本场前半场一直在坐牢，后半场才开始发力，甚至在封榜后过了两道题。在这之后我们继续进行卡手的区域赛的专训，希望下一次能不这么牢。

9.14 ICPC EC Online II\text{ICPC EC Online II}

9 月份的每一周的周末我们都被 vp 排满了，为的就是能在区域赛拿个名额。
转眼又到了第二次网络赛。
C\text{C}：开局看着 C\text{C} 像是签到，于是我想到了今年东北赛的 H\text{H} 的结论来做这道题，0:14 WA\text{0:14 WA}。之后便没再往这上面想，赛后才发现正解就是这个，而我在十四分钟叫上去的代码，只是少打了一个判断条件，可惜。于是这个题我们一直在尝试去用暴力解掉，由于数据范围小的缘故，这道题的暴力不会超时间，于是很长很长很长的暴力在我的手下出现了，显而易见的难调，调了整整三个小时，这道题才过，前半场同样的牢完了。
D\text{D}：这道题是一个神秘计数题，但是由于我们三个人组合数学普遍不好的缘故，这道题一直没推出来一个正确的权值。后来我就没打算推了，而是我去尝试找规律。我注意到了这道题的权值是一个 f1=1f_1=1 并且 fi=3fi−1+1f_i=3f_{i-1}+1 的神秘数列，写了过样例，交上去过了，还因为没开 long long 而 WA\text{WA} 了两发。
E\text{E}：其次就是这道题了，这是一个异或题，我的异或显然是我的弱项，所以我也采用找规律的方法，可惜这道题的做法不是很显然，我的规律到最后也没找出来，本剧终。
这场不是一队，是二队，我们的校排是 231，照样与名额无关，就等 CCPC\text{CCPC} 发力了。
经过了后面的几场加训之后，我们发现不知为什么，我们做 CCPC\text{CCPC} 总是没那么牢，于是我们对下一场 CCPC\text{CCPC} 的网络赛充满了期待，希望这次真能拿个名额吧，要不然这个赛季就提前结束了。

9.20 CCPC 网络预选赛\text{CCPC 网络预选赛}

中文题面！！！！！！
CCPC\text{CCPC} 网络预选赛，最后一场网络赛，要把握住。
E\text{E}：看到有人过了这道题，我就立马去看了，也是一眼出了思路，0:06 AC\text{0:06 AC}。
K\text{K}：虽然是中文题面，但是这道题的题面很难懂，申请中译中！我懂了这道题之后猜了一个结论，但是不敢全猜，而是用了个并查集把猜的策略的答案给算了一下，交上去 0:30 AC\text{0:30 AC}。
A\text{A}：小登开的 A\text{A}，这道题一开始我的思路假了，后来就重新想了，又没有头绪了，再后来小登给出了这道题的思路，但是说是柿子要我俩自己推，我俩推出来柿子之后写上去交上去直接 1:49 AC\text{1:49 AC}，到现在一发罚时没有。
G\text{G}：这道题过的确实是当时除了那三道题之外最多的，但是当时通过率不足 120\frac{1}{20}，我在想他们为什么这道题能 WA\text{WA}，因为我连 WA\text{WA} 的思路都没有。后来听到了对面桌的说了一句“根号”，我就往根号复杂度上去推的这道题，有了头绪，虽然算不出来实际复杂度，但是知道这个时间复杂度是带着一个根号的，想着这道题反正也不好过，实在不行打完这个暴力，TLE\text{TLE} 了之后再卡常，带着这个想法，我开始敲起来了这道题。但是交上去发现并没有 TLE\text{TLE}，而是 WA\text{WA}，于是我开始怀疑这个时间复杂度是正确的，等我改掉了我代码中的笔误之后，再交，真就出乎意料的过了。此时排名已经排到了 300 名以内，接下来的题不太是我们能做出来的了，其实到现在也才刚刚过了前半场，今天的前半场一点也不牢，反而是主要发力的时候。后来才知道我的这个做法，名字叫根号分治。
C\text{C}：队友还想开一道题，于是目光移到了 C\text{C}，是一个最小生成树的问题，最小生成树我只会 Kruskal\text{Kruskal}，在此基础上我没有头绪，于是就放弃了。赛后得知这道题需要用到的算法是 Boruvka\text{Boruvka}，这做不出来真不怪我了。
前两场排名一场 12951295 一场 12961296，本场排名 465465，超常发挥了属于是，校排 156156，我们队也是拿到了一个名额，后来学校名额分配的时候我选了哈尔滨，于是就有了一场哈尔滨之旅。

11.8 CCPC 哈尔滨 热身赛\text{CCPC 哈尔滨 热身赛}

前一天晚上的飞机，到达哈尔滨的时候已经过 1212 点了。
凌晨打车的时候发现这是一个“黑”车，车来了发现车并不是黑的，只有车牌号是 “黑A”。坐了很久发现打表变贵了，果然是个黑车，整辆车只有车不是黑的(bushi。
第二天睡醒已经十点了，准备去哈工大签到。外面下雪了，但是我不太喜欢雪，因为呼市冬天太多了。
先领了点物资（只有衣服、胸牌、队牌和红肠，而且三个人只有一个纸质手提袋），然后拍了一张我们赛场上的位置的照片（太远了，所以很糊），像这样：
然后去食堂吃了饭，吃完饭跟哈工大的高中室友见了面，然后聊了会就开幕式和热身赛了，热身赛签到很快：
但是被后面一个神秘哈希题卡了一会，我们没有用数论的哈希，而是有一个小小的贪心然后类似于暴力过的。打完热身赛拿了两个气球就带着球去玩了。
晚上一起吃了烧烤，不得不说哈尔滨的烧烤还是不错的。

11.9 CCPC 哈尔滨\text{CCPC 哈尔滨}

由于现在已经到达了冬天，外面还下了雪，并且赛服还是 T-shirt，进入赛场的时候一股寒意袭来，队友笑着调侃到：一会打题打红温了就暖和了（这一语成箴是我没想到的）。
题册发了下来，我从头往后看了一眼题目，发现基本上都不是很签。当我翻到 J\text{J} 题时，发现这是一个神秘字符串题，看起来好像不难的亚子。
J\text{J}：好像是回文串问题，这让我一眼想到了 Manacher\text{Manacher} 算法，这个时候我就想：是否能将题中的一个 w 当成两个 v 来看呢？
A\text{A}：十分钟左右，有队伍过了 A\text{A} 题，这个题长的一点不像签到，它能是签到吗？我看完题思考了片刻，无果，后来注意到了一个同余式子成立，但是还是没有想法。大概在 20min20\text{min} 左右的时候，听到了不知道哪个队说了一个“差分”，发现这题确实是差分。上机去打，样例过了，交上去 0:28 WA0:28\text{ WA}。后来发现输出 Impossible 的时候没有换行，而样例中的 Impossible 正好是在最后一组输出中，所以 VSCode 给按 AC\text{AC} 了。出师不利，此时心态已经出现了一些变化。
G\text{G}：思考 A\text{A} 的时候问了一下小登在看 G\text{G}，当时 G\text{G} 全场已经交了好几发，但是没有人过，这让小登把自己的错误思路给 hack 了。后来我打完 A\text{A} 题之后去看 G\text{G},此时 G\text{G} 已经有了好多过的了，我一眼想到了二维前缀和，但是后来自证做法是错误的。想到了这道题有一个贪心，但是直接贪心时间复杂度太大了。想了好久我发现可以用链表来优化，然后将时间复杂度成功降到 O(n×m)O(n\times m)，但是这道题的链表情况有点多，对我来说有点吃玛丽，于是在一个半小时才过这道题，此时名次已经靠后了。
L\text{L}：我打 G\text{G} 的时候小登在看 L\text{L}，我打完听小登讲了一下 L\text{L}，看到数据范围蛮小的，一开始我还在思考什么算法的时间复杂度能顶到这个时间。后来想到了一个暴力算法，仔细一想，时间复杂度还真能顶到时间限制，于是我开始打这个暴力（BFS\text{BFS}）。打着的时候就发现不对劲，需要特判的东西好多啊，很弯弯绕绕，还特别卡手。打完之后果然过不了样例，于是进入了漫长的调试代码阶段，这个电脑上的 VSCode 昨天用的时候是能调试的，今天打开调试界面之后直接卡退，之后便再没敢动过这调试，于是：肉眼调试开始了！时间过去了好久，还是没有任何进展。这个时候小登又提出了一个小贪心，让这个算法的时间复杂度降了下去，同时也比这个代码要好打很多。于是我就重新开了一个 LL.cpp 去打新的代码，不出意外的是，代码打出来以后也是同样的没有过样例，又要调。这个时候我头有点晕了（十二点半了，我还没吃东西），小登说他的 K\text{K} 题要猜一下，于是我下来打印了代码，继续肉眼调，调完之后样例终于过了，交上去一遍过，此时已经快一点了。
K\text{K}：在我打 L\text{L} 的期间，小登其实是在看 K\text{K} 的，在我头快调炸掉的时候（这个时候即使穿着 T-shirt 也感觉浑身冒汗），小登要上去猜一发 K\text{K}。当时他就上去写了，样例过了直接交，奈何 WA\text{WA} 的飞快然后又让我把 L\text{L} 改完了。我过了 L\text{L} 之后看了一眼 K\text{K}。是一个背包为背景的神秘构造，当我读题的时候：“第一行输出构造的物品总数 nn，第二行输出 nn 个整数 w1∼nw_{1\sim n} 表示物品的体积，第三行输出 nn 个整数 v1∼nv_{1\sim n} 表示物品的价值……”小登听到后恍然大悟，上去改了代码，就过了。原因是他的物品输出了 nn 行，每行两个整数 wiw_i 和 viv_i，那为什么样例过了呢？请看样例输出：
IN
2
1 2
2 3
这个横看竖看一模一样，于是在这里出了乌龙，交了一发罚时。
I\text{I}：这个题是六边形的三维坐标上的题，在暑假打杭电多校的时候遇到过类似的题，那个题当时是猜性质题，当时也没做出来，这个题看起来也没啥欲望，但是这个是除我们开掉的四道题里面开掉的人最多的，于是转向第二多的题 J\text{J}。
J\text{J}：这道题我从开局就有想法，当时全场没有任何提交，于是我也就没去试这道题。现在转过来做这道题，时间还剩 4040 分钟，当时是处于一个很紧张的状态，我遇到了第一个问题：由于是一个 w 当做两个 v 来看的，那么做 Manacher\text{Manacher} 之后的最大回文串在原始串中可能不是最大。David\text{David} 提出来一个思路：将变化的 w 下标打上标记 1，然后预处理前缀和，通过回文串的区间和就知道这个区间有多少伪装的 v。我让 David\text{David} 给我把 Manacher\text{Manacher} 板子给我抄上去，我休息了一会。然后我打完这个题一看没过样例，于是知道了第二个问题：回文串的其中一端正好是 w 的中间，这个时候没有办法将其作为原始串的回文串，于是开始想办法“缩 w”。因为现在也没时间了，直接暴力“缩”的 w，交了好几发我以为可能 TLE/AC\text{TLE/AC} 的代码，发现要么 RE\text{RE} 要么 WA\text{WA}，这个时候我知道我的暴力缩 w 打错了，但是没时间调了，想着这个时间复杂度也不太可能过，就放弃了。
稳铁了，我长叹了一句“尽力了，实力不足，尽力了就没留遗憾”。
Fun Fact\text{Fun Fact}：讲题的时候，I\text{I} 题的结论是一个特别短的结论，这没猜出来可能有点可惜，但是这个不算什么。J\text{J} 题的正解做法跟我们遇到的两个问题一模一样，解决方法也大致相同，我们没调出来，快遗憾死了。离铜牌擦肩而过。毕竟第一次带队出来打比赛，我们学校的另一支队伍在同时的 ICPC 南京\text{ICPC 南京} 也拿到了铁牌，这就使我心理好受些了。想着来都来了，晚上去吃好吃的！吃了一顿烤肉自助，回去复盘。
附：提交记录（两发罚时都糖完了）。
附：四个气球（由于 K\text{K} 题是封榜后过的，这个紫气球是借的别的队飞来的）

12.6 CACC\text{CACC}

第一次参加 CACC（其实是冲着午饭去的）。
第一题是一个特别简单的高精度题，直接用 JAVA 调用 BigInteger 来做就秒了；第二题是奇妙版过河卒，也是很快的秒掉了。
做了两道题之后后面的题就骗不到分了。第四题写了点缩点+拓扑，交上去发现全 WA\text{WA} 就没再尝试了。
午饭是 KFC！！！吃完就离场了，去逛了逛南区，又去了海亮。

12.7 40th CCF-CSP40^{\text{th}}\ \text{CCF-CSP}

在第 40 届 CCF-CSP 现场。
这一天其实也是百度之星现场赛的，我百度之星也报名了，但是碍于一些原因最终选择了来打 CSP\text{CSP}。
本次题目比上次(第 36 次)难了好多。
第一题就是个神秘小异或。虽然能一眼出思路，但是还是被卡了十分钟才打出来，一遍过。
第二题又是个神秘小异或，一开始忘记异或的性质不知道这题怎么做，后来盯着题看了一会，才知道可以用异或来反向求出原来的输入，虽然输入有高达 n=105n=10^5 个，但是注意到输入最多只有 0∼29−10\sim 2^9-1 这 512512 种，所以将 kk 序列输进来之后直接预处理所有可能的输入的答案即可，时间复杂度 O(512m+n)O(512m+n)。交上去一遍过，届时 14:0314:03，比赛已经开始了半个小时。
第三题是个模拟，每次 O(Z2)O(Z^2) 的直接模拟会超时，观察了 2020 分钟后发现题目有个很好的性质：除了最大块的旋转以外，剩下的小块操作不会超过 10×1010\times 10，于是用一个全局变量来存储大块转了几次，在什么位置，写一个函数对于大块在所有位置都能将操作坐标转化为当前坐标，就过了，跑的飞快（时限 1.5s1.5\text{s}，实测最慢的点跑了 13ms13\text{ms}）。交上去一遍过，此时时间已经到达了三点。
第四题是个神秘计数题，我本来今年是冲着 400pts400pts 来的，于是一眼就看上了 80pts80pts 的暴力，想了一个 O(n×d(n))O(n\times d(n)) 的做法，想着能过 10510^5 的数据点，但是交上去前 80pts80pts 是 WA\text{WA}，后 20pts20pts 是 TLE\text{TLE}，我很久才意识到事情的不对劲，我的算法打假了，于是我又修改了，时间复杂度更大了，变成了 O(∑i=1ni×d(i))O(\sum_{i=1}^ni\times d(i))，只有 30pts30pts 是 WA\text{WA}，剩下全是 TLE\text{TLE}，再一看前 30pts30pts 是 n≤10n\le 10，一怒之下打了 n5n^5 的暴力，AC\text{AC} 了 30pts30pts，又用暴力打表找了好长时间的规律，无果。
当我意识到还有半个小时的时候，我开始阅读了第五题，第五题有 20pts20pts 的暴力特别好打，于是花了 20min20\text{min} 去打了这个暴力。
最终得分 100+100+100+30+20=350pts100+100+100+30+20=350pts，比去年低了整整 10pts10pts。赛后看了眼榜，赫然在 72007200 多人中排名第 4141 名，这是意料之外的。最后证书发下来，发现在本次认证中排名前 0.39%0.39\%，这又是意料之外的。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...