骗分
一、从认识骗分开始
在信息学竞赛中，“骗分”指选手在无法实现完美算法时，通过次优策略或非标准解法获取部分分数的技巧。这一策略源于竞赛中“得分优先”的实战需求，其核心在于利用时间复杂度与编程复杂度的平衡，以最小代价换取最大收益
从竞赛心理学角度看，“骗分”本质是选手对自身能力的理性评估与资源分配的博弈。它要求选手快速识别题目特征，优先解决可实现的子问题，而非执着于完美解。这种策略不仅被竞赛规则允许，更是区分普通选手与顶尖选手的关键能力之一——顶尖选手往往能精准判断何时该“骗分”，何时需全力突破
让我们从这本书开始学习骗分吧！
二、普遍情况骗分
1、善于观察
看到一个题目，我们需要先观察数据范围，不是总的，而是观察每个测试点的数据范围及特殊性质。因为我们要骗部分好拿的分，而不是拿全部分
如果有那个实力谁会来看这个
2、对症下药
找出针对这些数据的方法。
具体有：
小数据：打表、暴力
特殊性质：枚举、分治(分类讨论)
这里再教一下哪些小数据和特殊性质值得骗分，哪些不值得
小数据：
如果我们要暴力处理，那么我们需要计算我们暴力的时间复杂度和空间复杂度并判断是否‘爆了’
如果我们要打表，那我们需要计算要打表情况数。
第3和4测试点表达式长度≤5，虽然看起来小到可以打表，但是实际要枚举上百种情况，而且还要为每种情况计算短路，需要很多时间和脑力，不如想正解。
特殊性质：
我们就需要思考这种特殊情况是否比原来要处理的问题简单，如果分治并没让问题简单化，那就没必要骗
举一个例子：一元二次方程(题目传送门)
这道题容易发现是大模拟，如果直接写的话不仅麻烦，还不一定能在考场上调试出来
这时候我们就需要骗分
先观察数据，注意到特殊性质C：如果方程有解，那么方程的两个解都是整数。
如果有特殊性质C，那么这道题就和洛谷的一道红题求一元二次方程(题目传送门)非常相似，甚至还更简单(因为不用输出5位小数)
相较之下，特殊性质A和特殊性质B就没啥用，因为不管其他项系数怎么变化，只要二次项系数不为0，那解的还是一元二次方程
而这道题的小数据不够打表，且本来就是暴力模拟，所以小数据骗不了分
接下来我们就可以对这些测试点特殊处理，这样我们可以不处理带除号根号等麻烦的情况
代码
#include<iostream>
#include<cmath>
using namespace std;
long long t,m,a,b,c,i,i3;
int main(){
cin>>t>>m;
while(t--){
cin>>a>>b>>c;
i=b*b-4*a*c;
if(i<0)cout<<"NO"<<endl;
else{
i3=max((-b+sqrt(i))/(2*a),(-b-sqrt(i))/(2*a));
cout<<i3<<endl;
}
}
return 0;
}
然后我们就可以用17行代码轻松拿到50分！
而这道题写正解要六七十行，由此看来还不如骗分
三、特殊题目骗分
1、无解情况
很多题目我们都能看到这么一句话
若无解请输出-1
或者是
若没有符合条件的情况请输出NO
每当我们看到这句话，就可以窃喜了，因为题目既然这样说了，那就代表一定有无解或者是不符合条件的情况
这道题只需输出-1，就可以拿到5分
2、测试样例
所有题目都会给你自测样例，然而这些样例不只是能帮你测出bug，有时还能帮你拿分(不过不用指望CCF会这样干)。很多比赛(如美国的USACO),第一个测试点往往都是自测样例，这时，我们只需输出自测数据，就可以拿100分(满分1000),这已经是相当可观的分数了
四、骗分杂谈
1、猜测骗分
所谓猜测骗分，指的是猜测出题人的心思
那该如何猜呢？你要知道，以很多真题来看，出题人为了培养参赛选手的细心意识(...)，会出诸如输出0之类的需要在代码中专门特判的测试点，我们可以利用这一点,专门写针对这些测试点的代码来骗分
直接写这道题或许有难度，但是通过计算临界值我们可以得出这题输出可以达到的最大值unsigned long long刚好存不下
根据经验(你猜哪来的)，出题人为了坑人肯定会出一个这样的数据
这时候我们直接输出18446744073709551616即可拿5分
但是现在有些题是捆绑测试，所以骗的时候小心点!
2、贪心思想
贪分思想(bushi)
我们经常会看到需要动态规划才能解决的问题，但总是想不出状态转移方程
这时，我们可以考虑贪心。贪心一般不能拿全分(拿了是出题人的问题)，但一般可以拿部分分。
以一道经典的DP题为例：
这题在没有做过背包的情况下不好想状态转移方程，但是容易想到可以贪心，时间、价值、性价比都可以，三个都贪，再取max，可以拿20分。
代码：
#include<bits/stdc++.h>
using namespace std;
struct H { int t, v; };
int calc(int T, vector<H> h, bool (*cmp)(H, H)) {
sort(h.begin(), h.end(), cmp);
int s = 0, r = T;
for(int i = 0; i < h.size(); i++) {
if(h[i].t <= r) {
r -= h[i].t;
s += h[i].v;
}
}
return s;
}
bool cmp1(H a, H b) { return a.t < b.t; }
bool cmp2(H a, H b) { return a.v > b.v; }
bool cmp3(H a, H b) { return a.v*b.t > b.v*a.t; }
int main() {
int T, M; cin >> T >> M;
vector<H> h(M);
for(int i = 0; i < M; i++)cin >> h[i].t >> h[i].v;
cout << max({
calc(T, h, cmp1),
calc(T, h, cmp2),
calc(T, h, cmp3)
}) << endl;
return 0;
}
五、万剑归宗
我们可以通过合并上述方法来拿分，有时一种方法可能只能拿5分，但是，多种方法结合起来，可能可以拿到直逼100的分数
比方说，有些题可能既有特殊性质又有测试样例，这时只需
if(输入样例)cout<<输出样例；
else 分类讨论
这里就不多举例了，大家自己体会
六、骗分练习题
Roundabount Rounding B(题目传送门)(
（题库扩充中......）
七、结语
虽然骗分是一种高效的得分手段，但是我还是想说
编译器的严谨胜过千万次侥幸通过，程序运行的精准才是你实力的铿锵回响。
(完)
C24chenzebang LV 6 @ 2025-8-24 8:24:55
