专栏文章

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

LLittleYang0531
生活·游记参与者 3已保存评论 2

文章操作

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

当前评论
2 条
当前快照
1 份
快照标识符
@mhze686d
此快照首次捕获于
2025/11/15 05:50
4 个月前
此快照最后确认于
2025/12/03 12:07
3 个月前
查看原文

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

day -n

你🐉搞了个🏀🏆校赛，这个校赛是考完了直接出成绩的，也算是本人上了大学以来第一次重新搞算法竞赛的比赛。
具体细节忘了，但有一道题我记得很清楚。学校选了道 [NOIP 2001 提高组] Car 的旅行路线 作为防 ak 题。没错，确实是挺防 ak 的，甚至数据范围都没写，我还得猜这个题的数据范围是多少。
当时我考场上怒码 100+ 行，样例过了，发现时间复杂度大概是 O(n2)O(n^2)，就把 MaxN 设置为了 10001000，结果提交后发现全部答案错误得了 00 分。赛后我想补个题吧，就先把赛时代码（最后考试结果会有赛时代码）交到洛谷上看看哪里错了。结果您猜怎么着，洛谷全过了，而且洛谷的数据范围只有 100100。这个时候我才反应过来不是我代码错了，而是他数据错了（真正意义上的防 ak 题）。
晚上我就去找程序设计老师去问咋回事，想把这 1010 分加回来（加回来就从 8080 变成 9090 了）。就这么搞了快一周了吧，学校的回复是：
本次校赛中第六题“Car的旅行路线”系统内部测试程序有问题，经与蓝桥杯备赛系统负责人沟通并查看全部试卷，所有同学第六题均未得分，该题目不会影响到校赛排名，请大家放心。
六百六十六，盐都不盐了。你数据都是错的能有人得分吗😅。后面还是一个没过的学长提出了异议，才让学校重新审核了一遍，最后把我这 1010 分加回来了。
最后考了 90/10090/100，搞了个全校第一，🏀🏆的 300300 块报名费学校报销了。

day -14

本来是今天举办比赛的，结果大风来了，学校听课了，🏀🏆自然也就没搞了。
但有一说一这风哪里大了？还不如平时周末的风大呢😅。

day -6

当天打了北京市程序设计大赛，有幸去小米转了一圈，也算是算法竞赛的恢复训练。比赛前还以为北京市校队前十五很容易拿，结果当做完四道题的时候一看，诶刚好排 1717，就差两名，遗憾打铁。
在总榜里面最终排名 62/6062/60，离拿牌就差两名。只要少吃两发罚时或者早点看出来 T5 的低级错误，就能把北林和北化挤下去，说不定就能拿牌了。哎，后悔死了...
打完了老登带着我们在小米里面转了一圈（没错🐉🧱的 ACM 没有教练，全靠老登带），亲眼见到了 su7ultra，也算是满足了。
后面跟老登聊天的时候才发现今年已经是🐉🧱距离拿牌最近的一次了，明年老登就要毕业了，后面得我自己找队友打 ACM 了。
回学校了晚上还去考了场高数，结果高数也崩了，哈哈...

day 1

头天晚上上完程序设计课就回来和朋友聊 QQ，一聊发现都到凌晨 11 点了，于是赶紧定了个 88 点的闹钟睡了。早上 88 点听到闹钟声音了，心想有点早，转头就定了个 88 点 2020 的闹钟，就又睡了。还好 88 点 2020 的闹钟把我叫醒了，赶紧洗漱，在 88 点 4040 到了考场。5050 分的时候突然收到两个朋友的消息说他们睡过了，简单和他们聊了两句催他们赶紧来就把手机收了准备考试了。
一开始去系统下题目，一个 100100 多 kb 的题目压缩包愣是下了一分多钟（Windows 真有你的，扫个文件扫了半天），下下来了发现没有默认打开方式，最后问了监考老师才发现可以直接右键菜单有 7-zip 可以解压。
过了两分钟终于打开题了，这个时候监考老师才准备发草稿纸。

T1

观察可得 240mod  3=0,250mod  50=0,200mod  4=0240 \mod 3 = 0, 250 \mod 50 = 0, 200 \mod 4 = 0，直接用大体积 240×250×200240\times 250\times 200 除以小体积 3×4×53\times 4\times 5 就是答案了。
用 Windows 自带的计算器算一算就知道是 200200 了。
讲个笑话，我 200200 都算出来了这个时候监考老师才给我发草稿纸...

T2

一眼假设 n+20255202=x2,n+10244201=y2n + 20255202 = x^2, n + 10244201 = y^2，两个等式做个差发现 x2−y2x^2 - y^2 是个常数，直接找因数就可以了。
后续查的时候发现没有判断 nn 是否为正整数的条件，判断了一下答案就是 1414。

T3

看了看题，这不就是判断有多少个 i,ji, j 满足 i+j=1,5mod  7i + j = 1, 5\mod 7 嘛。
然后一看数据范围，1≤n,m≤1001\leq n, m\leq 100，你认真的？
个人感觉这个题比 T2 还水...

T4

当时第一反应就是直接找最左边的 AA 和最右边的 BB 消掉，直到消不掉位置。用个双指针就出来了。
后面复查代码的时候把这个东西看成括号序列了，结果写一发发现样例都过不了，这个时候才反应过来不对，重新证明了一下才发现我一开始的思路才是对的。证明如下：
由题意可知最后剩下的一定是一堆 BB 加上一堆 AA 组成的字符串。要想这个字符串最长，也就是要左边的 BB 越长越好，右边的 AA 越长越好
很显然每次消最左边的 AA 和最右边的 BB 会使得最左边的 BB 和最右边的 AA 留下来的数量越多。
好久没写过证明的东西了，大家看个乐就好。

T5

这不是个 DFS 板子吗？🏀🏆你逗我玩呢😅。
随便用 DFS 求了个深度，然后判断每个点的深度是否小于等于 2×k2\times k。编译一发，样例过了，下一题。

T6

看一眼数据范围，1≤n≤10001\leq n\leq 1000，那应该就是 O(n2)O(n^2) 或者 O(n2log⁡n)O(n^2\log n) 的算法了。
显然这个东西可以用 KMP 搞（应该吧），但是鉴于我不会 KMP，于是写了个单哈希。
发现子串数量不多，直接用 m[i]m[i] 的 map 存前面的所有子串中长度为 ii 的哈希值及其对应的长度。
写的很快啊，大概五分钟就搓完了，调了十分钟，样例过了，走了。
后面大概 2h 的时候回来把单哈希加强了一下，搞成了双哈希。又随便写了个暴力和数据生成器，手动造了几个 100100 的数据拍了下，发现没问题就继续想 T8 了。
赛后交洛谷的时候，一开始发现 A 了，然后才反应过来我洛谷默认开了 O2，关了之后发现 T 了 33 个点，应该是 map 的常数太丑了。哎，大概率这题要挂点分。

T7

这个 2322^{32} 的限制很有说法啊，如果不输出 OVERFLOW 的话，显然最多只会有 3232 个不为 00 或 11 的数乘起来。
很容易就想到把好几个连续的相同的数压缩一下，然后随便写个栈就完事了。这个题也没写多久，就是细节有点小多，大概十五分钟就调完走了。
赛后交洛谷的时候发现 WA 了，一看是所有答案为 00 的我却输出了 OVERFLOW。没花多久时间就构造出下面的数据成功把我卡掉了：
CPP
4
1 0
1 65536
1 65536
3 3
答案应该是 00，但是我的程序发现前两个数乘起来已经超范围了，就输出了 OVERFLOW，但实际上后面还有个 00，会导致最后乘积式结果为 00。
这个错误很好卡啊，只要随便在数据中放一个上面构造的 hack 数据轻易就能给我卡成 00 分。寄咯，哈哈...
目前没想到怎么改这个方法能够处理好这种情况...

T8

讲个笑话，我做到 T8 的时候时间才过去了 5555 分钟的样子。
看一眼 T8 的题面，完全没有任何思路，预估是省选难度的题目。当时就觉得完了，这套题绝对没有什么区分度，要是做不了 T8 我一定完蛋了。
想了半个小时，当时的想法是差分约束。由于我不会处理负边权，干脆就先把所有负边权全扔了，然后又搞了什么拓扑，什么 dijkstra 来判正边环和求最小极差，最后再来讨论加上负边权的情况。写完了随便构造个数据就发现我的想法伪了。
这个时候大概已经 2h 了，回去检查了一遍前面的题，大概 15min，继续回来写 T8 了。
这次看了一眼部分分，m≤300m \leq 300，一点写的思路都没有。
又过了大概半个小时，我心想算了不建图了，直接用 O(n2m)O(n^2m) 的类似 SPFA 的算法跑一遍得了。T 了就 T 了，至少 m≤300m\leq 300 的部分分我还有嘛。
写完了才发现还有 0≤ri−li<100,0≤qi−pi<1000\leq r_i - l_i < 100, 0\leq q_i - p_i < 100 的限制。那很好了啊，这下时间复杂度不是直接进化成了 O(100n2)O(100n^2)？欸好像能过。
当时考场也想证明这个算法的正确性，鉴于本人实力有限，确实不会证明。这个题就处于一种我感觉他有问题，但我又说不出来哪里有问题；我感觉他没有问题，但我总感觉哪里怪怪的。但是我更多感觉的还是有点问题。
最后与其拿一个明显错误的算法交上去，不如就交这个算了，能骗多少是多少。
赛后重新写了一遍交洛谷，发现 A 了。应该是数据不够强，等后续洛谷加强一轮数据后再看吧...

赛后

最后检查了半个小时的样子，把万能头全部换了，还在 main 函数最后加了 return 0。
大概 1212 点 4040 的样子，交卷出去等朋友了。
11 点等到所有人都出来了，和朋友一起去吃饭去了，吃完了赶着去上下午的基础日语课了。

后记

感觉第二场的题比第一场简单太多了，搞不好一堆 ak 的。看了看知乎确实也有人说省一线搞不好要搞到 100100 去。
哎，希望🏀🏆的数据和 €€£ 一样水，这样我的分数不至于太难看。至于国赛？能进的话就进去玩玩吧，进不去只能明年继续和🐉🧱的同学竞争名额了。我想这个成绩大概率是进不去国赛的吧哈哈...

评论

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

正在加载评论...