普及组题解

A 月相

需要判断的是接下来会变大还是会变小，不如先顺着前面的节奏走，即得到 b+(b-a) ，如果结果为 16 或 -1 ，大于0~15的范围，则考虑变为 14 和 1 即可。

其余情况使用直接得到 b+(b-a) 即可。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49022113

B 间隔

需要注意的是有一些 case 需要讨论：

如 正好成等差数列的情况（尤其是全部相同的情况），不需要插入元素，结果为0。

以及样例里的部分 相等的情况（结果为-1）。

考虑了这些情况之后，暴力枚举差值就可以获得满分，时间复杂度为：

约等于 。

更进阶的做法是：特判了一些 case 之后，本质是一个求相邻元素的 gcd 的问题。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49022111

C 密码锁

完全暴力应该比较容易获得分。

dfs/bfs计数+剪枝可以获得约分。

定义状态为(当前按钮位置, 当前密码输入到第几个)，显然需要枚举范围内的所有可能性，状态数 ，转移复杂度 ，故时间复杂度为 。缓慢的写法可以得到约分。

在真实数据上，稍加剪枝（或卡常）即可通过。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49022109

此外，暴力枚举做一些处理，使复杂度变为 。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49022251

D 上街

对于没有红绿灯的情况，直接使用最短路算法即可，可以得到 分。

对于小范围的地图，可以考虑暴力搜索，有很多逼近正确答案的技巧，甚至随机搜索也可以得到一定的分数。

考虑如何建图：

因为所有红绿灯的总时长都是相同的，可以考虑将红绿灯的相对时间（时间 mod 红绿灯总时长）编码到当前状态中，当前状态为（红绿灯的相对时间，当前路口， 当前朝向），这样的状态可以唯一表示，当前路口可以直接使用 的方式编码，朝向0上1右2下3左。

如果在每个路口之内转移，可以将“是否已通过路口”加入状态，（红绿灯的相对时间，当前路口，当前朝向，是否已通过路口(0=未通过，1=已通过)）。初始状态为（0, (1,1), 朝下，未通过），即(0,0,2,0)。设到状态的最小代价为。

接下来开始详细讨论状态转移：

如果已经通过一个路口，就可以向下一个路口前行了，设为下一个路口，为这段路程的距离，即。

接下来考虑通过路口，向右转的情况相对比较简单， 。

向左和向前需要考虑是否需要等待红灯，等待红灯的时间需要额外计算，设需要等待 秒，代价为 。即 。

以上，我们已经完成了对整个状态转移的讨论，因为状态转移中存在环，对于最短路的寻找需要依赖最短路算法而不能是有向无环图（DAG）的求解。

此外，注意到通过路口后，一定会前往该方向的下一个路口，所以事实上可以删除状态中的“是否已通过路口”，可以节约大约相当大量的时间。

最短路算法中，点数为 ，边数为 ，使用的最短路算法可以通过本题。

P.S: 本题因为造数据的技术原因可能没有卡住SPFA，并由此作者感到了恐惧。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49022106