NOIP 1999 普及组算法题解

零、背景

之前分享了 1997 年和 1998 年的 NOIP 和 NOI 算法比赛题解，今天继续分享 1999 年 NOIP 普及组题解。

PS：代码还没上传网盘，如果需要的朋友，可以留言，我收到留言后上传一下发给你网盘地址。

一、Cantor 表

题意：给一个如下图的公式表格，按 Z 形遍历这些数字，例如第一项是 1/1，然后是 1/2，2/1，3/1，2/2，…
问第 N 项是多少。

思路：数学计算或者模拟。

仔细观察可以发现两个规律。

规律1：每一斜行的数字个数比上一行多一个。
即第一行 1 个，第 2 行 2 个，第 x 行 x 个，依次递推。

规律2：偶数行从右上到左下，奇数行从左下到右上。

因此给一个 N 后，我们可以解方程，计算出有几个完整的行。
对于最后一个不完整的行，先确定方向，然后推导出答案即可。
复杂度：O(1)

如果解方程担心有精度问题，也可以直接模拟每一行，快速定位到最后一行。
复杂度：O(sqrt(N))

二、回文数

题意：给一个 N 进制数字，将数字翻转后与原数字求和，得到一个新的数字。
这样不断重复操作，直到得到回文数字。
问第几次操作才能得到回文数字，如果 30 次内都没得到，则输出得不到。

思路：大整数模拟。

封装一个大整数加法，以及判断是否是回文数的函数，循环模拟即可。

三、旅行家的预算

题意：告诉你始发站到终点的距离，以及中间 N 个加油站的位置与油价。
每升油能开的距离是固定的，问是否可以从始发站开到目的地，可以的话最少花费多少钱。

思路：后悔贪心。

基本思路：先把油箱加满，并记录每一滴油的油价。
走一段路，优先消耗油价最低的油。
如果遇到一个加油站，油价更便宜，则把较贵的油都后悔退还，然后购买这个更便宜的油，最后也需要把油箱加满。
到达终点后，剩余的油全部后悔退还。

根据上面的思路，可以发现我们需要一个单调双向队列，来记录每个油价有多少油。
走一段路程时，消耗队列前面便宜的油。
遇到更便宜的加油站时，把队列后面较贵的油后悔退掉。

小技巧：在终点站追加一个油价为 0 的加油站，这样可以在最后把剩余的油全部后悔换成免费的油。

N 个加油站需要排序，排序最占时间。
复杂度：O(n log(n))

四、最后

1999 年的 NOIP 普及组的题比较简单，第一道 Z 形模拟，第二道大整数模拟，第三道后悔贪心。
其中加油后悔贪心属于经典题型，相信大家都很熟悉了。

《完》

-EOF-

本文公众号：天空的代码世界

个人微信号：tiankonguse

公众号ID：tiankonguse-code