0. 前言
骗分，是 OI 中特有的得分方式，旨在使用简单的非正解获取更多的分数。毕竟并不是所有人都可以在赛场上就可以想到满分正解的，并且还要考虑时间分配问题。因此，熟练掌握骗分方法，让自己在赛场上尽力得分，这是 OIers 的基本素养。（ACM 没有部分分，所以无法施展骗分妙招 /oh）
本文将会为大家讲解常用的骗分瞎搞技巧 / 算法 / 数据结构，祝各位 CSP/NOIp/NOI 以及其它所有比赛 rp++！
1. 基础骗分技巧
1.1 "不可以，总司令"
在有些题目中，会有这么一句话：
若无解，请输出 -1/NO
这让许多没有任何头绪或时间不够没法写正解的 OIers 欣喜若狂。因为这意味着，只需要：
printf("-1");
你就可以获得 10 分、20 分甚至更多！
值得一提的是，在 CSP-S 2022 T3 星战 一题中，虽然每个测试点多组数据，但是只要全部输出 NO，你还是可以获得 45 分！这也是本章标题的来历。
通常数据没这么水，所以期望得分：
10 pts ~ 30 pts
1.2 样例
样例是很有用的，因为这可以帮你初步 debug 程序，还可以骗分！
在美国的 USACO 中，第一个测试点 必定是样例。也就是说，在一题中只要输出样例，你就可以获得 10pts！
当然 CSP 啥的就没这个规定了。/oh
期望得分：
0 pts ~ 10 pts
另：多找一找样例规律，也许是诈骗题。
1.3 打表——无赖但好用
打表，就是把答案手算或暴力算出来，然后把已经算出来的答案塞进一个数组里，对于每个输入，输出算好的答案。
这在小数据中及其好用，例如：NOIp 2003 普及组 T3 栈。
本题看着挺唬人的，不过就是一道卡特兰数板子。当然，普及组选手不一定会这些。这题数据异常的小，我们直接模拟先算出来，然后放进一个数组里，就可以静待 AC 啦！
当然，打表也不一定要打全部，可能会爆代码长度上限，可以只打部分分。在提高组及以上，打表也通常用来找规律写出状态转移方程啥的。
期望得分（能使用的话）：
30 pts ~ 100 pts
1.5 欧皇专属——随机数
请注意，在您没有满足以下任意一个条件时，请不要随便使用此方法：
- CSGO 一发出高价红 / 粉皮；
- CODM 一发出神话；
原神一发出五星；- 其他类似的……
你可以用 C 标准库中的 srand() 和 rand() 函数，也可以使用 C++11 的 std::mt19937 类。使用指南可参考 OI-wiki 或 CppReference。
当然数据范围越小越好，例如输出 Yes/No 又找不出规律时，随机就成为了首选！
期望得分：
Random numbers from 0 to 100 pts
接下来会涉及到基础算法，请刚学完语法的萌新止步于此。/fad
2. 基础骗分算法
2.1 模拟
这个应该没什么应该说的吧，照着题目要求模拟就行。（
较繁琐的模拟就不是骗分了，赤裸裸的例子：SDOI 2010 猪国杀 。
模拟通常用来骗高级数据结构和高级算法的分，如：ST 表、线段树、平衡树等等。
例题：[USACO 20007 JAN] Balanced Lineup G 。
本题是 RMQ（区间极值问题）的板子，神犇可以手搓线段树、ST 表，蒟蒻的我们，还是骗分吧。
while (q--) {
scanf("%d%d", &a, &b);
int minn = INT_MAX, maxn = INT_MIN;
for (int i = a; i <= b; i++) {
if (h[i] < minn)minn = h[i];
if (h[i] > maxn)maxn = h[i];
}
printf("%d\n", maxn - minn);
}
本程序得分：50 pts。
期望得分：
20 pts ~ 40 pts
2.2 DFS：万能算法
DFS 是图论中的重要算法，但我们看来，图论神马的都是浮云，关键就是如何骗分。正如你所见，DFS 是适用性最高的算法之一。像是 DP、数学题、诈骗题，大多都可以 DFS！
例题 1：NOIp 2005 普及组 采药 。
本题是 0/1 背包的板子题，不过对于不知 DP 为何物的我们来说，DFS 成了不错的选择。
DFS 的万能 + 简易可能不太明显？接下来以一道状态压缩 DP 例题作为我们下一个 DFS 骗分目标（不是真题）：洛谷 P1433 吃奶酪 。
本题 DFS 简单好写，且可通过所有普通数据！
void dfs(int step, int now, double sum) {
if (sum >= ans)
return;
cnt++;
if (cnt >= 17000000) {
printf("%.2Lf", ans);
exit(0);//卡时间，递归到一定次数直接输出当前结果
}
if (step > n) {
if (sum < ans)ans = sum;
return;
}
for (int i = 1; i <= n; i++)
if (!f[i]) {
sum += dis[now][i];
if (sum >= ans)
continue;
f[i] = 1;
dfs(step + 1, i, sum);
f[i] = 0;
sum -= dis[now][i];
}
}
可惜的是，本题增加了 hACk 数据，本代码无法 AC。
期望得分：
20 pts ~ 40 pts
2.3 BFS
和 DFS 差不多，多用在图论。
期望得分：
20 pts ~ 40 pts
2.4 下下策：Floyd
如果一道图论题需要求最短路，但是不会 dijkstra，或负权图不会 bellman ford（SPFA 是队列优化 bf），可以考虑使用 Floyd。虽然在稀疏图效率变低很多，但是总比全丢分强吧？
无向图板子：
void floyd () {
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (j != i && j != k && i != k)
f[j][i] = f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}
期望得分（假设正解需要用到的是 dij）：
20 pts ~ 30 pts
3. 高级骗分技巧
3.1 数据点分治
注：本骗分方法和分治 & 点分治没啥关系。
有时候我们口胡出正解或贪心解等快速解法了！但是有可能假掉或对代码实现的正确性不敢保证。/oh/fad
这时候，我们就需要 数据点分治 了！
数据点分治的代码结构大概是这样的：
if (n < 骗分能过范围) {
...;//骗分程序
} else {
...;//正确性有待证明的快速解法
}
当然你还可以 if..else if..else if..else 这样套着玩！
期望得分：
暴力法得分 ~ 100 pts
当然不一定是快速解法，也可以是……
if (是样例) {
printf("%d", 样例);
} else if (n < 暴力能过) {
...;//暴力程序
} else if (打表范围) {
printf("%d", ans[n - 1]);
} else ...//其他的
也可以称之为数据点分治。
3.2 常数优化
有很多，但是不建议各位乱用，可能会负优化，不要以为你比编译器更懂优化。
3.2.1 快读快写
顾名思义，就是加快 IO 速度。
第一种方法：关闭同步流
在主函数开头加上这个（C++ 98 请把 nullptr 换成 NULL）：
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(nullptr);
就可以加快 IOStream 的速度！
注意：永远也不要混用 C 风格 StdIO 和 C++ 风格 IOStream！
第二种方法：fread()
请注意这货是 StdIO 的。
char buf[1 << 20], *_now = buf, *_end = buf;
#define getchr() (_now == _end && (_end = (_now = buf) + fread(buf, 1, 1 << 20, stdin), _now == _end) ? EOF : *_now++)
int read () {
int x = 0, f = 1;
char ch = getchr();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchr();
}
while (ch >= '0' && ch <= '9')
x = x * 10 + ch - '0', ch = getchr();
return x * f;
}
不使用传统快读的原因是因为优化甚至不如 IOStream 关同步流。
3.2.2 适当的位运算
请不要滥用。因为可能会负优化。
通常在线段树之类的常数怪兽使用。接下来我给大家列出几个常用的加速位运算。
n & 1，判断 n 奇偶性。奇数返回 1；n << k，返回 n 乘 2 的 k 次方；k << 1以及k << 1 | 1，线段树的节点 k 的左儿子右儿子；
n >> k，返回 n 除以 2 的 k 次方。
3.3 猜测、找规律
有时候，满足题目有解的条件十分苛刻，我们可以“猜测”答案大概率为 YES/NO，并且赌数据较水，没有过多特殊构造的，从而实现总司令可获得的分数变多。这类题目通常在提高组及以上，且不会太多。
比如，满足 CSP-S 2022 T3 星战 有解的情况比较苛刻，CCF 又有随机脚本造数据，因此出现这么水的数据。/oh
至于找规律，通常配合打表使用，一般是用于找出数列本身的规律（如：卡特兰数），亦或者口胡动态转移方程，这再上一章提到过了。此外：珍爱生命，谨防诈骗题。没头绪或数据范围极大记得找规律啊，大概率是诈骗。
期望得分（找出来的话）：
10 pts ~ 40 pts
4. STL & pb-ds
4.1 STL
STL 是个好东西，封装了常用算法（如快排）和常用数据结构（如栈、堆等），有助于节省码量、节约时间和骗分！
STL 相关部分参考 CppReference
4.1.1 std::deque
注意：std::deque 空间常数很大。
std::deque 实现了双端队列。
常用操作：
at()/operator[]，随机访问；front()/back()，前后元素；push_front()/push_back()，前后端插入；pop_front()/pop_back()，前后端弹出；size()/empty()，元素个数以及是否为空；insert()，插入元素；- 各种迭代器相关的……
用途：主要是单调队列。
4.1.2 std::stack
注意：stack 基于 std::deque，空间常数很大。
std::stack 实现了栈。
常用操作：
top()，栈顶元素；pop()/push()，弹出栈顶以及入栈；size()/empty()，元素个数以及是否为空；
4.1.3 std::queue
注意：queue 基于 std::deque，空间常数很大。
std::queue 实现了队列。
常用操作：
front()/back()，队首和队尾元素；pop()/push()，弹出队首以及入队；size()/empty()，元素个数以及是否为空；
4.1.4 std::priority_queue
std::priority_queue 实现了优先队列。
第三个参数类似于 std::sort() 的第三个参数，填充的是比较类。
top()，（暂时先这么说）堆顶元素；pop()/push()，弹出堆顶以及入堆；size()/empty()，元素个数以及是否为空；
4.1.5 std::set & std::multiset & unordered_set
set 用红黑树实现了“集合”，multiset 则是“可重集”。unordered set 则是“无序集合”
set 和 multiset 因为底层是 rbt，所以会自动排序。unordered set 底层是 Hash，所以不会自动排序。
常用操作：
insert()，插入；erase()/clear()，删除和清空；size()/empty()，元素个数以及是否为空；count()，返回指定元素在集合内的个数；find()，查找某个指定元素；lower_bound()和upper_bound()，二分查找首个不小于和大于指定元素的元素；- 各种迭代器相关的……
例题
- HNOI 2002 营业额统计
你知道吗：这题就是因为 set 能过所以降级到了绿。
-
洛谷 P1738 洛谷的文件夹
-
珂朵莉树的习题后文会提到。
4.1.6 std::map & std::multimap & std::unordered_map
map 用红黑树实现了“映射”，multimap 则是“可重映射”。unordered map 则是“无序映射”
map 和 multimap 因为底层是 rbt，所以会自动排序。unordered map 底层是 Hash，所以不会自动排序。
常用操作：
insert()，插入；erase()/clear()，删除和清空；size()/empty()，元素个数以及是否为空；count()，返回指定元素在映射内的个数；find()，查找某个指定元素；lower_bound()和upper_bound()，二分查找首个不小于和大于指定元素的元素；at()/operator[]，访问键值映射的元素；- 各种迭代器相关的……
例题
其实大部分字典树的题都可以用 map 的。/oh
-
TJOI 2010 阅读理解
set + map 或 map + vector。
-
洛谷 P2580 于是他错误的点名开始了
待更新……
标签：std,骗分,get,元素,得分,DFS,How,pts From： https://www.cnblogs.com/FiveUnderlines/p/how-to-get-ioi-au.html