2024/10/2

前言

主要是做了 CSP-S 2022，并成功比前两年的我进步了不少，起码有一等了。

• 当年我确实是拿了不可以总司令的 $45pts$。

• 为什么考试的题面都那么长啊，不想读一点...

---

[CSP-S 2022] 假期计划

闲话

现在看来确实是挺简单的...

Solution

一开题时想简单了，以为可以floyd/dijkstra+dp解决，后面打完后测样例时发现会出现一个问题：就是它所要求的景点是不同的，但是在dp时，可能会重复选择同一个点，这种方法就被pass掉了。

数据大小肯定是可以用 $n^2$ 的方法过掉的，直接暴力的话时间复杂度是 $O(n^4)$ 的；

但题目很好心，要求从点 $1$ 出发最终又要回到点 $1$，这就提示我们A和D景点的候选点是可以预处理出来的，且点A与点D的性质是相同的；

尝试用 $p_{i,0/1/2}$ 分别记录与点 $i$ 距离符合条件的点中分数最大，次大，次次大的点。

Q：为什么要记录三个呢？

A：后面枚举点B，匹配点A时不能匹配到点C，需避免出现与点B距离符合条件的点中分数最大的点是点C的情况，所以需要次大值；

同样的，在枚举点C，匹配点D时，不能匹配到点A，也不能匹配到点B，最坏情况下点A和点B都是最大和次大分数的点，避免这种情况，我们需要引入次次大值。

那么最后只需要暴力枚举点B和C，并打擂台取所有方案数的最大值即可。

---

[CSP-S 2022] 策略游戏

闲话

当年硬磕没磕出来的题...

• 我竟然打了 4k 多的代码长度...

• 要多注意算术运算爆long long/int。

Solution

很容易想出来是个贪心的心理博弈题，啊啊啊，大分讨，类别很多，但不难想，这边不做详细分析；

我们需要用线段树维护区间极值（也可以用st表，也不多说了，详细见代码...

重点是我没一次过！！！为什么呢？后来拿出数据发现是爆long long了，那时我就疑惑了，打代码时我也注意了这个问题，到底哪里出错了，后面发现是漏了一个细节点没注意（教训）...

---

[CSP-J2019 江西] 道路拆除

闲话

• 原来dijkstra+优先队列优化时间复杂度是 $O((n+m)logm)$的，$O((n+m{)}^{2}logm)$ 过不了 $n,m\le 3000$。

• 凡是多条路径以后都要考虑重复的部分...

Solution

一开始以为跑一边dijkstra，找路径标记并计算贡献即可，后面发现这不一定是最优的，有可能两条路径会走重复的一段路再分开，自己画图分析；

又不能对每个点都跑dijkstra，会超时，那不妨只从点 $1$，$s_1$ 和 $s_2$ 开始跑最短路，再暴力枚举点 $i$，判断以点 $i$ 为中转站（断点）是否能在 $t_1$ 和 $t_2$ 的时间内跑完，若可以，则取符合条件集合中的总路径长度最小的。

---

[CSP-J2019 江西] 非回文串

Solution

这还是很好想的，正难反则易，考虑用总方案数减去回文串的方案数即可，利用回文串左右两边的对称性，分别对每种字母分别单独讨论求组合数，最后用乘法原理乘起来，就是回文串的个数。

---

[USACO08MAR] Pearl Pairing G

闲话

看到题解时怀疑自己脑子是废的...

Solution

有一种贪心是出现数量最多的和最少的匹配；

另一种贪心本蒟蒻竟然一眼没看出来！！！

因为保证有解，所以种颜色出现的数量肯定不会大于 ${\displaystyle \frac{n}{2}}$，那不妨把整个序列按输入的顺序分成前后两部分，一一配对即可，感性画图理解一下，肯定不会被hack。