..
TG1 暴力与部分分
为什么要打暴力/部分分？
为什么要打暴力分？
为什么暴力是神？在讨论这个问题之前，我想先说说其他打法相较于狂打暴力差在了哪里……
打比赛不一定 AC 的题足够多才能拿一等奖。打到的分数能过线就能拿一等奖。
此外，打暴力有个很重要的作用，就是对拍。
OI 赛制下，出题人提供的仅有几个样例，而这样例也可能出现强度过低的情况，于是将你的程序与暴力程序对牌可以更好发现错误。
常见思路：
- 用生成器 generator 生成输入数据到 0.in；
- 用暴力程序 brute-force 从 0.in 读入，输出到 0.ans；
- 用你的程序 my-ans 从 0.in 读入，输出到 0.out；
- 比较 0.ans 和 0.out，若不一致则暂停程序，否则回到第一步。
时间安排
众所周知，NOIp 和 CSP 考试时长有 4.5h。你通常不能把这些时间全部用来想正解。
通常的做法是，
- 花一点时间浏览一遍所有题目；
- 从最有把握的题目开始想，每题最多想 15～30 分钟，对于想出来的题目以力所能及的程序写正解；
- 对于想不出正解（花了较长时间但是仍然一筹莫展）的题目，不要有多余负担，直接打暴力和部分分。
部分分的组成
知道了出题人是怎么样设计部分分的，才能更好地挖掘隐藏在这一个个数据范围背后隐藏的得分点。
题目分值的构成
每条题目通常会设置不同档次的数据范围，每个范围都有对应的分值。
- 一道题一定会有个正解。最大的数据范围通常就是为正解设置。
- 一道题通常有暴力做法。最小的数据范围往往用暴力即可解。
- 正解可能是由劣解步步优化而来。根据优化的层次，出题人会设置梯度。
- 此外，作为提示，出题人可能会设置具有特殊性质的部分分。
- 当然，还有一种情况就是出题人想送分但是没别的想法，就随便整几个性质。
怎么写多档次范围的题目？
一条题目可以有很多档次的数据范围以及对应的分值。有时候这些范围是严格包含上一层范围的关系，有时候部分范围含有特殊性质。
你的程序要求能够对不同范围对症下药，尽量拿到更高的分数。
设法区别出不同的数据范围
有些题目比较良心，第一行会输入该测试点的编号。或者它会有很明显的数据特征，比如：
| 测试点编号 | $n =$ | 特殊性质 |
|---|---|---|
| $1 ∼ 2$ | $7$ | 无 |
| $3 ∼ 5$ | $199$ | 无 |
| $6 ∼ 8$ | $1999$ | 无 |
| $9 ∼ 11$ | $49991$ | A |
| $12 ∼ 15$ | $262143$ | B |
| $16$ | $99995$ | 无 |
| $17 ∼ 18$ | $199995$ | 无 |
| $19 ∼ 20$ | $299995$ | 无 |
有的题目虽然有性质，但是需要你进行一定处理。比如，
- 保证给定的图是一条链。那你就得找到链的端，同时按顺序取出链上每个元素的编号。
- 保证给定的图是个菊花。那也得找到菊花的花心。
- 保证某变量的值在某范围内。这个比较容易判断。
- 保证数据随机。这个真没啥办法区别，听天由命吧。
用命名空间组织程序
使用命名空间（namespace）可以有效区别出不同数据范围所采用的不同做法。
具体而言，每个针对不同数据范围的程序都放在一个命名空间内。
不过由于我们还得判别输入数据对应哪个范围，因此输入需要特殊处理。
此外可能存在代码片段复用的情况。一些函数可以放在命名空间外或者单独开个命名空间，但是注意不要打架。
#include<bits/stdc++.h>
using namespace std;
// 这里放各种要输入的东西的定义
namespace Reader{
void read(){ ... } // 这里读入所有数据
} }
namespace Sub1{ // 第一种数据范围的做法
// 这里放这种做法其他的变量 / 函数
void mian(){ ... }
}
namespace Sub2{ // 第二种数据范围的做法
}
...
int main(){
Reader :: read(); // 先读入所有东西
if( ... ) Sub1 :: mian(); else // 对于不同范围采用不同做法
if( ... ) Sub2 :: mian(); else ...
}
题目选讲
实战一些具有多档部分分的题目，获得尽量多的部分分，不必去细想正解怎么写。
在考场上，拼尽全力为自己赢得尽可能多的分数才是最优决策。
题目列表
- P7075 [CSP-S2020]儒略日
- P5017 [NOIP2018 普及组]摆渡车
- P5021 [NOIP2018 提高组]赛道修建
- P5664 [CSP-S2019]Emiya 家今天的饭
- P5666 [CSP-S2019]树的重心
- P5659 [CSP-S2019]树上的数
- P8291 [省选联考 2022]学术社区
- P7739 [NOI2021]密码箱
- P2482 [SDOI2010]猪国杀
- P3920 [WC2014]紫荆花之恋