0x00 前言

无论怎样，今年的CSP总算是落下了帷幕。
这一届CSP相较于往年来说，J组没有了DP，S组多了道大模拟。
总体来说，题目的颜色难度可能会下降，但是体感难度并不会。
也真的不得不让人感慨：

0x01 CSP-J

J组毕竟在本校考，还是比较适应的。

T1

首先先看了数据，n \le 10^9必然想到这题要么推式子，要么就是复杂度很小的模拟，这题一看就属于后面那位。
首先，隔两个取走一个，其实就意味着假设有n个苹果，那么取走的个数总会是固定的\left\lfloor\dfrac{n-1}{3}\right\rfloor+1个，至于如何判断取走了最后一个，只需要找到第一个n使得n-1 \equiv 0 \pmod{3}
然后就直接while循环去做就可以了，时间复杂度O(能过),您也可以尝试在n=10^9时运行此程序，会发现第一个输出不到10^5。
考场用时30mins,期望得分100pts.

T2

首先看数据，n \le 10^5看起来就不是让人O(n^2)去做的。
于是，考虑贪心/DP。很显然，DP就是那个O(n^2)的弃子。
那贪心策略是什么呢？
首先我们先给出结论：每一次找到下一个距此最近且价格比其低的加油站，并不断重复这一个过程。
这里，我们定义此站为当前的位置，下一个距此最近且价格比其低的加油站为下一站。
好，接下来我们口胡证明一下：
首先，对于要在下一站前加油的方案，直接PASS掉，WHY?
因为汽车可以搭载无限的油，只要在下一站前加，就是冤大头。
但为什么不是寻找下一站更远的加油站呢？
因为下一站以后的路程，仍然需要由此站提供，那因为下一站的油比此站便宜，所以不如在下一站加油后再走。
但是需要特判，如果此站加的油可以直接供给到下下站，那么下一站就不需要加油。
时间复杂度O(n)，注意需要开启long long。
考场用时约1小时（后面解释），期望得分100pts。

T3

一看题目，一元二次方程，真的是又在欺负初一初二以及小学六年级的小朋友们了。
不过还好题目描述还是很清晰的，至少理解起来并不像下午的CSP-S T3。
这题就是一个大模拟，然后……没了？
考场用时45分钟，期望得分100(?)pts

T4

终于来到最后一题。
第一眼，好像是个图论，竟然没有DP?
然后犹豫了半个小时，反复确定这一次确实没有DP。
然后开始图论。
很显然k \le 100，因此，开一个st[N][K]来BFS，
但是BFS的队列由优先队列实现。
预计得分50-60pts，时间复杂度约O((n+k)log(n+k))
正解给了一个复杂度基本一致的拆点+dijkstra。
只要算法正确性对了，分应该不会太惨。

0x02 CSP-S

先给出总体感受：不是人做的。

T1

$n\le8$，还能干什么呢？比状压还小，那就爆搜喽。
考场用时约$30$min，预计得分$100$pts.

T2

（来自考后，CCF出原题，举报了！链接）
（似乎也不完全是原题）。
没想出来，一直在想优化，结果发现连暴力优化都没想出来。
复杂度O(n^3)，现在想原地升天。
O(n^2)的做法是枚举起点，然后每一次都扫一遍。
正解是O(n)/O(26n)的。
使用HASH+DP。
这么说可能CZY DALAO是对的。
考场用时近1h，预计得分20-30pts.

T3

题目很长，数据很小，就只能是大模拟了。
但是真的很复杂，还出现了各种结构体套结构体的情况。
预计得分0pts.

T4

有了最小，那么肯定就是二分答案，二分答案后，然后去预处理出往前至少几天才能长完。
后面用优先队列优化+树形DP检查。
想到前面，没想到后面，于是后面挂掉了。
预计得分0-15pts.

0x03 总体感受

如果J和S互换一道题，那么这绝对是有史以来最好的一次CSP。