GESP 七级游记

记录一下 GESP 的七级，83 分，可以免CSP-J 的初赛了。 不过很遗憾由于时间不够 T2 没优化，不然绝对能上 90

选择判断

这次的选择判断还是很有难度的。 比赛前我看着往年的历次题目基本都要考类相关的概念和应用（像什么类的继承、友元、析构、初始化），然后还特地复习了往年的所有和类相关的题目。 结果——今年类是一个都没考！ 完事考了一堆最小生成树？要知道前几年就最后一道判断会是最小生成树相关，今年直接来两三道？ 还好我粗浅了解过，而且其他题错的不多，才勉强够看。

编程题

这次编程一如既往一黄一绿，我也一如既往做黄做不出绿。

T1 拆分

这次 T1 很有意思。 一开始我看七级题单里至少 $\frac{1}{3}$ 都是动态规划，然后看到疑似有重叠子问题，就高高兴兴写了个一维的动态规划，交了上去，然后不出我所料地 WA 了。反思了一下为什么不能用 DP，主要有两点：

1. 时间复杂度过不去
2. 由于要统计最大值，所以就没法在 DP 里取模，会报 long long

既然 $O(n \sqrt{n})$ 都过不了， $O(n \log{n})$ 的二分也不好写，那就只剩下 $O(n)$ 的贪心或者数学方法了。 但是我反反复复模拟却始终看不出有什么规律可言，因为我还一直陷在 DP 里，分解都是分解为两个数的和再取两个数的最优分解的乘积，直到我写了个纯暴力并输出最终分解成了哪些数的和时才发觉——原来分解出来的只会是 3 或者 2 ！ 然后我就兴奋地写出了先分解 2 直到能被 3 除尽再计算 $3^{\frac{n}{3}}$ ，为了防止爆 long long 还贴心地写了快速幂，可是我终归是忘了快速幂的复杂度在 $1\leq t\leq 10^4$，$1\leq n\leq 10^6$ 下还是会超时，其实也很好解决，预处理一下 3 的幂次的值即可，可惜当时时间所剩不多，慌忙之中也未能想到，真的着实可惜，假如当时想到了的话可以直接多 10 分，上个 90 轻轻松松！

T2 物流网络

这次 T2 确实是有点难了，其实当时我第一时间是有想到最短路的，想过使用 Dijkstra 但是可惜没有想到还有二维的 Dijkstra，因此没想一会就放弃了，然后鬼使神差地，用普通队列加上一堆特判的 BFS 写了个奇奇怪怪的最短路，居然过了 9 个点，就一个卡掉了？这 CCF 的数据真的还是太水了。