当前位置:首页 >> 学科竞赛 >>

noip2012 解析


noip2012

day 1
01
vigenere p1431

02 03

game p1432

drive p1433

名次 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

vigenere 100 100 100 30 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100

game 100 60 50 80 20 60 50 60 50 40 20 60 50 60 40 40 20 0 50

drive 30 65 70 70 70 70 70 5 70 60 70 70 0 70 65 5 65 50 60

管窥noip2012 day1

管窥noip2012
? 我们可以看到,第一天的题目通常都是比 较水的。以去年的题目为例,第一天的基 本分数应该在140(100+40+0)~210 (100+40+70)左右。这是一个比较正常或 者说理想的成绩。

? 这140~210是怎么拿到的?下面我们就具体 分析每一道题目。

vigenre p1431
? 思路:一个基本的找规律+模拟。读懂题目的意思 则是关键。 ? 题目的大概意思是根据指定的规则,构造密码, 已知密钥(k)和密文(c),求明文(m)。 ? 从题目中可以发现很多种规律,而下面提供的则 是其中一种思考方向。

vigenere p1431
? 审题之后发现,输入仅包含大小写字母。而大小 写字母又是以ASCII码的形式存储的,所以把字母 转换成数字之后再找规律,显然要清晰地多。

? 按照常规,可以先把A~Z以1~26替代,看看会发 生什么变化~~

vigenere p1431
mc k 1 1 2 3 1 2 3 2 ? contents 2 3 4 3 3 4 5 4 4 5 6 5 5 6 7 6 6 7 8 7 7 8 9 8 8 9 10 ...

我们可以很清 楚的看到: m+k-1=c; 则m=c-k+1

4 5
6 7 8 ...

4 5
6 7 8

5 6
7 8 9

6 7
8 9 10

7 8
9 10 11

8 9
10 11 12

9 10
11 12 13

10 11
12 13 14

11 12
13 14 15

vigenere p1431
? 为了使公式更简洁,我们不妨将A~Z设为0~25
mc k 0 0 1 2 3 4 ... 0 1 2 3 4 1 1 2 3 4 5 2 2 3 4 5 6 3 3 4 5 6 7 4 4 5 6 7 8 ...

? 这样我们就得到公式m=c-k。 ? 但是仅仅这样就完了么?m必须要大于等于0。而 当c<k时的情况可能出现么?

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

0
1 2

0
1 2

1
2 3

2
3 4

3
4 5

4
5 6

5
6 7

6
7 8

7
8 9

8
9 ...

9
...

...

3
4 5 6 7 8

3
4 5 6 7 8

4
5 6 7 8 9

5
6 7 8 9 ...

6
7 8 9 ...

7
8 9 ...

8
9 ...

9
...

...

注意右下角! 你发现了什么 问题?
15
16 17 18 19

9
10 11 12 13 14

9
10 11 12 13

10
11 12 13 14

11
12 13 14 15

12
13 14 15 16

13
14 15 16 17

14
15 16 17 18

16
17 18 19 20

17
18 19 20 21

18
19 20 21 22

19
20 21 22 23

20
21 22 23 24

21
22 23 24 25 0

22
23 24 25 0 1

23
24 25 0 1 2

24
25 0 1 2 3

vigenere p1431
? 怎么办?25之后就又从0开始了,即c<k之后,我们之前
的公式就不成立了。所以,我们刚才的公式有一定局限性。
? 25之后又是一个从0到25的循环,我们解决它其实很容易: ? 方案一:加一个if语句就可以了。 ? 方案二:我们是学过数论的oier,换一个高端一点的方法: 同余。那么公式就变成了:m=(c+25-k)%25 ? 同理,我们可以利用这一方法,将密钥也循环使用。

小结和问题
? 一个函数的三要素是定义域,值域和对应关系, 而通常,我们对值域、定义域的关注较少。这是在 数学和信息学中都要注意的。 考虑到全部可能的情况是模拟题的关键,如果漏 掉某一情况那么很可能这道题你就会爆0。。 细节!模拟的题目基本上都没有多大思考的难度, 但一旦你不注意细节,别人就和你拉开了差距。

?

你真的注意到细节 了么?ppt第5页的 标题少了一个‘e’, 你注意到了么? ?

?

对于这样一段没有多高复杂度的代码,你能在 30min内一次写满分么?你能以一种高效的代码形 式写出来而不是加了一堆if语句么?如果你不能, 那么需要如何提高?
是否能以一种特殊形式不用判断密文的大小写?

?

Game p1432
? 思路:一个很经典的贪心模型,但是加了恶心的高精度。 ? 先抛开高精度,该怎么做? 提供几个思路: ? A:问题是求最大的最小,二分加验证的标准问法,可是, 怎么二分,又如何验证? ? B:左手的累乘是单调递增的,所以,我们很容易的想到 按右手排序。那么怎么证明这个思路是正确或错误的? ? C:看数据范围,40%的爆搜貌似也是可以的,你能写成 么? ? D:标准解法...

Game p1432
? 思路:其实是一个很经典的贪心模型,但是加了恶心的 高精度。 ? 可以看到即使交换相邻两个人的位置,前面所有人的左 手积也是不变的。如图*: 我们设n1前的左手积为S,则
求的是max(s/r1,s*l1/r2) ;A式

大臣编号:... n1 n2

交换n1,n2之后,max(s*r2,s*l2/r1);B式 若A<=B,则化简后推出:r1*l1<=r2*l2; 即左右手乘积小的,要放在前面,可保证max 最小

右手:...
左手:...

r1 r2
S l1 l2

小结和问题
? 贪心的问题一般很难证明,有时看似没什么道理但是 却是对的,有时貌似很正确的算法,反而爆了0。最好 的方法就是反证法,多构几组数据验证一下,想想极端 的情况是否符合等等。 贪心问题也是有规律可循的,多做题之后要进行整理, 把题目分分类会好一些。 本题是左右手相乘的问题,如果换成相加、相减或相除 的问题,又该这么做?和原来是否有相同的地方?又额 外需要注意些什么?

?

?

?

考场上实在做不出来就要爆搜或骗分,怎么搜?怎么 骗?提示:P13 的方案B可以试一下。建议学习《骗分 导论》。
作业**:p1134 p1893

?

*:参考:《说说NOIP2012的题》(oj首页有原文) **:参考文章:徐王子浩——《贪心策略在排序中的应用》

Drive p1433
? 思路:好像没什么思路。也没办法输出-1之类的来骗分。 而事实上,这道题纯模拟拿70%。 ? 读懂题目是关键,必须耐下性子把题目读完,认真推一 下样例才能较好的理解题目。 ? 我们可以先预处理,把离每一个点的最近和第二近的点 用结构体或者二维数组存起来。然后构造一个函数,模拟 AB的跳跃。第一问就把每一个点都枚举一遍,比较答案 输出。 第二问则是相当于第一问的一小问。

小结和问题
关于模拟题,我的感觉是尽量能用最优或最简洁的代码来 写。因为这样,我们敲代码和调试的时间才最少。虽然题目 最简单,但并不意味这并不需要思考。也许写一段很优的代 码需要思考很长时间,但是它却能省下你大多数调试的时间。 很多时候,一旦杂乱的代码调试的时间是很长~~~~~~~~~~~ 的。 比如这一道题就是这样。在写代码时,将A,B跳跃的步骤写 成相互迭代的函数,这样,不仅代码清晰,不相互纠缠,而 且,在第二问中可以再次调用。这样一段代码就解决了两问, 性价比非常高。 同样能提高效率的是在演草纸上把每一种可能的情况写出来, 再照着列举的情况来写,就不会漏写了。 1、你能在1h30min内写完70分的模拟么? 2、根据AB的这种特殊跳跃,你还能想到那些方式来模拟? 这种跳跃方式类似于什么结构?

day 2
01
mod p1434

02 03

classroom p1435

blockade p1436

名次

mod

classroom

blockade

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

管窥noip2012 day2

100 100 100 100 100 100 70 100 60 70 70 60 100 60 50 100 100 100 60

70 70 70 90 80 40 45 90 80 40 75 45 80 40 75 80 40 70 40

10 0 0 0 0 0 30 10 0 30 0 0 0 0 0 0 0 0 0

管窥noip2012 day2
? 第二天的题目,通常来说难度要大一点,但并不 意味着我们不能拿到一个很好的分数。第二天的 基本分数,应该100(60+40+0)~110(60+50)左 右。

mod p1434
? 在认真学过数论的同学看来,这道题目仅 仅是一道基本的扩展欧几里得。

? 公式的化简是非常必要的。化简过后才会 有基本的算法体现,根据化简之后的式子 ax+by=1,我们可以得到两种算法: ? A:40%,将ans从1开始试,每次+1,直 到试出来为止; ? B:60%,将ans从1开始试,但是每次加

classroom p1435
? 这道题很容易理解,只是在区间上进行操 作。但是如果没有一定基础,AC的算法还 是不容易想到。

? 解法: ? A:45%左右,O(m*n)按照题目要求, 一步一步来,当成一个模拟。很好写,人 品好的话,分数可能更高。
? B:85%左右,线段树的写法,当做基本的 线段树的模板题。

classroom p1435
? 标准解法: ? 首先我们考虑的是如何快速的在一 段区间上修改(包括增加和减少)。线段 树可以,离散化也可以,而且时间复杂度 是O(n)的,比线段树还高。 ? 所谓离散化,是指把原本混在一起 的操作分开进行,类似于矢量的分解。在 线段(区间)的操作中,一般指添加和删 除,我们可以进行离散。 ? 添加:整个区间为(A,B)在(a,

classroom p1435
? 快速的维护区间问题已经解决,剩下的就

是如何确定订单编号。 ? 尝试理解下面的“推论”: ? 1、若前i个订单不能被满足,则之 后 ? 的订单一定不能被满足; ? 2、若前i个订单可以被满足,则之 前的

blockade p1436

? 做人要懂得放弃...

总 览 noip 2012

? 总的来说2012年的题目,想要 仅靠基本分数拿到1=(河南 285分 29人)是比较困难的, 但是并不是没有可能(比如 2012年的第16、30名)。需要 我们有过硬的代码能力。

? 一定的信息学思考方向 (game)、数学(mod)、及 高级数据结构(classroom)等 也是必不可少的,这会让我们 在noip中轻松许多。 ?


相关文章:
noip 2012 提高组 解题报告
noip 2012 提高组 解题报告_学科竞赛_高中教育_教育专区。noip 2012 提高组 解题报告 Vigenère 密码模拟注意大小写 var i,l,t:longint; a:Array[0..1000] ...
NOIP2012初赛第3题解析
NOIP2012初赛第3题解析_英语考试_外语学习_教育专区。NOIP2012 初赛试题解析(第 3 题问题求解)上传:朱全民 浏览:144 时间:10-15 http://www.091edu.com/news...
Noip2012普及组解题报告
Noip2012普及组解题报告_学科竞赛_初中教育_教育专区。Noip2012 普及组解题报告 ...2014年在线教育行业分析报告 2014年互联网金融投资行业分析报告20080份文档 权威...
noip20123题解
noip20123题解_计算机软件及应用_IT/计算机_专业资料。F(i, j)表示 1-i 种花摆放 j 盆的方案数 f(n, m)即为所求 ? f (i ? 1, j ? 0){i种花...
NOIP2012提高组答案
NOIP2012提高组day2试题 4页 2下载券N​O​I​P​2​0​1​2...Photoshop的抠图技巧分析©2014 Baidu 使用百度前必读 | 文库协议...
NOIP2012
NOIP2012_电脑基础知识_IT/计算机_专业资料。NOIP2012今日推荐 68...2014教师资格材料分析辅... 2014小学教师资格考试《... 2014年幼儿园教师资格考...
NOIP2012普及组初赛试题和参考答案
NOIP2012 普及组初赛试题和参考答案 发表时间:2012-11-2 8:38:59 来源: 第十八届全国青少年信息学奥林匹克联赛初赛(普及组 Pascal 语言试题) 竞赛时间:2012 年...
NOIP2012普及组复赛解题报告
NOIP2012普及组复赛解题报告_学科竞赛_初中教育_教育专区。第一题:筛选法求素数...2014年建筑幕墙建筑装饰行业分析报告80份文档 家装材料选购攻略 高端水龙头贵在哪儿...
冲刺NOIP2012模拟试题(十四)解析
3页 2下载券 NOIP2012普及组模拟试题... 12页 免费喜欢此文档的还喜欢 ...Photoshop的抠图技巧分析©2014 Baidu 使用百度前必读 | 文库协议...
冲刺CCF NOIP2012模拟试题与解析(普及组)
冲刺CCF NOIP2012模拟试题与解析(普及组)_电脑基础知识_IT/计算机_专业资料。冲刺CCF NOIP2012模拟试题与解析(普及组)冲刺CCF NOIP2012 模拟试题与解析(普及组) 题...
更多相关标签:
noip2012初赛解析 | noip初赛试题解析 | noip2016复赛解析 | noip2016 day1解析 | noip2012提高组复赛 | noip2012普及组复赛 | noip2012疫情控制 | noip2012开车旅行 |