主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
【置顶】骗分宝典
最后更新于 2025-07-31 11:27:47
作者
guoziyu_2023CSP
分类
个人记录
复制 Markdown
查看原文
删除文章
更新内容
### 第1章 绪论 在Oier中,有一句话广为流传: 任何蒟蒻必须经过大量的刷题练习才能成为大牛乃至于神牛。 这就是著名的lzn定理。然而,我们这些蒟蒻们,没有经过那么多历练,却要和大牛们同场竞技,我们该怎么以弱胜强呢? 答案就是: ## 骗分 那么,骗分是什么呢?骗分就是用简单的程序(比标准算法简单很多,保证蒟蒻能轻松搞定的程序),尽可能多得骗取分数。 让我们走进这本《骗分导论》,来学习骗分的技巧,来挑战神牛吧! ### 第2章 从无解出发 #### 2.1 无解情况 在很多题目中都有这句话:若无解,请输出-1. 看到这句话时,骗分的蒟蒻们就欣喜若狂,因为——数据中必定会有无解的情况!那么,只要打出下面这个程序: ```cpp printf("-1"); ``` 就能得到10分,甚至20分,30分! #### 得10分。 #### 2.2 样例——白送的分数 每道题目的后面,都有一组“样例输入”和“样例输出”。它们的价值极大,不仅能初步帮你检验程序的对错(特别坑的样例除外),而且,如果你不会做这道题(这种情况蒟蒻们已经司空见惯了),你就可以直接输出样例! 例如美国的USACO,它的题目有一个规则,就是第一组数据必须是样例。那么,只要你输出所有的样例,你就能得到100分(满分1000)!这是相当可观的分数了。 现在,你已经掌握了最基础的骗分技巧。只要你会基本的输入输出语句,你就能实现这些骗分方法。那么,如果你有一定的基础,请看下一章——我将教你怎样用简单方法骗取部分分数。 ### 第3章 “艰苦朴素永不忘” 本章的标题来源于《学习雷锋好榜样》的一句歌词,但我不是想教导你们学习雷锋精神,而是学习骗分! 看到“朴素”两个字了吗?它们代表了一类算法,主要有模拟和DFS。下面我就来介绍它们在骗分中的应用。 #### 3.1 模拟 所谓模拟,就是用计算机程序来模拟实际的事件。例如NOIP2012的“寻宝”,就是写一个程序来模拟小明上藏宝塔的动作。 较繁的模拟就不叫骗分了,我这里也不讨论这个问题。 模拟主要可以应用在骗高级数据结构题上的分,例如线段树。下面举一个例子来说明一下: 排队(USACO 2007 January Silver) 对于这个例子,大牛们可以写个线段树,而我们蒟蒻,就模拟吧。 附模拟程序: ```cpp 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\%20%的数据来做,可以用DFS枚举方案,然后模拟计算出最优解。附一个大致的代码: ```cpp 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 听天由命 如果你觉得你的人品很好,可以试试这一招——输出随机数。 先看一下代码: ```cpp #include<stdlib.h> #include<time.h> //以上两个头文件必须加 srand(time(NULL)); //输出随机数前执行此语句 printf("%d", rand() % X); //输出一个0~X-1的随机整数。 ``` 这种方法适用于输出一个整数(或判断是否)的题目中,答案的范围越小越好。让老天决定你的得分吧。 据说,在NOIP2013中,有人最后一题不会,愤然打了个随机数,结果得了70分啊!! #### 4.2 猜测答案 有些时候,问题的答案可能很有特点:对于大多数情况,答案是一样的。这时,骗分就该出手了。你需要做的,就是发掘出这个答案,然后直接输出。 有时,你需要运用第3章中学到的知识,先写出朴素算法,然后造一些数据,可能就会发现规律。 例如,本班月赛中有一道题: 题目: 炸毁计划 你发现问题了吗?那么多座桥,炸一座就破坏岛屿的联系,可能性微乎其微(除非特别设计数据)。那么,我们的骗分策略就出来了:对于所有询问,输出yes.果然,此算法效果不错,得80分。 现在知道猜测答案的厉害了吧? #### 4.3 寻找规律 首先声明:本节讲的规律不是正当的算法规律,而是数据的特点。 某些题目会给你很多样例,你就可以观察他们的特点了。有时,数据中的某一个(或几个)数,能通过简单的关系直接算出答案。 只要你找到了规律,在很多情况下你都能得到可观的分数。 这样的题目大多出现在NOI或更高等级的比赛中,本人蒟蒻一个,就不举例了。传说某人去省选时专门琢磨数据的规律,结果有一题得了30分。 #### 4.4 小数据杀手——打表 我认识一个人,他在某老师家上C语言家教,老师每讲一题,他都喊一句:“打表行吗?” 他真的是打表的忠实粉丝。表虽然不能乱打,但还是很有用的。 先看一个例子:NOIP2003 栈 这题看似复杂,但数据范围太小,N\le18N≤18。所以,骗分程序就好写了: ```cpp int a[18] = {1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790,477638700}; scanf("%d",&n): printf("%d",ans[n - 1]); ``` 测试结果不言而喻,AC了。 学完这一章,你已基本掌握了骗分技巧。下面的内容涉及一点算法知识,难度有所增加。蒟蒻中的蒟蒻可以止步于此了。 ### 第5章 做贪心的人 #### 5.1 贪心的算法 给你一堆纸币,让你挑一张,相信你一定会挑面值最大的。其实,这就是贪心算法。 贪心算法是个复杂的问题,但你不用管那么多。我们只关心骗分。给你一个问题,让你从一些东西中选出一些,你 就可以使用贪心的方法,尽量挑好的。 举个例子:这是我们的市队选拔的一道题。 题目: 有趣的问题 都在int 范围内。 这题让人望而生畏,但我们有贪心的手段。每个二元组的aa值是乘到答案中的,所以aa越大越好,那么只要选择出最小的kk个去掉即可。代码就不写了,因为这个设计到下一章的内容:排序。 此代码得20分。 #### 5.2 贪心地得分 我们已经学了很多骗分方法,但他们中的大多效率并不高,一般能骗10~20分。这不能满足我们的贪心。 然而,我们可以合成骗分的程序。举个最简单的例子,有些含有无解情况的题目,它们同样有样例。我们可以写这个程序: ```cpp if(是样例) printf(样例); else printf("-1"); ``` 这样也许能变10分为20分,甚至更多。 当然,合并骗分方法时要注意,不要重复骗同一种情况,或漏考虑一些情况。 大量能骗分的问题都能用此法,大家可以试试用新方法骗2.1中的例子“文化之旅”。 ### 第6章 C++的福利 #### (请P党们跳过本章,这不是你们的福利) 在C++中,有一个好东西,名唤STL,被万千OIer们所崇拜,所喜爱。下面让我们走进STL。 #### 6.1 快速排序 快速排序是一个经典算法,也是C++党的经典福利。他们有这样的代码: ```cpp #include<algorithm>//这是必须的 sort(A,A+n);//对一个下标从0开始存储,长度为n的数组升序排序 ``` 就这么简单,完成了P党一大堆代码干的事情。 #### 6.2 “如意金箍棒” C++里有一种东西,叫vector容器。它好比如意金箍棒,可以随着元素的数量而改变大小。它其实就是数组,却比数组强得多。 下面看看它的几种操作: ```cpp vector<int> V;//定义 V.push_back(x);//末尾增加一个元素x V.pop_back();//末尾删除一个元素 V.size();//返回容器中的元素个数 ``` 它同样可以使用下标访问。(从0开始) ### 第7章 “宁为玉碎,不为瓦全” 至此,我已介绍完了我所知的骗分方法。如果上面的方法都不奏效,我也无能为力。但是,我还有最后一招——有句古话说:“宁为玉碎,不为瓦全”。我们蒟蒻也应有这样的精神。骗不到分,就报复一下,卡评测以泄愤吧! 卡评测主要有两种方法:一是死循环,故意超时;二是进入终端,卡住编译器。 就是这短短一句话,就能卡住评测机长达10s,20s,甚至更多!对于测试点多、时限长的题目,这是个不错的方法。 第二种方法也很简单,但危害性较大,建议不要在重要比赛中使用,否则可能让你追悔莫及。它就是: ```cpp #include<con> //(windows系统中使用) #include</dev/console> //(Linux系统中使用) ``` 它非常强大,可以卡住评测系统,使其永远停止不了编译你的程序。唯一的解除方法是,工作人员强行关机,重启,重测。当然,我不保证他们不会气愤地把你的成绩变成0分。请慎用此方法。 ### 第8章 实战演练 下面我们来做一些习题,练习骗分技巧。 我们来一起分析一下NOIP2013普及组的试题吧。 记数问题(NOIP普及组2013第一题)(count.cpp/c/pas) 表达式求值(noip2013普及组第二题)(expr.cpp/c/pas) 小朋友的数字(noip2013普及组第三题)(number.cpp/c/pas) 车站分级(NOIP普及组2013第四题)(level.cpp/c/pas) [type1] 第1题,太弱了,不用骗,得100分。 [type2] 第2题,数据很大,但是可以直接输入一个数,输出它mod 10000的值。得10分。 [type3] 第3题,是一道非常基础的DP,但对于不知DP为何物的蒟蒻来说,就使用暴力算法(即DFS)。得20分。 [type4] 第4题,我们可以寻找一下数据的规律,你会发现,在所有样例中,M值即为答案。所以直接输出M,得10分。 这样下来,一共得140分,比一等分数线还高20分!你的信心一定会得到鼓舞的。这就是骗分的神奇。 ### 第9章 结语 骗分是蒟蒻的有力武器,可以在比赛中骗得大量分数。相信大家在这本书中收获了很多,希望本书能帮助你多得一些分。 但是,最后我还是要说一句: 不骗分,是骗分的最高境界。
正在渲染内容...
点赞
7
收藏
0