【题解】第二届中国计量大学ACM程序设计竞赛个人赛(同步赛)

A.Little Gyro and Sort

所谓排序签到题,用桶排序或基数排序在本题中大概率可通过,其他算法均有超时的风险。
本题输入输出数据量很大,建议采用快速的读入方式,或通过读入优化亦可轻松通过本题。
复杂度

B. Little Gyro and Sets

先求出 之间有多少个数是 的倍数, ,然后用等差数列求和公式分别求出中所有
数的和 中所有n的倍数的数的和sumA,答案为 ,注意数据要开
复杂度

C. Little Gyro and Numbers

对式子取,得到,则
不考虑精度误差的话,按这个值排序即可。
如何避免精度误差呢?——考虑的单调性
求导后大家会发现导函数的极值点是,所以如果所有数字都大于 的话,直接排序就好了。这时有两个例外:,提前拿出来特判算答案贡献即可。
一些corner case:,
复杂度

D. Little Gyro and Array

维护一个差分数组 ,初始值为
对于区间加等差数列的操作,,,,
对于单点 查询:
注意更新时的边界条件
复杂度

E. Little Gyro and Derrick

模拟可知棋盘边缘是否小于5即可。
复杂度

F. Little Gyro and Sequences

模板题,通过 定理将问题转化,把上升最小划分问题转化为最长不上升子序列问题,即可以理解为最经典的导弹拦截问题。注意本题需要采用二分优化的 算法才能通过。
复杂度

G. Disk Scheduling

维护一个存当前还需访问磁道的 ,对于当前的磁道位置 ,在 中二分找出比 小的最大的
磁道和比 大的最小的磁道(注意有一边不存在的情况),选取距离最小的磁道,更新 ,在 中删除所选取磁道,并用该值去更新当前的磁道位置 ,直到 为空时算法结束
复杂度

H.Monster Fighting

如果想要打败所有的怪物,首先要对怪物类型进行分类,一种是耗血少回血多的,另一种则相反,耗血和回血数量一样的最好应放在第二类。
虽然我们都知道应根据贪心的原则先处理第一类再处理第二类,但本题的难点在于如何确定每一类的处理顺序。显然,对于第一类应优先处理耗血少的怪物,对于第二类应优先处理回血多的怪物。
复杂度O(nlogn)

I.Logs Stacking

不难看出,由于堆积层数不超过2层,堆积原木的方式满足斐波那契数列的变化规律。
然而,本题的难点在于如何处理在原木数量很大(接近2e9)时的斐波那契数列值,直接求法显然超时;考虑到本题要求对1e4(不是类似于1e9+7的素数)取模,可以找到数列变化的周期为15000,或者采用矩阵快速幂的方法求解。
复杂度O(1)或O(logn)

K.Shuttle Bus

如果想要最快的从A景点搭乘景区班车经过B景点到达C景点,由于中间路途的时间固定,那么应在A景点和到达B景点时找到最早发车的下一趟班车。
由于在景区高峰限流期间,景区管理员可以任意取消k趟班车,最坏情况下,如果k超过当天任意一类型的班车趟次,直接输出Please wait...;
其他情况下,对A景点到B景点被取消的靠前的趟次进行枚举,如果可以搭乘的班车到达B景点后没有后面的班车,或者后面的班车可以被取消,直接输出Please wait...;否则输出最坏情况下最早到达的时间。
复杂度O(nlogn)

L. Stoty of Eden

签到题,字符串的读入读出。
复杂度


全部评论
3 收藏 评论
分享

全站热榜

正在热议