依旧是前言
刚好赶着 2025 年的 csp,想着可以蹭蹭热度。又突然想到这类专题应该每个机构在考前都会讲,根本轮不到我,可是想到的时候我已经写好多了,果断决定放弃“#创作计划#”(笔者不想当小丑),继续硬着头皮写下去。
另外说明一下:如果您已经得到了 csp-j 1= 或是更高的奖项,那么您没必要继续阅读,因为笔者没有权力去教您部分分。
正文
事实上,如果您是一名 OI 的初学者,想要今年得到 csp-j 1= 的成绩,但因为实力问题,无法在赛场上场切 T3,但可以确保 AC 前两题,那么本篇文章将会非常适合您。
为了保证赛场上不要由于心态问题发挥失常,练习标准肯定要高一些,所以接下来我们就以强省(ZJ)为分数线 (主要原因是我是 ZJ
人) 进行练习。
例题
2025.06 GESP 八级 T2
口说无凭,我们以一道例题举例 - P13020,题目呢是今年六月份 GESP 八级的第二题,难度标的是绿,而去年 csp-j T3 是黄,所以只要能保证可以场切绿,在赛场 1= 可是轻轻松松。
可是不然,我们是蒟蒻,做不到,但也不能空手而归,所以即使无法 AC,也要拿点部分分。
先读题面,大致意思就是给定一棵无根树,求有多少种不同的 DFS 序。显然对于 n≤105n \le 10^5n≤105 的数据。如果只是枚举每个点为根进行树形 DP,复杂度为 O(n2)O(n^2)O(n2),显然过不了。但是我们可以过 n≤8n \le 8n≤8 的数据,这样就无脑获得了 404040 分的好成绩,再加上前两题的分数,共 240240240,在一些弱省中已经可以获得 1= 了,可是我们的目标是强省 1=,所以还不够。
再仔细读数据范围,容易发现还有 20%20\%20% 的测试点满足给出的无根树是一条链,由于笔者写的不是题解,所以对思路不加赘述,但事实上,如果您勤于思考,容易发现答案始终为 2×n−22 \times n - 22×n−2。那么这样我们就共得到了 260260260 的成绩,只需要在 T4 中得到 555 分即可获得 265265265 的成绩,就达到了 ZJ 去年 1= 的分数线。另外再说明一点,去年 T3 的难度为黄,而刚刚的例题难度为绿,所以真正在赛场上我们可以在 T3 取得的分数 ≥60\ge 60≥60。
2023 CSP-J T4
当然,如果只是用 GESP 的题目,显然不具备信服力,所以我又找了一道 csp 真题 P9751,这是 2023 年的 T4,该题部分分巨多,让我们一个一个讲。这里事先声明,当年 csp-j 1= ZJ 的分数线是 225225225,同样假设 AC 了前两题,所以我们需要在后两题中得到 252525 分。
对于这种存在 -1 又没有多测,显然可以直接输出,能拿多少看 CCF 愿意施舍多少,在这道题中可以得到 555 分。
对于 k=1k = 1k=1 且 ai=0a_i = 0ai =0 的情况,我们直接跑一个最短路板子即可,可以得到 101010 分,再加上上面的 555 分,共 151515 分。事实上当年 T3 可以非常轻易的得到 101010 分,如果这样我们可以获得 1= 了,可以分卡得这么紧,如果挂分就炸了。所以展示容错
另外这边笔者去年备考 csp 的时候写了一份 252525 分的代码,过的测试点非常神奇,由于自己忘记做法了,所以就贴一下代码(放附录了),读者可以自己思考一下(((
然后我们可以通过上述两份代码进行合并取并集,就可以得到一份 353535 分代码,具体代码也放附录了。
继续观察题面数据,容易发现对于 ai=0a_i=0ai =0 时,显然从 000 时刻进入园区时最优的,因为所有地点都没有时间限制。而当 k=1k=1k=1 则满足当走到园区门口时可以直接出来而不需要等待,可以用神秘 BFS 过掉。这样我们就可以得到高贵的 555555 分,就算 T3 爆零,就算 T2 挂 303030 分,我们依旧可以获得 1=。
朋友请注意,这只是 T4,如果我们 T3 也这么玩一遍,将会得到多少分呢?
实战练习
多说无益,还是让我们直接模拟去年的 csp 试试效果(您可以先自己做一遍,题目在题库里可以找到,记住,一定要模拟 OI 赛制,不要交太多遍)。
T1
用 map 或是 set 都可以做,这里就不讲了。
T2
别看题面长,其实难度比 23 年的 T2 简单多了,按题意模拟即可,不过记住多测清空(反正我有个朋友就是这样 T2 爆零的
T3
T3 往往都是决定 1= 的重头戏。
先是暴力的 303030,不要白不要。
然后注意特殊性质 A 和 B,都和 777 有关,这就暗示了正解的突破口将从 777 展开。经过肉眼观察容易发现,数码 8 所需火柴棒刚好为 777 且最大,去年坐在凳子上的笔者突然想到了一个很简单又很容易忽视的特点“比较数字大小优先比较数位”,换句话说,为了让数字最小,一定要先让数位最少,而让数位最少,就一定要保证每一位所用火柴棒最多也就是尽量用 8。那么就简单了,对于 n=7kn=7kn=7k,显然将每一位都放 8 最优,对于 n=7k+1n=7k+1n=7k+1,则选择先放 10,然后跟着放若干位 8。
再结合暴力的 303030 分,我们共得到了 808080 分,总分 280280280,这也就达到了笔者去年的水平。
然后再仔细想,正解就一目了然了,对 n%7n\%7n%7 的结果分讨。无奈的是,笔者写完 808080 分后将所有时间投入 T4 无果,在最后 555 min 想出正解思路,并超了 111 分钟写完了代码,这个时候监考员已经走到我身边,我根本不敢动,虽然代码写好了,但由于没有测样例,所以最终还是不敢按下 Ctrl+s,遗憾离场。
T4
md,T4 真毒瘤,这里就不讲了 (其实是累了)。
总结
只要在赛场上注意观察每道题的数据范围,即使不会也可以得到好看的分数,从而斩获 1=。
最后祝大家在今年的 csp 中常常发挥,取得自己满意的成绩!
代码
如果您需要上述六道题的 AC 代码,可以私信我,一般都会给出的。
附录
252525 分代码如下:
353535 分代码如下: