主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
如何在比赛中进行暴力和骗分？
最后更新于 2025-07-31 10:33:34
作者
听取MLE声一片
分类
个人记录
复制 Markdown
查看原文
删除文章
更新内容
[旧版备份](https://www.luogu.com.cn/paste/80bmmxj4) ## 声明 本文主观性较强，可能含有口嗨，请谨慎对待其正确性。 本文针对于联赛，因为省选并不在我经验范围内。 这是[之前的版本](https://www.luogu.com.cn/blog/vegetable-MLE/ru-he-zai-lian-sai-hu-xing-xuan-zhong-jin-xing-pu-li-hu-pian-fen-post)，如果想看就去那看看。 前半部分（直到 NOIP2020）是在 21-22 赛季正式开始前写的，后半部分是在 22 年末以及 23 年初写的。这也算是把之前挖的坑给填好吧。全文写的比较小丑，请见谅。 为什么没有 2021 年？因为我 2021 年整一年都在自闭。 如果这对你来说有帮助，就点个赞吧。 一定要看后记。 如何在比赛中进行暴力和骗分？ ## $\text{Part -1}$ 目录 - $\text{Part 0}$ 前言 - $\text{Part 1}$ 心态 - $\text{Part 2}$ CSP-S 2020 - $\text{Part 2.1}$ 前置知识 - $\text{Part 2.2}$ 比赛分析 - $\text{Part 2.3}$ 实战演练 - $\text{Part 3}$ NOIP 2020 - $\text{Part 3.1}$ 前置知识 - $\text{Part 3.2}$ 比赛分析 - $\text{Part 3.3}$ 实战演练 - $\text{Part 3}$ CSP-S 2022 - $\text{Part 4.1}$ 前置知识 - $\text{Part 4.2}$ 比赛分析 - $\text{Part 4.3}$ 实战演练 - $\text{Part 3}$ NOIP 2022 - $\text{Part 5.1}$ 前置知识 - $\text{Part 5.2}$ 比赛分析 - $\text{Part 5.3}$ 实战演练 - $\text{Part 5}$ 做题策略总结 - $\text{Part 6}$ 后记 ## $\text{Part 0}$ 前言 CSP 即将来临，肯定有很多同学肯定在为绿勾蓝勾而奋斗，希望能在二轮比赛中获得好成绩。 然而，神仙都是经过千锤百炼而诞生的，蒟蒻是不能在短时间内弥补与神仙巨大的实力差距，而又需要与神仙来竞争。这应该怎么办呢？这就需要**暴力与骗分**。 [骗分导论](https://www.luogu.com.cn/paste/mp153wv3) 这里说一下我对**暴力和骗分**的理解： > 暴力：用自己已经熟练掌握的方法或者非正解对一道题拿到部分分甚至AC。 > 骗分：在一道题不择手段地（SSH等除外）拿到尽量多的部分分。 从这里可以看到，我所定义的暴力与骗分**不仅仅**包括爆搜、循环、输出无解等，更多的包括依靠自己实力来获得比最朴素的暴力多得多的分数。 **暴力和骗分**是一个很有用的技巧，但它也依靠这自己的能力。下面我来举一下 $2020\sim2021$ 和 $2022\sim2023$ 比赛季的四场比赛，普及组的比赛就不再讲解，原因是普及组的东西是最基础的，普及组不建议在一二题骗分。 也可以说，本篇文章是为想要一等的同学准备的。 ## $\text{Part 1}$ 心态 首先，心态是最重要的。 **同一个你，同一份考题，有没有一个好的心态，能差好几十分，甚至是数百分。** 在比赛开始之前不要把结果看得太重，平常心去比赛即可。不管成功或者失利，出成绩都不要过于高兴或悲伤，这绝不是终点（除非您高二）。 ## $\text{Part 2}$ CSP-S 2020 ### $\text{Part 2.1}$ 前置知识 **极其熟练**的搜索，一定的 ds 基础（ST表，树状数组，线段树，LCA），一定的dp基础（会绿题及一下经典题目的方程推导），组合数学入门，能做一些中型模拟甚至大模拟（不限时间），基础STL，一定的图基础，一定的字符串基础（哈希），图上的 tarjan 之类。 练习可以去洛谷题单搜索，十分方便。 ### $\text{Part 2.2}$ 比赛分析 提高组的比赛，难度不算太高，能拿到**很多**部分分的。 有一说一，2020 年的提高组比赛题目不算太难，但是**第一题**搞人心态。**做题顺序**能很大程度上决定分数。 ### $\text{Part 2.3}$ 实战演练 [题库中前四道]( https://www.luogu.com.cn/problem/list?tag=342%7C37&page=1 ) 拿到试卷，我们看到了第一题： [儒略日](https://www.luogu.com.cn/problem/P7075) 数据范围： | 测试点编号 | $Q =$ | $r_i \le$ | |:-:|:-:|:-:| | $1$ | $1000$ | $365$ | | $2$ | $1000$ | $10^4$ | | $3$ | $1000$ | $10^5$ | | $4$ | $10000$ | $3\times 10^5$ | | $5$ | $10000$ | $2.5\times 10^6$ | | $6$ | $10^5$ | $2.5\times 10^6$ | | $7$ | $10^5$ | $5\times 10^6$ | | $8$ | $10^5$ | $10^7$ | | $9$ | $10^5$ | $10^9$ | | $10$ | $10^5$ | 年份答案不超过 $10^9$ | 显然这是道大分类讨论题，这就引出了我们第一个原则： **大分类讨论和大模拟尽量往后放** 很多人折在第一题上，导致分数线很低。 先看一下数据范围，发现前四个点都是公元前的，非常好写，橙题难度，直接写个暴力枚举月份即可，大约 $20$ 分钟即可完成。 **期望得分：** $\mathbf{40+0+0+0=40} $ 然后我们来看第二题： [动物园](https://www.luogu.com.cn/problem/P7076) 这题就很水了，只需要仔细找一下性质即可 有一个条件是“所有的 $q_i$ 互不相同”，这意味着饲料是啥都不重要了，$c$ 和 $q_i$ 甚至不用读进来,这就避免了 MLE。 最多需要 $25$ 分钟就可以把这道题的AC代码写完，特判 $k=64,n=0$ 的情况即可。 此时仅仅过去了一节课的时间，我们就**期望得到了**：$\mathbf{40+100+0+0=140}$。 之后我们开第三题： [函数调用](https://www.luogu.com.cn/problem/P7077) 显然，我们可以很容易的写出不包含三号函数，裸的线段树2，写完大概需要 $25min$（不熟练线段树的话）。 接着来看特殊限制： > 不含第 `2` 类函数或不含第 `1` 类函数 不含第1类函数极其简单，因为是全部的操作。 然后显然纯暴力是可以把 $1\sim 4$ 数据点跑过去的 这样我们又期望得到了 $\mathbf{40}$ 分，目前期望 $\mathbf{40+100+40+0=180}$ 分。 T3的正解其实也不算太难，现在可以先写一下T4的暴力，回头再写T3。 第四题： [贪吃蛇](https://www.luogu.com.cn/problem/P7078) 从题面很容易就可以得知这一个性质（每条蛇的策略），设还剩下 $m$ 条蛇，长度递减。 下面比较默认加上编号比较。 > 如果 $a_0$ 吃了 $a_m$ ，而且吃完之后还不是最小的，即 $a_0-a_m>a_{m-1}$ ，$a_0$ 肯定会吃。 > 如果 $a_0-a_m<a_{m-1}$，如果 $a_1$ 按照同样的策略不吃 $a_0$ 的话， $a_0$ 就吃。 根据第一条性质就可以很容易得想出基本代码，但是会栽在大样例上，而且每个都会多 $1$。 从这里就可以帮助我们想第二条性质，就是性质二可以再帮助我们吃掉一条蛇！ 如果说想到这第一条性质，可以获得 $\mathbf{20}$ 分。 如果想到第二条性质，我们最少可以获得 $\mathbf{40}$ 分。 第二条性质该怎么办呢？用奇偶性搞。 我们把 $a_2$ 定为第一条蛇，以此类推。 显然，如果第奇数条蛇的决定是吃，$a_0$ 选择不吃。 如果第偶数条蛇的决定是吃，$a_0$ 选择吃。 这个东西就可以用一个 `set` 来维护，分成两个阶段。 第一阶段：最长的疯狂吃，直到最长的吃掉之后比最短的短。 第二阶段：判断奇偶性看看能不能再吃一条。 然后就可以用 `set` 来维护，时间复杂度为 $Tn\log(n)$ ，可以拿到 $\mathbf{70}$ 分！ （满分算法其实优化起来不算太难，不过这好像已经是正解了就不放了，感兴趣的可以看题解） **期望得分**：$\mathbf{40+100+40+[20,70]=[200,250]}$ 分 然后就可以去看前面的T3和T1了，您可以尝试去写T3的正解（拓扑一下即可）以及干T1的分类讨论。 T1的分类讨论发现非常复杂，我们发现可以用**二分**方法去做，比直接弄要简单不少。 如果时间足够是可以写出正解的。 **期望得分**：$\mathbf{[40,100]+100+40+[20,70]=[200,310]}$ 分 可以看到，最低档的暴力分是在 $\mathbf{200}$ 分，而最高档的已经达到了 $\mathbf{310}$ 分。 而蓝勾分数线仅仅为 $\mathbf{140}$ 分，有很多的挂分空间。 ### 小总结 大胆猜想，小心求证。其实前面那一句话是很重要的，比如贪吃蛇的第二条性质，只要总结出来分数就可以至少提高 $\mathbf{50}$ 分。 ## $\text{Part 3}$ NOIP 2020 ### $\text{Part 3.1}$ 前置知识 基本和前面的一样，而又往后了一个月，可以往前学习一点。 大概可以向前学树剖网络流之类的。 关于字符串：MLE太菜了不会字符串，只会哈希和暴力，就不写了。 ### $\text{Part 3.2}$ 比赛分析 这场比赛总体来说难度也不算太高，就是T1卡了先乘后除。 ### $\text{Part 3.3}$ 实战演练 [题库中后四道](https://www.luogu.com.cn/problem/list?keyword=&tag=37%7C83&page=1) 我们拿到了第一题[排水系统](https://www.luogu.com.cn/problem/P7113)。 显然这是一道拓扑排序的裸题，直接扔一个板子。我假设您看到了数据范围，并且有非常好的习惯这道题用了先除后乘，时间大概过去半个小时。 因为数据范围算出来一个点很有可能爆ll。 期望得分 $\mathbf{90+0+0+0=90}$ 分。 我们来看第二道题[字符串匹配](https://www.luogu.com.cn/problem/P7114)。 这道题显然有个极其暴力的做法，直接照着题面，从头开始找循环长度，直接模拟即可，但是一定要**注意细节**。 [参考代码，考场写的，很臭，请见谅。](https://www.luogu.com.cn/paste/4qyvbmnq) 对于特殊性质一和二，因为只含有一到两种字符，就可以用**字符串哈希**来搞一下，这样就得到了不少的分数。 期望得分 $\mathbf{90+[48,84]+0+0=[138,174]}$ 分。 第三题是一道构造题，**先放一放**。 第四题[微信步数](https://www.luogu.com.cn/problem/P7116)。 显然 `-1` 的情况很容易判断出来，就是一轮循环仍然在原地。 然后前三十分的暴力非常好拿，写一个dfs就行。 [暴力代码](https://www.luogu.com.cn/paste/g75mhqnq) 因为后面估计还有一个点是 `-1`，所以我们期望得分是： $\mathbf{90+[48,84]+0+35=[173,209]}$ 分。 检查其他题没有问题，我们就来看第三题[移球游戏](https://www.luogu.com.cn/problem/P7115)。 这是NOIP第一次出SPJ题，非常考验思维。 先来看 `n=2` 的情况，可以用暴力解决，具体可以看题解（因为MLE太菜了真不好描述）。 这道题就看您思维水平了，但是10分应该是能拿到的。 期望得分 $\mathbf{90+[48,84]+10+35=[183,219]}$ 分。 ### 小总结 NOIP2020确实比CSP-S2020要难一些，但还是可以通过自身强大的功底来获得比上述期望高的多的分数。 参考：山东高中生NOIP2020一等分数线大概是140分，不算高。 ## $\text{Part 4}$ CSP-S 2022 ### $\text{Part 4.1}$ 前置知识 基本同上。 ### $\text{Part 4.2}$ 比赛分析 算是近几年最简单的提高比赛了，非常容易得很高的分。 骗分也是没有啥表现，直接写正解就差不多了。 ### $\text{Part 4.3}$ 实战演练 [题目链接](https://www.luogu.com.cn/problem/list?tag=342%7C59&page=1) 看到第一题，因为中间只有四个点，自然想到枚举中间两个点。 然后就转化成求每个点经过一个点再到达起点的分数。 算上重复也最多取三个，枚举每两个点前三个判断是否合法即可。 期望得分 $\mathbf{100+0+0+0=100}$ 分。 接着看第二题，一眼申必 st 表，直接敲上，注意些细节就差不多过了。 期望得分 $\mathbf{100+100+0+0=200}$ 分。 最多两个小时就能写完前两道题。 第三题题面看起来很麻烦，仔细读完题发现可以反攻当且仅当出度均为 1。 首先把 $n^2$ 的写了，然后考虑用 set 维护把没有操作 4 的做出来，就有 $60$ 分了。 期望得分 $\mathbf{100+100+60+0=260}$ 分。 第四题随便写写暴力，最少把 $16$ 分 $k=1$ 暴力写了。 期望得分 $\mathbf{100+100+60+16=276}$ 分。 因为没打，而且太简单了，描述就很简略。 ## $\text{Part 5}$ NOIP 2022 ### $\text{Part 5.1}$ 前置知识 基本同上。 ### $\text{Part 5.2}$ 比赛分析 分数严格依赖于开题顺序的比赛。 个人认为如果 swap T2T3 队线会提高 30-50。 为了留有一些真实性，我们按照考场上做题进行分析。 ### $\text{Part 5.3}$ 实战演练 [题目链接](https://www.luogu.com.cn/problem/list?page=1&tag=83%7C59) 第一题是[种花](https://www.luogu.com.cn/problem/P8865)，是一个小清新签到题。随便跑几次前缀和就能过了。 注意多测要清空。 时间大概要二十分钟要一个小时吧。 期望得分 $\mathbf{100+0+0+0=100}$ 分。 然后看到了[喵了个喵](https://www.luogu.com.cn/problem/P8866)。 看到题之后发现 $k=2n-2$ 非常简单。可以一个栈固定塞两种，最后空出来一个栈，然后用这个空出来的栈对每次塞进来的卡牌和前面的卡牌进行消除。策略就是能消就消。注意要输出步数。 期望得分 $\mathbf{100+15+0+0=115}$ 分。 此时时间过了不到一个小时。 因为你的经验告诉你，如果联赛第二题都拿不了高分会很丢人，然后你开始硬冲喵了个喵。 时间又过去了快两个小时，发现 T2 非常神秘，还是没想出 T2，我们假定你把爆搜写了并写对了。 期望得分 $\mathbf{100+35+0+0=135}$ 分。 时间还剩将近两个小时，显然是不能继续冲 T2 了。 开始看 T3 [建造军营](https://www.luogu.com.cn/problem/P8867)。 看了一会题面不难想到，这是一个缩点+树上 dp。 但是不能保证一个多小时内能把这两个写完并写对。 再来看 T4 [比赛](https://www.luogu.com.cn/problem/P8868)。 这题是一道数据结构题，而且看起来比较经典。但是这个时候显然是不能想正解了。 $n^2$ 的前缀和很容易写，这样是有 $20$ 分的。 单调栈是有 $52$ 分的，但是这没时间了。 期望得分 $\mathbf{100+35+0+20=155}$ 分。 最后来看 T3。 看到状压竟然有足足 $35$ 分，所以决定去打这档部分分。 $2^n$ 枚举哪些点选作军营，然后再统计有多少条边是必须要保护的，这个单次可以用 $m^2$ 做到，假定结果是 $x$。所以这个状态对答案的贡献就是 $2^{m-x}$。 期望得分 $\mathbf{100+35+35+20=190}$ 分。 大概可以在结束前十多分钟前完成吧。 看到后面还有 $10$ 分链的部分分。假设军营最左端是 $l$，最右端是 $r$，显然 $l$ 和 $r$ 内部可以随便插入军营，而且 $l$ 到 $r$ 之间的道路必须要守。可以通过枚举区间长度进行统计。 期望得分 $\mathbf{100+35+45+20=200}$ 分。 ### 小总结 如果开题顺序改为 $1-3-4-2$，分数大概可以比刚才的 $200$ 分提高至少 $30$ 分吧，上面是按照真实考场上大多数人的开题顺序写的。 其实 csp-s 已经暗地里挑出第一题比第二题难，但是因为 csp 第一题比较水所以没啥人注意到这一点。 最大的教训是开题顺序不能严格依赖于题目安排顺序，一定要在比赛开始时读完每一道题再做。 ## $\text{Part 5}$ 做题策略总结 我写的这四场比赛，大多数的得分都和开题顺序有关。 所以，一定要在开始时，看完全部的四道题，自己心里评判一下难度，再从对于自己来说好做的开始做。 或者说更暴力一点，遇到非传统题默认手动排到第三题。 正解不会就别想正解了，因为会有 $114514$ 分的部分分也可以拿。 ## $\text{Part 6}$ 后记 这大概是我前年为了总结一下如何暴力骗分而开始写的东西吧。 文章的前半部分是 21-22 赛季开始前写的，现在看来比较小丑，有时间就改改。虽然说我现在也很小丑就是了。 写写停停那么长时间的东西也改完结了吧。 其实暴力和骗分，最终指的还是部分分。 对于每个人来说，暴力的标准显然是不同的，所以就能拿到不同档的部分分。 这个能打的部分分的高低，归根结底来说还是自己的能力。 这可能也比较小丑，为了突破自己的能力拿到更高分而学习暴力和骗分，然而最后暴力和骗分还是要归于自身能力的。 对于一个人来说，部分分是非常多的，但是这又引出来 OI 正赛的一个关键词——挂分。 有骗分技巧能提高分数上限，而挂分则决定你到底能获得多少分。 最终的得分，大概是归结于自身的能力和考场技巧的。 但是，显然一个人的能力是不能简单量化的，还得看相性。 每个人都有相对突出的点，也有相对差劲的点。如果考到自己擅长的点，分数可能会提高，反之分数可能会降低。 总之，这就是 OI，永远存在不稳定因素，就像一场豪赌的，但是我们仍然坚持的，信息学竞赛。 补：之后可能会改改一下前面的内容，看看有没有时间吧。
正在渲染内容...
点赞
80
收藏
12
