新版骗分导论（转载+修改）

Vitamin_B · 2023-10-12 11:01:09 · 算法·理论

[TOC]

第1章 绪论

​ 在Oier中，有一句话广为流传：

任何蒟蒻必须经过大量的刷题练习才能成为大牛乃至于神牛。

​ 这就是著名的lzn定理。然而，我们这些蒟蒻们，没有经过那么多历练，却要和大牛们同场竞技，我们该怎么以弱胜强呢？
答案就是：

骗分

​ 那么，骗分是什么呢？骗分就是用简单的程序（比标准算法简单很多，保证蒟蒻能轻松搞定的程序），尽可能多得骗取分数。
​ 让我们走进这本《新版骗分导论》，来学习骗分的技巧，来挑战神牛吧！

第2章 从无解出发

2.1 无解情况

​ 在很多题目中都有这句话：若无解，请输出-1.
​ 看到这句话时，骗分的蒟蒻们就欣喜若狂，因为——数据中必定会有无解的情况！那么，只要打出下面这个程序：

printf("-1");

​ 就能得到10分，甚至20分，30分！
​ 举个例子： NOIP2012第4题，文化之旅
​ 这道题看起来很复杂，但其中有振奋人心的一句话“输出-1”，我考试时就高兴坏了（当时我才初一，水平太烂），随手打了个printf("-1");,得10分。

2.2 样例——白送的分数

​ 每道题目的后面，都有一组“样例输入”和“样例输出”。它们的价值极大，不仅能初步帮你检验程序的对错（特别坑的样例除外），而且，如果你不会做这道题（这种情况蒟蒻们已经司空见惯了），你就可以直接输出样例！
​ 例如美国的USACO，它的题目有一个规则，就是第一组数据必须是样例。那么，只要你输出所有的样例，你就能得到100分（满分1000）！这是相当可观的分数了。
​ 现在，你已经掌握了最基础的骗分技巧。只要你会基本的输入输出语句，你就能实现这些骗分方法。那么，如果你有一定的基础，请看下一章——我将教你怎样用简单方法骗取部分分数。

第3章 “艰苦朴素永不忘”

​ 本章的标题来源于《学习雷锋好榜样》的一句歌词，但我不是想教导你们学习雷锋精神，而是学习骗分！
​ 看到“朴素”两个字了吗？它们代表了一类算法，主要有模拟和DFS。下面我就来介绍它们在骗分中的应用。

3.1 模拟

​ 所谓模拟，就是用计算机程序来模拟实际的事件。例如NOIP2012的“寻宝”，就是写一个程序来模拟小明上藏宝塔的动作。
​ 较繁的模拟就不叫骗分了，我这里也不讨论这个问题。
​ 模拟主要可以应用在骗高级数据结构题上的分，例如线段树。下面举一个例子来说明一下: 排队(USACO 2007 January Silver)
​ 对于这个例子，大牛们可以写个线段树，而我们蒟蒻，就模拟吧。
附模拟程序：

for(int i = 1; i <= q; i++)
{
    scanf("%d%d", &a, &b);
    int min = INT_MAX,max = INT_MIN;
    for(int i = a; i <= b; i++)
    {
        if(h[i] < min) min = h[i];
        if(h[i] > max) max = h[i];
    }
    printf("%d\n",max - min);
}

程序简洁明了，并且能高效骗分。本程序得50分。

3.2 万能钥匙——DFS

DFS是图论中的重要算法，但我们看来，图论神马的都是浮云，关键就是如何骗分。下面引出本书的第2条定理：

DFS是万能的。

​ 这对于你的骗分是至关重要的。比如说，一些动态规划题，可以DFS；数学题，可以DFS；剪枝的题，更能DFS。下面以一道省选题为例，解释一下DFS骗分。
​ 例题：NOIP2005，采药
​ 这题的方法很简单。我们瞄准20\%的数据来做，可以用DFS枚举方案，然后模拟计算出最优解。附一个大致的代码：

void DFS(int d, int c)
{
    if(d == n)
    {
        if(c > ans)
            ans = c;
        return;
    }
    DFS(d + 1, c + w[i]);
    DFS(d + 1 ,c);
}

第4章 骗分的关键——猜想

4.1 听天由命

​ 如果你觉得你的人品很好，可以试试这一招——输出随机数。
先看一下代码：

#include<stdlib.h>
#include<time.h>
//以上两个头文件必须加
srand(time(NULL));
//输出随机数前执行此语句
printf("%d", rand() % X);
//输出一个0~X-1的随机整数。

​ 这种方法适用于输出一个整数（或判断是否）的题目中，答案的范围越小越好。让老天决定你的得分吧。
​ 据说，在NOIP2013中，有人最后一题不会，愤然打了个随机数，结果得了70分啊!!

4.2 猜测答案

​ 有些时候，问题的答案可能很有特点：对于大多数情况，答案是一样的。这时，骗分就该出手了。你需要做的，就是发掘出这个答案，然后直接输出。
​ 有时，你需要运用第3章中学到的知识，先写出朴素算法，然后造一些数据，可能就会发现规律。 ​ 例如，本班月赛中有一道题：

题目: 炸毁计划

【问题描述】
皇军侵占了通往招远的黄金要道。为了保护渤海通道的安全，使得黄金能够顺利地运送到敌后战略总指挥地延安，从而购买战需武器，所以我们要通过你的程序确定这条战略走廊是否安全。
已知我们有N座小岛，只有使得每一个小岛都能与其他任意一个小岛联通才能保证走廊的安全。每个小岛之间只能通过若干双向联通的桥保持联系，已知有M座桥(A_i,B_i)表示第i座桥连接了A_i与B_i这两座城市。
现在，敌人的炸药只能炸毁其中一座桥，请问在仅仅炸毁这一座桥的情况下，能否保证所有岛屿安全，都能联通起来。
现在给出Q个询问C_i，其中C_i表示桥梁编号，桥梁的编号按照输入顺序编号。每个询问表示在仅仅炸毁第C_i座桥的情况下能否保证所有岛屿安全。如果可以，在输出文件当中，对应输入顺序输出yes，否则输出no（输出为半角英文单词，区分大小写，默认为小写，不含任何小写符号，每行输出一个空格，忽略文末空格）。

【输入格式】
第一行三个整数N，M，Q，分别表示岛屿的个数，桥梁的个数和询问的个数。
第二行到第M+1行 每行两个整数。第i+1行有两个整数A_i,B_i表示这个桥梁的属性。
第M+2行有Q个整数C_i表示查询。

【输出格式】