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

A.Little Gyro and Sort

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

B. Little Gyro and Sets

先求出 $\left[1,m\right]$ 之间有多少个数是 $\mathit n$ 的倍数, $cnt=\frac{m}{n}$ ,然后用等差数列求和公式分别求出 $\left[1,m\right]$ 中所有
数的和 $\text{sumB}$ 和 $\left[1,m\right]$ 中所有n的倍数的数的和sumA,答案为 $sumB-2\times sumA$ ,注意数据要开 $\text{long long}$
复杂度 $\mathit O(1)$

C. Little Gyro and Numbers

对式子取 $\mathit{ln}$ ，得到 $ylnx \gt xlny$ ，则 $\frac{y}{lny}\gt \frac{x}{lnx}$ 。
不考虑精度误差的话，按这个值排序即可。
如何避免精度误差呢？——考虑 $\frac{x}{lnx}$ 的单调性
求导后大家会发现导函数的极值点是 $\mathit e$ ，所以如果所有数字都大于 $\mathit e$ 的话，直接排序就好了。这时有两个例外： $\mathit 1$ 和 $\mathit 2$ ，提前拿出来特判算答案贡献即可。
一些corner case： $\mathit ln1=0$ , $2^4=4^2$
复杂度 $\mathit O(nlogn)$

D. Little Gyro and Array

维护一个差分数组 $\mathit b$ ,初始值为 $\mathit0$
对于区间 $\left[l,r\right]$ 加等差数列 $d\times x+k$ 的操作， $b\left[l\right]+=k$ , $b\left[x\right]+=d$ , $(l\lt x \leq r)$ , $b[r+1]-=k+(r-l)\times d$
对于单点 $\mathit p$ 查询： $ans=a[p]+b[1]+\dots+b[p]$
注意更新时的边界条件
复杂度 $\mathit O(mlogn)$

E. Little Gyro and Derrick

模拟可知棋盘边缘是否小于5即可。
复杂度 $\mathit O(1)$

F. Little Gyro and Sequences

模板题，通过 $\text{Dilworth}$ 定理将问题转化，把上升最小划分问题转化为最长不上升子序列问题，即可以理解为最经典的导弹拦截问题。注意本题需要采用二分优化的 $\text{DP}$ 算法才能通过。
复杂度 $\mathit O(nlogn)$

G. Disk Scheduling

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

H.Monster Fighting

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

I.Logs Stacking

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