🏀🏆A组第二场🐉🧱赛场游记

LittleYang0531 · 2025-04-26 20:22:19 · 生活·游记

🏀🏆A组第二场🐉🧱赛场游记

day -n

你🐉搞了个🏀🏆校赛，这个校赛是考完了直接出成绩的，也算是本人上了大学以来第一次重新搞算法竞赛的比赛。

具体细节忘了，但有一道题我记得很清楚。学校选了道 [NOIP 2001 提高组] Car 的旅行路线 作为防 ak 题。没错，确实是挺防 ak 的，甚至数据范围都没写，我还得猜这个题的数据范围是多少。

当时我考场上怒码 100+ 行，样例过了，发现时间复杂度大概是 O(n^2)，就把 MaxN 设置为了 1000，结果提交后发现全部答案错误得了 0 分。赛后我想补个题吧，就先把赛时代码（最后考试结果会有赛时代码）交到洛谷上看看哪里错了。结果您猜怎么着，洛谷全过了，而且洛谷的数据范围只有 100。这个时候我才反应过来不是我代码错了，而是他数据错了（真正意义上的防 ak 题）。

晚上我就去找程序设计老师去问咋回事，想把这 10 分加回来（加回来就从 80 变成 90 了）。就这么搞了快一周了吧，学校的回复是：

本次校赛中第六题“Car的旅行路线”系统内部测试程序有问题，经与蓝桥杯备赛系统负责人沟通并查看全部试卷，所有同学第六题均未得分，该题目不会影响到校赛排名，请大家放心。

六百六十六，盐都不盐了。你数据都是错的能有人得分吗😅。后面还是一个没过的学长提出了异议，才让学校重新审核了一遍，最后把我这 10 分加回来了。

最后考了 90/100，搞了个全校第一，🏀🏆的 300 块报名费学校报销了。

day -14

本来是今天举办比赛的，结果大风来了，学校听课了，🏀🏆自然也就没搞了。

但有一说一这风哪里大了？还不如平时周末的风大呢😅。

day -6

当天打了北京市程序设计大赛，有幸去小米转了一圈，也算是算法竞赛的恢复训练。比赛前还以为北京市校队前十五很容易拿，结果当做完四道题的时候一看，诶刚好排 17，就差两名，遗憾打铁。

在总榜里面最终排名 62/60，离拿牌就差两名。只要少吃两发罚时或者早点看出来 T5 的低级错误，就能把北林和北化挤下去，说不定就能拿牌了。哎，后悔死了...

打完了老登带着我们在小米里面转了一圈（没错🐉🧱的 ACM 没有教练，全靠老登带），亲眼见到了 su7ultra，也算是满足了。

后面跟老登聊天的时候才发现今年已经是🐉🧱距离拿牌最近的一次了，明年老登就要毕业了，后面得我自己找队友打 ACM 了。

回学校了晚上还去考了场高数，结果高数也崩了，哈哈...

day 1

头天晚上上完程序设计课就回来和朋友聊 QQ，一聊发现都到凌晨 1 点了，于是赶紧定了个 8 点的闹钟睡了。早上 8 点听到闹钟声音了，心想有点早，转头就定了个 8 点 20 的闹钟，就又睡了。还好 8 点 20 的闹钟把我叫醒了，赶紧洗漱，在 8 点 40 到了考场。50 分的时候突然收到两个朋友的消息说他们睡过了，简单和他们聊了两句催他们赶紧来就把手机收了准备考试了。

一开始去系统下题目，一个 100 多 kb 的题目压缩包愣是下了一分多钟（Windows 真有你的，扫个文件扫了半天），下下来了发现没有默认打开方式，最后问了监考老师才发现可以直接右键菜单有 7-zip 可以解压。

过了两分钟终于打开题了，这个时候监考老师才准备发草稿纸。

T1

观察可得 240 \mod 3 = 0, 250 \mod 50 = 0, 200 \mod 4 = 0，直接用大体积 240\times 250\times 200 除以小体积 3\times 4\times 5 就是答案了。

用 Windows 自带的计算器算一算就知道是 200 了。

讲个笑话，我 200 都算出来了这个时候监考老师才给我发草稿纸...

T2

一眼假设 n + 20255202 = x^2, n + 10244201 = y^2，两个等式做个差发现 x^2 - y^2 是个常数，直接找因数就可以了。

后续查的时候发现没有判断 n 是否为正整数的条件，判断了一下答案就是 14。

T3

看了看题，这不就是判断有多少个 i, j 满足 i + j = 1, 5\mod 7 嘛。

然后一看数据范围，1\leq n, m\leq 100，你认真的？

个人感觉这个题比 T2 还水...

T4

当时第一反应就是直接找最左边的 A 和最右边的 B 消掉，直到消不掉位置。用个双指针就出来了。

后面复查代码的时候把这个东西看成括号序列了，结果写一发发现样例都过不了，这个时候才反应过来不对，重新证明了一下才发现我一开始的思路才是对的。证明如下：

由题意可知最后剩下的一定是一堆 B 加上一堆 A 组成的字符串。要想这个字符串最长，也就是要左边的 B 越长越好，右边的 A 越长越好

很显然每次消最左边的 A 和最右边的 B 会使得最左边的 B 和最右边的 A 留下来的数量越多。

好久没写过证明的东西了，大家看个乐就好。

T5

这不是个 DFS 板子吗？🏀🏆你逗我玩呢😅。

随便用 DFS 求了个深度，然后判断每个点的深度是否小于等于 2\times k。编译一发，样例过了，下一题。

T6

看一眼数据范围，1\leq n\leq 1000，那应该就是 O(n^2) 或者 O(n^2\log n) 的算法了。

显然这个东西可以用 KMP 搞（应该吧），但是鉴于我不会 KMP，于是写了个单哈希。

发现子串数量不多，直接用 m[i] 的 map 存前面的所有子串中长度为 i 的哈希值及其对应的长度。

写的很快啊，大概五分钟就搓完了，调了十分钟，样例过了，走了。

后面大概 2h 的时候回来把单哈希加强了一下，搞成了双哈希。又随便写了个暴力和数据生成器，手动造了几个 100 的数据拍了下，发现没问题就继续想 T8 了。

赛后交洛谷的时候，一开始发现 A 了，然后才反应过来我洛谷默认开了 O2，关了之后发现 T 了 3 个点，应该是 map 的常数太丑了。哎，大概率这题要挂点分。

T7

这个 2^{32} 的限制很有说法啊，如果不输出 OVERFLOW 的话，显然最多只会有 32 个不为 0 或 1 的数乘起来。

很容易就想到把好几个连续的相同的数压缩一下，然后随便写个栈就完事了。这个题也没写多久，就是细节有点小多，大概十五分钟就调完走了。

赛后交洛谷的时候发现 WA 了，一看是所有答案为 0 的我却输出了 OVERFLOW。没花多久时间就构造出下面的数据成功把我卡掉了：

4
1 0
1 65536
1 65536
3 3

答案应该是 0，但是我的程序发现前两个数乘起来已经超范围了，就输出了 OVERFLOW，但实际上后面还有个 0，会导致最后乘积式结果为 0。

这个错误很好卡啊，只要随便在数据中放一个上面构造的 hack 数据轻易就能给我卡成 0 分。寄咯，哈哈...

目前没想到怎么改这个方法能够处理好这种情况...

T8

讲个笑话，我做到 T8 的时候时间才过去了 55 分钟的样子。

看一眼 T8 的题面，完全没有任何思路，预估是省选难度的题目。当时就觉得完了，这套题绝对没有什么区分度，要是做不了 T8 我一定完蛋了。

想了半个小时，当时的想法是差分约束。由于我不会处理负边权，干脆就先把所有负边权全扔了，然后又搞了什么拓扑，什么 dijkstra 来判正边环和求最小极差，最后再来讨论加上负边权的情况。写完了随便构造个数据就发现我的想法伪了。

这个时候大概已经 2h 了，回去检查了一遍前面的题，大概 15min，继续回来写 T8 了。

这次看了一眼部分分，m \leq 300，一点写的思路都没有。

又过了大概半个小时，我心想算了不建图了，直接用 O(n^2m) 的类似 SPFA 的算法跑一遍得了。T 了就 T 了，至少 m\leq 300 的部分分我还有嘛。

写完了才发现还有 0\leq r_i - l_i < 100, 0\leq q_i - p_i < 100 的限制。那很好了啊，这下时间复杂度不是直接进化成了 O(100n^2)？欸好像能过。

当时考场也想证明这个算法的正确性，鉴于本人实力有限，确实不会证明。这个题就处于一种我感觉他有问题，但我又说不出来哪里有问题；我感觉他没有问题，但我总感觉哪里怪怪的。但是我更多感觉的还是有点问题。

最后与其拿一个明显错误的算法交上去，不如就交这个算了，能骗多少是多少。

赛后重新写了一遍交洛谷，发现 A 了。应该是数据不够强，等后续洛谷加强一轮数据后再看吧...

赛后

最后检查了半个小时的样子，把万能头全部换了，还在 main 函数最后加了 return 0。

大概 12 点 40 的样子，交卷出去等朋友了。