CSP-J 2023 解题报告

零、背景

有人问我一个算法，一看是最短路。
代码写完了找了一个OJ 来提交代码，然后发现这道题是 CSP-J 2023 的最后一道题。
干脆 CSP-J 2023 的四道题都做一下，写一个题解。

一、小苹果（apple）

题意：n个苹果，每一轮隔2个拿走一个，问多少轮可以拿完苹果，另外最后一个苹果是第几轮拿走的。

思路：每一轮苹果少三分之一，大概需要log(n)轮才能拿完，可以模拟即可。

对于每一轮，假设当前轮有 k 个苹果，则可以拿走 1 + (k - 1) / 3个苹果。
如果最后一个苹果还没拿走，且 k%3 等于 1，则最后一个苹果这一轮可以拿走。

如果还有苹果，轮数加一，继续上面的模拟即可。

复杂度：O(log(n))
代码: https://qoj.ac/submission/602156

二、公路（road）

题意：一条公路有 n 个价格独立标价的加油站，你有一个无限大的油箱，问走一遍公路，最低需要多少油钱。

思路：由于油箱无限大，如果要加油，肯定选择前面价格最便宜的加油站提前加油。

分析所有加油站的关系，最终选择的加油站是递减单调栈。

假设单调栈是 a0,a1,a2,...,ak。
性质1：a0>a1>a2>...>ak
性质2：[ai,ai+1) 之间的加油站价格都高于 ai，从 ai 开到 ai+1 如果缺油，需要从 ai 加油。

如何到单调栈呢？

算法1：二分+线段树。

起始位置在 a0，通过二分可以找到 a1，并计算出 a0 开到 a1 需要加的油。
之后不断的从上个选择的加油站二分找到下个加油站，计算油钱即可。
复杂度：O(n log(n))

算法2：循环判断。

直接循环比较，找到下个加油站即可。
复杂度：O(n)

算法3：逆向思考

有一个故事：前面有一个又大又美的稻田,你只要往前走,一路走不能回头,如何才能选到一个你觉得最大最美的稻穗。
由于无法回头，这个没有最优答案。

如果可以回头，你会怎么做呢？
分别看每一段路，如果要加油，回头看那个加油站最便宜，时光回退回去，提前加好油，是不是就行了？
解法：标记经过的价格最便宜的加油站价格。
复杂度：O(n)
代码: https://qoj.ac/submission/602176

三、一元二次方程（uqe）

题意：给一个一元二次方程ax^2 + bx + c = 0,(a != 0)，按要求输出最大的解。

要求如下：
1）无解时，输出 NO
2）有解时，输出最大的解。
2.1）解是有理数时，输出最简的有理数形式。
2.2）解是无理数时，根号内需要是最简的整数。

思路：按题意模拟即可。

第一步，先标准化方程。
即使得 a 大于0。
另外，求出 a,b,c 的最大公约数，使得 a,b,c 的最大公约数未1。

第二步，判断是否游街。
即求出 ∆=b2 − 4ac，判断是否小于0。

第三步，输出一个解的情况。

第三步，输出有理数解。
当有多个解时，较大的解为(−b+√∆)/(2a)。
先判断是否可以开根号是否可以得到有理数解。
有了，计算出分子和分母，求最大公约数，消除后，输出有理数解。

第四步，输出无理数解。
没有有理数解时，根号里拆分为 k*d*d, 并将 d 提取出来，得到 (−b+d√k)/(2a)。
进而可以拆分为 −b/(2a) + d√k/(2a) 如果 b 不为0，则可以输出 −b/(2a)。
对于 d√k/(2a),需要先求出 d 与 2a 的最大公约数来化简，之后输出即可。

复杂度：O(1)
代码地址: https://qoj.ac/submission/603877

四、旅游巴士（bus）

题意：一个旅游园区加上入口与出口共有 n 个地点，园区内有若干路径连接着这些地点，但是路径在指定时间之后才开放。
大巴车每隔k个单位时间路过入口与出口，问游客坐大巴车到达入口后，如何走，才能到达出口时恰好可以坐上大巴车。
如果可以，输出最早的时间。

思路：先看题目的限制与要求。

入口：每隔k个单位时间可以进入入口。
出口：必须在地k个单位时刻走出出口，不能提前出来停止等待。
路径：部分路径大于等于某个时刻才能走。
路径代价：1个单位时刻

针对上面的限制和要求，可以推导出一些结论。

结论1：不考虑任何限制，入口与出口是连通的时才有答案。

结论2：如果时刻 t 可以到达一个地点，则 t+bk 时刻都可以到达这个地点。
对于到达这个地点的所有时刻，可以分为 k 组， 每组只需要保存最小的到达时刻 t 即可。

结论3：如果时刻 t 到达一个地点1，地点1到达地点2的路径的开放时间是 a，且 t<a，则此时无法通过这条路径。
根据结论2，每隔 k 个时间还可以到达当前地点，所以可以找到最小的T,使得 T=t+bk>=a。
这样T 时刻就可以通过这条路径，从而 T+1到达地点2。

有了上面的三个结论，就可以发现，这个是一个最短路题。
只是每个定点可以到达 k 次，对应的时刻分别为 [0, k) + bk，可以通过二维数组来标记到达的最小时刻。

最短路一般使用 bfs 来求解，只有时刻更优时才能入队列。

为了做到每次先计算最小时刻的点，需要使用优先队列来储存数据。
对于出队的重复的时刻点，有更优答案时，代表前面已经计算过，直接丢弃即可。

当然，直接使用队列也没问题。
这个时候，出队遇到重复的时刻点，更优答案可能在队里后面还没处理。
此时可以选择丢弃，或者修正时刻为当前最优时刻。

复杂度：O(max(m, nk))

代码地址：
队列：https://qoj.ac/submission/614551
优先队列: https://qoj.ac/submission/601659

五、最后

总的看来，这次比赛四道题题型分别为数学计算、单调栈、模拟、图论最短路。
难度都不大，大家把基本算法知识掌握之后，做出这几道题都没问题。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code