简介《信息学-骗分导论.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)。当 M10 时只有 1024 种组合30% 的数据点能过当 M100 时即使用剪枝最坏情况下也是 2^100 级别跑完整个数据点不可能。但把if (c T) return放在函数开头比放在调用前更有效因为它在递归入口统一拦截能提前结束大量分支。DFS 的骗分价值不光在于全枚举还在于半枚举——先用 DFS 算出小数据的结论再用打表的方式输出这就是下一章要讲的思路。4. 猜答案、找规律与打表数据规律的概率模型4.1 随机数与听天由命期望值的数学分析输出随机数的核心逻辑是答案取值范围小随机命中的概率就不低。如果题目要求输出 0 或 1rand() % 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 小所以能跑——再观察数列的增长模式。n12345678910答案12514421324291430486216796这张表可以直接作为打表程序的原始数据。打表的边界在于 n 的取值范围n 再大 int 就装不下了需要用 long long 或高精度。这个规律发现的过程本身就是数据驱动推断的标准流程和工业信息学里离线批处理的思想同源先在离线环境跑完整计算再把结论固化成表。区别在于竞赛打表只针对小数据范围而工业场景可以跑数亿条记录生成索引表。这类工程思路可以参考 IEEE 工业信息学汇刊的投稿网站中关于离线计算与在线检索分离的典型设计本质上都是把复杂计算前置、简单查询后置。4.3 打表程序从暴力枚举到静态数据打表不只是把已知答案写死在代码里更常见的方式是先写一个暴力程序在自己电脑上运行生成答案表然后把表嵌入提交的代码中。这样既保证了正确性又不需要在评测机上现场计算。#include cstdio // 已预生成的卡特兰数n1..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 就跑 DFSN 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 分。本文还有配套的精品资源点击获取