竞赛总览

CSDN 编程竞赛五十四期:比赛详情 (csdn.net)

吐槽:又是一期原题竞赛,四道题都做过无数次了……

竞赛题解

题目1、陶陶摘苹果

陶陶家的院子里有一棵苹果树,每到秋天树上就会结出十颗苹果。苹果成熟时,陶陶会跑去摘苹果。陶陶有个三十厘米高的板凳,当她不能直接用手摘到苹果的时候,就会踩到板凳上再试试。现在已知苹果到地面的高度,以及陶陶把手伸直的时候能够达到的最大高度。请帮陶陶算一下她能够摘到的苹果的数目(假设她碰到苹果,苹果就会掉下来)。

这道题完全是一道签到题。将陶陶能达到的高度加上板凳的高度,得出最大高度。苹果的位置只要小于最大高度就能摘到,一个循环即可解决。

题目2、交际圈

小明参加了个大型聚会,聚会上有n个人参加,我们将他们编号为1到n。有些人已经互相认识了,有些人还不认识。聚会开始后,假设A跟B认识,A会给所有他认识的人介绍B。原先跟A认识,但不认识B的人,都会在此时跟B互相认识。当所有人都把自己认识的人介绍一遍后,此时n个人就会形成k个交际圈。同一个交际圈中,两两互相认识;不同的交际圈之间,互相不认识。当所有人都把自己认识的人介绍一遍后,形成了多少个交际圈?

已经反复出现多次的并查集问题。

题目3、编码

编码工作常被运用于密文或压缩传输。这里我们用一种最简单的编码方式进行编码:把一些有规律的单词编成数字。字母表中共有二十六个字母a到z,这些特殊的单词长度不超过6且字母按升序排列。把所有这样的长度相同的单词放在一起,按字典顺序排列,一个单词的编码就对应着它在整个序列中的位置。你的任务就是对于所给的单词,求出它的编码。

第十四期出现过的原题。

题目4、选择客栈

丽江河边有n家很有特色的客栈,客栈按照其位置顺序从1到n编号。每家客栈都按照某一种色调进行装饰(共有k种,用整数0到k-1表示)。且每家客栈都设有一家咖啡店,每家咖啡店均有各自的最低消费。两位游客一起去丽江旅游,他们喜欢相同的色调,又想尝试两个不同的客栈。因此,他们决定分别住在色调相同的两家客栈中。晚上,他们打算选择一 家咖啡店喝咖啡,要求咖啡店位于两人住的两家客栈之间(包括他们住的客栈),且咖啡店的最低消费不超过p 。他们想知道,总共有多少种选择住宿的方案,保证晚上可以找到一家最低消费不超过p元的咖啡店小聚。

和第一题一样,NOIP上古原题。关于这道题,已经有很多人写过各种各样的方法了,这里就不再写了,感兴趣的小伙伴自行查找NOIP题集即可。

05-25 03:03