如何在比赛中进行暴力和骗分？
听取MLE声一片
·
·
个人记录
声明
本文主观性较强，可能含有口嗨，请谨慎对待其正确性。
本文针对于联赛，因为省选并不在我经验范围内。
这是之前的版本，如果想看就去那看看。
前半部分（直到 NOIP2020）是在 21-22 赛季正式开始前写的，后半部分是在 22 年末以及 23 年初写的。这也算是把之前挖的坑给填好吧。全文写的比较小丑，请见谅。
为什么没有 2021 年？因为我 2021 年整一年都在自闭。
如果这对你来说有帮助，就点个赞吧。
一定要看后记。
如何在比赛中进行暴力和骗分？
\text{Part -1} 目录
-
-
-
- $\text{Part 2.1}$ 前置知识
- $\text{Part 2.2}$ 比赛分析
- $\text{Part 2.3}$ 实战演练
-
- $\text{Part 3.1}$ 前置知识
- $\text{Part 3.2}$ 比赛分析
- $\text{Part 3.3}$ 实战演练
-
- $\text{Part 4.1}$ 前置知识
- $\text{Part 4.2}$ 比赛分析
- $\text{Part 4.3}$ 实战演练
-
- $\text{Part 5.1}$ 前置知识
- $\text{Part 5.2}$ 比赛分析
- $\text{Part 5.3}$ 实战演练
-
-
\text{Part 0} 前言
CSP 即将来临，肯定有很多同学肯定在为绿勾蓝勾而奋斗，希望能在二轮比赛中获得好成绩。
然而，神仙都是经过千锤百炼而诞生的，蒟蒻是不能在短时间内弥补与神仙巨大的实力差距，而又需要与神仙来竞争。这应该怎么办呢？这就需要暴力与骗分。
骗分导论
这里说一下我对暴力和骗分的理解：
暴力：用自己已经熟练掌握的方法或者非正解对一道题拿到部分分甚至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} 实战演练
题库中前四道
拿到试卷，我们看到了第一题：
儒略日
数据范围：
| 测试点编号 |
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}
然后我们来看第二题：
动物园
这题就很水了，只需要仔细找一下性质即可
有一个条件是“所有的 q_i 互不相同”，这意味着饲料是啥都不重要了，c 和 q_i 甚至不用读进来,这就避免了 MLE。
最多需要 25 分钟就可以把这道题的AC代码写完，特判 k=64,n=0 的情况即可。
此时仅仅过去了一节课的时间，我们就期望得到了：\mathbf{40+100+0+0=140}。
之后我们开第三题：
函数调用
显然，我们可以很容易的写出不包含三号函数，裸的线段树2，写完大概需要 25min（不熟练线段树的话）。
接着来看特殊限制：
不含第 2 类函数或不含第 1 类函数
不含第1类函数极其简单，因为是全部的操作。
然后显然纯暴力是可以把 1\sim 4 数据点跑过去的
这样我们又期望得到了 \mathbf{40} 分，目前期望 \mathbf{40+100+40+0=180} 分。
T3的正解其实也不算太难，现在可以先写一下T4的暴力，回头再写T3。
第四题：
贪吃蛇
从题面很容易就可以得知这一个性质（每条蛇的策略），设还剩下 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} 实战演练
题库中后四道
我们拿到了第一题排水系统。
显然这是一道拓扑排序的裸题，直接扔一个板子。我假设您看到了数据范围，并且有非常好的习惯这道题用了先除后乘，时间大概过去半个小时。
因为数据范围算出来一个点很有可能爆ll。
期望得分 \mathbf{90+0+0+0=90} 分。
我们来看第二道题字符串匹配。
这道题显然有个极其暴力的做法，直接照着题面，从头开始找循环长度，直接模拟即可，但是一定要注意细节。
参考代码，考场写的，很臭，请见谅。
对于特殊性质一和二，因为只含有一到两种字符，就可以用字符串哈希来搞一下，这样就得到了不少的分数。
期望得分 \mathbf{90+[48,84]+0+0=[138,174]} 分。
第三题是一道构造题，先放一放。
第四题微信步数。
显然 -1 的情况很容易判断出来，就是一轮循环仍然在原地。
然后前三十分的暴力非常好拿，写一个dfs就行。
暴力代码
因为后面估计还有一个点是 -1，所以我们期望得分是：
检查其他题没有问题，我们就来看第三题[移球游戏](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，永远存在不稳定因素，就像一场豪赌的，但是我们仍然坚持的，信息学竞赛。
补：之后可能会改改一下前面的内容，看看有没有时间吧。