没有合适的资源?快使用搜索试试~ 我知道了~
信息学-骗分导论.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 21 浏览量
2022-05-30
13:40:32
上传
评论
收藏 42KB DOCX 举报
温馨提示
试读
18页
。。。
资源推荐
资源详情
资源评论
新 版 骗 分 导 论
THE NEW GUIDE OF CHEATING IN INFORMATICS OLYMPIAD
目录
第 1 章 绪论
第 2 章 从无解出发
2.1 无解情况
2.2 样例——白送的分数
第 3 章 “艰苦朴素永不忘”
3.1 模拟
3.2 万能钥匙——DFS
第 4 章 骗分的关键——猜想
4.1 听天由命
4.2 猜测答案
4.3 寻找规律
4.4 小数据杀手——打表
第 5 章 做贪心的人
5.1 贪心的算法
5.2 贪心地得分
第 6 章 C++的福利
6.1 快速排序
6.2 “如意金箍棒”
第 7 章 “宁为玉碎,不为瓦全”
第 8 章 实战演练
第 9 章 结语
第 1 章 绪论
在 Oier 中,有一句话广为流传:
任何蒟蒻必须经过大量的刷题练习才能成为大牛乃至于神牛。
这就是著名的 lzn 定理。然而,我们这些蒟蒻们,没有经过那么多历练,却要和大牛们同场
竞技,我们该怎么以弱胜强呢?答案就是:
骗分 那么,骗分是什么呢?骗分就是用简单的程序(比标准算法简单很多,保证蒟蒻能轻
松搞定的程序),尽可能多得骗取分数。
让我们走进这本《新版骗分导论》,来学习骗分的技巧,来挑战神牛吧!
第 2 章 从无解出发
2.1 无解情况
在很多题目中都有这句话:“若无解,请输出-1.”
看到这句话时,骗分的蒟蒻们就欣喜若狂,因为——数据中必定会有无解的
情况!那么,只要打出下面这个程序:
printf(“-1”);
就能得到 10 分,甚至 20 分,30 分!
举个例子:
NOIP2012 第 4 题,文化之旅
题目描述 Description
有一位使者要游历各国,他每到一个国家,都能学到一种文化,但他不愿意学习任何一种文
化超过一次(即如果他学习了某种文化,则他就不能到达其他有这种文化的国家)。不同的
国家可能有相同的文化。不同文化的国家对其他文化的看法不同,有些文化会排斥外来文化
(即如果他学习了某种文化,则他不能到达排斥这种文化的其他国家)。
现给定各个国家间的地理关系,各个国家的文化,每种文化对其他文化的看法,以及这位使
者游历的起点和终点(在起点和终点也会学习当地的文化),国家间的道路距离,试求从起
点到终点最少需走多少路。
输入描述 Input Description
第一行为五个整数 N,K,M,S,T,每两个整数之间用一个空格隔开,依次代表国家个数
(国家编号为 1 到 N),文化种数(文化编号为1 到 K),道路的条数,以及起点和终点的编
号(保证 S 不等于 T);
第二行为 N 个整数,每两个整数之间用一个空格隔开,其中第i 个数 Ci,表示国家 i 的文化
为 Ci。
接下来的 K 行,每行 K 个整数,每两个整数之间用一个空格隔开,记第 i 行的第 j 个数为 aij,
aij= 1 表示文化 i 排斥外来文化 j(i 等于 j 时表示排斥相同文化的外来人),aij= 0 表示不排斥
(注意 i 排斥 j 并不保证 j 一定也排斥 i)。
接下来的 M 行,每行三个整数 u,v,d,每两个整数之间用一个空格隔开,表示国家 u 与
国家 v 有一条距离为 d 的可双向通行的道路(保证u 不等于 v,两个国家之间可能有多条道
路 )。
输出描述 Output Description
输出只有一行,一个整数,表示使者从起点国家到达终点国家最少需要走的距离数(如果无
解则输出-1)。
样例输入 Sample Input
输入样例 1
2 2 1 1 2
1 2 0 1 1 0 1 2 10 输入样例 2
2 2 1 1 2
1 2 0 1 0 0 1 2 10 样例输出 Sample Output
输出样例 1
-1 输出样例 2
10 数据范围及提示 Data Size & Hint
【输入输出样例 1 说明】
由于到国家 2 必须要经过国家 1,而国家 2 的文明却排斥国家 1 的文明,所以不可能到达国
家 2。
【输入输出样例 2 说明】
路线为 1 -> 2。
【数据范围】
对于 20%的数据,有 2≤N≤8,K≤5;
对于 30%的数据,有 2≤N≤10,K≤5;
对于 50%的数据,有 2≤N≤20,K≤8;
对于 70%的数据,有 2≤N≤100,K≤10;
对于 100%的数据,有 2≤N≤100,1≤K≤100,1≤M≤N2,1≤ki≤K,1≤u,v≤N,1≤d≤
1000,S≠T,1 ≤S, T≤N。
这道题看起来很复杂,但其中有振奋人心的一句话“输出-1”,我考试时就高兴坏了(当时
我才初一,水平太烂),随手打了个 printf(“-1”);,得 10 分。
2.2 样例——白送的分数
每道题目的后面,都有一组“样例输入”和“样例输出”。它们的价值极大,不仅能初步帮
你检验程序的对错(特别坑的样例除外),而且,如果你不会做这道题(这种情况蒟蒻们已
经司空见惯了),你就可以直接输出样例!
例如美国的 USACO,它的题目有一个规则,就是第一组数据必须是样例。那么,只要你输
出所有的样例,你就能得到 100 分(满分 1000)!这是相当可观的分数了。
现在,你已经掌握了最基础的骗分技巧。只要你会基本的输入输出语句,你就能实现这些骗
分方法。那么,如果你有一定的基础,请看下一章——我将教你怎样用简单方法骗取部分分
数。
第 3 章 “艰苦朴素永不忘”
本章的标题来源于《学习雷锋好榜样》的一句歌词,但我不是想教导你们学习雷锋精神,而
是学习骗分!
看到“朴素”两个字了吗?它们代表了一类算法,主要有模拟和DFS。下面我就来介绍它们
在骗分中的应用。
3.1 模拟
所谓模拟,就是用计算机程序来模拟实际的事件。例如 NOIP2012 的“寻宝”,就是写一个
程序来模拟小明上藏宝塔的动作。
较繁的模拟就不叫骗分了,我这里也不讨论这个问题。
模拟主要可以应用在骗高级数据结构题上的分,例如线段树。下面举一个例子来说明一下。
排 队(USACO 2007 January Silver)
【问题描述】
每天,农夫约翰的 N(1≤N≤50000)头奶牛总是按同一顺序排好队,有一天,约翰决定让
一些牛玩一场飞盘游戏(Ultimate Frisbee),他决定在队列里选择一群位置连续的奶牛进行
比赛,为了避免比赛结果过于悬殊,要求挑出的奶牛身高不要相差太大。
约翰准备了 Q(1≤Q≤200000)组奶牛选择,并告诉你所有奶牛的身高 H(i 1≤ Hi ≤106)。
他想知道每组里最高的奶牛和最矮的奶牛身高差是多少。
注意:在最大的数据上,输入输出将占据大部分时间。
【输入】
剩余17页未读,继续阅读
资源评论
苦茶子12138
- 粉丝: 1w+
- 资源: 6万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功