简介：《信息学-骗分导论.docx》是一份面向信息学竞赛参赛者的策略性得分指南，主要定位给算法基础薄弱、备赛经验不足或处于集训初期的选手，系统讲解在无法完整求解时如何借助多种技巧博取尽可能高的分数。文档从lzn定理引出“骗分”理念，随后按章节梳理无解情况输出-1、利用题目样例直接得分、以模拟和DFS作为朴素解法、依托猜想与寻找规律、打表处理小数据、采用贪心策略，以及发挥C++快速排序、模板等语言优势等实用方法，并通过文化之旅、USACO排队查最值等真题演示操作过程，还设有实战演练章节帮助读者把技巧落地。资源包内含1个docx文档，压缩包大小约42KB，内容精炼、轻量便携，方便随时翻阅。目前已有129人浏览学习，适合希望提升竞赛得分率、增强考场应变能力和拓展解题思路的选手作为补充参考。
1. 信息学竞赛的骗分导论：它不只是投机取巧
参赛选手拿到一份题目，面对 100% 的数据范围手足无措，但每个数据点都有部分分，每个无解分支都可能白送 10 分。所谓“骗分”，本质上是把比赛当成一场带有明确评分规则的概率游戏：在无法写出标准算法时，用更简单的程序换取尽可能多的部分分。这套方法论不是乱猜，而是对评测机制、数据分布和算法复杂度的另一种理解，适合刚入门信息学竞赛、还在补算法基础的选手，也适合已经能写出正解但想在分档数据里多拿几分的工程型选手。
下面这份《信息学-骗分导论》文档，把竞赛里的常见得分手段系统化了：输出无解、直接输出样例、暴力模拟、DFS 枚举、猜答案、找规律、打表、贪心。这些手段大多数情况下并不冲突，可以组合在一个程序里。本文会把这些策略逐层拆开，结合代码、复杂度边界和适用场景讲清楚——为什么这样写能得分，哪里会失效，以及怎么把骗分程序做成一个结构完整、可回退的工程。
2. 无解分支与样例探测：输入输出层的基础得分
2.1 输出 -1：利用评测数据的必然分布
很多题目在输出描述中写着“若无解，请输出 -1”。这句话对不会做的人来说，是直接送分。数据范围越大，构造全部有解的数据就越困难，命题人几乎必然会在测试数据里混入无解的情况。以 NOIP2012 的文化之旅为例，国家、文化、排斥关系三重约束交织，全有解的数据反而少。
#include <cstdio> int main() { // 注意：这不是完整解法，而是针对无解数据点的策略性输出 printf("-1\n"); return 0; }这段代码没有任何输入读取。评测时程序直接输出 -1，遇到无解的数据点就能拿到对应的分数。跑这道题大概能拿到 10 分。原理在于：判题机按输出文件比对答案，不会检查你是否真的计算了过程。
这里的参数和边界要注意：printf("-1")需要补充换行符，有的评测系统对末尾换行敏感；更稳妥的做法是读取所有输入但不做处理，这样能避免运行时异常导致的额外失分。在样例输出为-1时这个方法更安全，否则你至少要知道“题目明确声明有 -1 输出”，这个策略才成立。
2.2 直接输出样例：精确匹配输入指纹
样例输入本身就是测试数据的一部分，尤其是 USACO 这类竞赛，规则明确要求第一组数据必须是样例。针对这种情况，可以把样例输入整体读入，做字符串哈希，匹配成功后直接输出样例输出。
#include <cstdio> #include <cstring> int main() { int a, b; scanf("%d%d", &a, &b); // 读取两个整数作为样例指纹 if (a == 2 && b == 2) { // 匹配到样例输入，直接输出样例答案 // 采样例：2 2 1 1 2 的答案可能是 -1 或 10 printf("-1\n"); } else { // 其他数据点：走普通逻辑，哪怕只是输出 -1 也有概率拿分 printf("-1\n"); } return 0; }比较输入指纹时，不仅要比对答案，还要比对题目中给出的输入规模。注意这里不能用论文式的“以输入样例为准”的口吻，每个人都在猜数据，但关键是让主程序在匹配失败时仍然能兜底。这就是所谓的“组合骗分”——样例分支命中 10 分，其余数据点用无解输出兜住另外的分。
直接输出样例的适用范围有限：只有确认题目数据里必然包含样例，或者样例本身就是一种极端情况时，整段程序才不会变成无效代码。否则，面对随机数据时这个分支永远不会被触发，只是一种防御。
3. 暴力算法的复杂度工程：模拟与 DFS 的边界
3.1 模拟：把高级数据结构题降维成循环
模拟是骗分手段里最接近正规解法的一种。线段树、树状数组、ST 表能解决的区间最值问题，用一层 for 循环扫描区间也能做，区别只在复杂度。USACO 2007 的排队题，50000 头牛、200000 个询问，模拟复杂度是 O(NQ)，即 1e10 次运算，肯定超时。
#include <cstdio> #include <climits> const int MAXN = 50005; int h[MAXN]; int main() { int n, q; scanf("%d%d", &n, &q); for (int i = 1; i <= n; i++) scanf("%d", &h[i]); while (q--) { int a, b; scanf("%d%d", &a, &b); // 直接扫描区间，求最大最小值之差 int minv = INT_MAX, maxv = INT_MIN; for (int i = a; i <= b; i++) { if (h[i] < minv) minv = h[i]; if (h[i] > maxv) maxv = h[i]; } printf("%d\n", maxv - minv); } return 0; }这里没有建树、没有维护区间信息，只在每次询问时做一次线性扫描。50% 的数据点能过，因为小数据区间短、询问少，1e6 以内的运算量可以压进时间限制。如果加ios::sync_with_stdio(false)和scanf混用需要注意，事实上纯scanf/printf已经足够。真正的优化点在于：如果数据范围再大一倍，连模拟都会超时，这时候需要把minv和maxv的初始化从INT_MAX改成首元素值，省去一次无意义的比较。
| 数据结构 | 单次询问复杂度 | 可承受数据规模 | 代码量 |
|---|---|---|---|
| 线段树 | O(logN) | 1e5 以上可跑 | 80 行+ |
| ST 表 | O(1) | 1e6 预处理受限 | 40 行+ |
| 模拟 | O(N) | 1e4 以下较稳 | 10 行 |
模拟适合作为其他骗分手段的底座。先写模拟，再考虑是不是要用数据结构优化，这本身就是竞赛选手调试程序的基本功。
3.2 DFS 枚举：剪枝与参数设计
DFS 被称为“骗分万能钥匙”的原因在于：任何 DP 题都可以用搜索枚举所有状态，任何图论题都能用深度优先遍历做连通性判断。代价是指数复杂度。以 NOIP2003 采药为例，100 株草药、背包时间上限 1000，正经解法是 0/1 背包 DP，但 DFS 能枚举所有采摘组合。
#include <cstdio> const int MAXM = 105; int t[MAXM], w[MAXM]; int T, M, ans = 0; // d: 当前决策到第几株药; c: 当前已用时间; val: 当前总价值 void DFS(int d, int c, int val) { if (c > T) return; // 超出时间限制，剪枝 if (d == M) { if (val > ans) ans = val; // 更新最优解 return; } // 跳过当前草药 DFS(d + 1, c, val); // 采摘当前草药（前提是时间不超） if (c + t[d] <= T) { DFS(d + 1, c + t[d], val + w[d]); } } int main() { scanf("%d%d", &T, &M); for (int i = 0; i < M; i++) { scanf("%d%d", &t[i], &w[i]); } DFS(0, 0, 0); printf("%d\n", ans); return 0; }这段代码的时间复杂度是 O(2^M)。当 M=10 时只有 1024 种组合，30% 的数据点能过；当 M=100 时，即使用剪枝，最坏情况下也是 2^100 级别，跑完整个数据点不可能。但把if (c > T) return放在函数开头，比放在调用前更有效，因为它在递归入口统一拦截，能提前结束大量分支。
DFS 的骗分价值不光在于全枚举，还在于半枚举——先用 DFS 算出小数据的结论，再用打表的方式输出，这就是下一章要讲的思路。
4. 猜答案、找规律与打表：数据规律的概率模型
4.1 随机数与听天由命：期望值的数学分析
输出随机数的核心逻辑是：答案取值范围小，随机命中的概率就不低。如果题目要求输出 0 或 1，rand() % 2的命中率就是 50%，每个数据点 50% 概率拿到对应分数。
#include <cstdio> #include <cstdlib> #include <ctime> int main() { srand(time(NULL)); // 用当前时间做随机种子 int n; scanf("%d", &n); // 读入数据范围（可选） // 猜测答案可能是某个范围内的整数 // 假设答案范围是 [1, 100] printf("%d\n", rand() % 100 + 1); return 0; }srand(time(NULL))保证每次运行生成的序列不同，但这在评测机上是双刃剑：如果答案只有一个固定值，随机数种子不同并不会提高命中率，rand() % 100的命中率始终是 1%。从期望值角度看，随机数只适合答案集合极小的判定性问题，比如“是否存在环”输出 yes/no。不要在高精度数值题上使用随机数，因为除 0 错误或类型溢出反而会挂掉整个测试点。
4.2 寻找规律：用小数据枚举反推数学特征
NOIP2003 的栈问题，数据范围 n ≤ 18，输出序列总数。大牛能用卡特兰数公式直接算，但完全可以用 DFS 枚举小规模入栈出栈操作，得到前几项答案，再查 OEIS 或者直接猜规律。
#include <cstdio> // 用递归模拟栈操作，统计输出序列总数 // 参数 a: 待入栈元素个数，b: 栈内元素个数 int dfs(int a, int b) { if (a == 0) return 1; // 没有待入栈元素，只剩一种弹栈顺序 int ans = 0; if (b > 0) ans += dfs(a, b - 1); // 弹出一个栈顶元素 ans += dfs(a - 1, b + 1); // 压入一个元素 return ans; } int main() { for (int n = 1; n <= 18; n++) { printf("n=%d: %d\n", n, dfs(n, 0)); } return 0; }这段程序跑出来的序列是 1, 2, 5, 14, 42, 132...，这就是卡特兰数的前几项。一旦识别出这个规律，就能用递推公式在 O(n) 时间内算出答案，甚至直接硬编码一个数组。找规律的本质是先做小数据全枚举——枚举本身可能是 O(2^n)，但因为 n 小所以能跑——再观察数列的增长模式。
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 答案 | 1 | 2 | 5 | 14 | 42 | 132 | 429 | 1430 | 4862 | 16796 |
这张表可以直接作为打表程序的原始数据。打表的边界在于 n 的取值范围，n 再大 int 就装不下了，需要用 long long 或高精度。这个规律发现的过程本身就是数据驱动推断的标准流程，和工业信息学里离线批处理的思想同源：先在离线环境跑完整计算，再把结论固化成表。区别在于竞赛打表只针对小数据范围，而工业场景可以跑数亿条记录生成索引表。这类工程思路可以参考 IEEE 工业信息学汇刊的投稿网站中关于离线计算与在线检索分离的典型设计，本质上都是把复杂计算前置、简单查询后置。
4.3 打表程序：从暴力枚举到静态数据
打表不只是把已知答案写死在代码里，更常见的方式是先写一个暴力程序，在自己电脑上运行生成答案表，然后把表嵌入提交的代码中。这样既保证了正确性，又不需要在评测机上现场计算。
#include <cstdio> // 已预生成的卡特兰数，n=1..18 const long long ans[] = {0, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700}; int main() { int n; scanf("%d", &n); if (n >= 1 && n <= 18) { // 直接查表输出，O(1) 复杂度 printf("%lld\n", ans[n]); } else { // 超出打表范围，退回暴力递归 printf("0\n"); } return 0; }直接查表的效率是 O(1)，不存在超时问题。风险在于：表的数据必须一字不差，多一个少一个数字都会导致答案错误。这里ans[0]留空位是为了让下标和题目的 n 直接对齐，避免写ans[n-1]时出现 off-by-one。如果表的长度超过 20，建议写成字符串常量，减少数字手抄出错的可能。
5. 贪心策略与实际编码细节：组合骗分与自校验骨架
5.1 贪心骗分的逻辑：把复杂优化降成排序
贪心算法在骗分领域的用法，是寻找目标函数中对结果影响最大的局部变量。以文档摘录的“有趣的问题”为例，目标是从 n 个二元组里去掉 k 个，使得最终比值尽可能小。虽然全局最优可能很复杂，但直觉上应该优先移除 a 值较大的项，因为 a 在分子上，越大越拉高比值。
#include <cstdio> #include <algorithm> struct Node { int a, b; }; bool cmp(const Node &x, const Node &y) { return x.a < y.a; // 按 a 升序排序，小的留在最后 } int main() { int n, k; while (scanf("%d%d", &n, &k) && (n || k)) { Node p[10005]; for (int i = 0; i < n; i++) scanf("%d", &p[i].a); for (int i = 0; i < n; i++) scanf("%d", &p[i].b); std::sort(p, p + n, cmp); // 按 a 值排序 // 去掉 a 最大的 k 个，剩下 n-k 个 long long sa = 0, sb = 0; for (int i = 0; i < n - k; i++) { sa += p[i].a; sb += p[i].b; } printf("%lld\n", (sa * 100 + sb / 2) / sb); // 四舍五入 } return 0; }这里用(sa * 100 + sb / 2) / sb实现四舍五入，是整数运算的标准技巧。贪心策略只取了 a 值排序，忽略了 b 值对分母的影响，这就是它的局限：当 b 值波动极大时，保留一个 a 很小但 b 也很小的项，可能比保留 a 较大 b 较大的项更合理。所以这种骗分能拿到 20 分，但对全部数据点不一定成立。
5.2 组合骗分与自校验的稳健骨架
把前面所有骗分手段组装到一个程序里，核心是分级策略：优先输出样例分支，其次输出无解分支，最后才跑暴力计算。避免“用样例分支覆盖无解分支”导致逻辑重叠，也避免暴力程序在超时数据点上浪费评测时间。具体的骨架可以这样组织：
#include <cstdio> int main() { // 第 1 层：样例精确匹配（用输入指纹判断） if (is_sample_input()) { printf("样例答案\n"); return 0; } // 第 2 层：无解判断，题目明确声明时优先输出 -1 if (has_no_solution()) { printf("-1\n"); return 0; } // 第 3 层：小数据暴力求解（DFS/模拟） if (data_size_small()) { solve_by_brute_force(); return 0; } // 第 4 层：贪心兜底，不保证正确但保证有输出 solve_by_greedy(); return 0; }is_sample_input()通常通过比对前两行输入的数字实现，不要用字符串整文件比对，因为输入格式中可能有无关空格。has_no_solution()只能用于题目明确提及“无解输出 -1”的场景。真正的关键在第 3 层的判定条件：data_size_small()可以利用输入中读到的 N 和 M 值判断，比如 N <= 20 就跑 DFS，N <= 1000 就跑模拟，否则直接跳到贪心。
这样设计的好处是程序在任何数据点上都有输出，不存在编译通过但运行崩溃的空档。代价是代码长度增加，可能从 30 行膨胀到 120 行，但比赛规则通常不限制代码长度。
5.3 一个压箱底的技巧：把样例答案做成接口回退
在所有骗分手法里，有一个容易被忽略但非常稳健的细节：样例答案不要直接写死在主流程里，而是封装成一个独立的函数。
int get_sample_answer(int sample_id) { static const int table[][2] = { {1, -1}, // 第一组样例输入对应的答案 {2, 10}, // 第二组样例输入对应的答案 }; for (int i = 0; i < 2; i++) { if (table[i][0] == sample_id) { return table[i][1]; } } return -1; // 默认无解 }把样例答案封装为独立接口后，后续如果发现样例输入有多组，只需要扩展 table 数组，而不需要改动主判断逻辑。这比在 main 函数里堆 if-else 更贴近工程实践——预处理、查表、回退三种行为分离，代码可读性和可维护性都更好。
测真题时，建议先做一步自动验证：把样例输入复制进程序，看输出是否与样例输出完全一致，包括空行和末尾换行。这一步能过滤掉大约 30% 的笔误，比如printf("%d", x)少写了换行，在部分评测系统上不会判错，但在严格比对时就是 0 分。
本文还有配套的精品资源，点击获取
