0827总结 - 洛谷保存站

#### 前排提醒
这位作者写总结时习惯形式化题意，个别形式化过长，读者可以选择跳过。
### T1 子串
从$A$中取$k$个子串，使其按序拼接起来与$B$相同。

这题很显然是DP，那么就开始考虑如何转移。

我试着定义过很多次$dp_{i,j,k}$代表什么，但是”大脑“转不过来，想不出转移方程（其中多半都是能写转移方程的，确实是我的问题）。然后一个小时就过去了。

发现浪费了太多时间，我就不想怎么转移是对的了。准确来说，因为“大脑”无法判断怎么转移是对的，所以我直接让“手”来帮忙，用实践的方式看看到底哪种方法能行。

接下来，“手”模出了一种“转移”，因为他没有大脑，所以这个“转移”看起来极其猎奇。考虑到能跑的都是好代码，“大脑”无奈得接受了，然后因为“手”只弄出来了“转移”而非“方程”，所以调试过程痛苦而漫长，再用一小时写出$O(nm^3)$的诡异代码，计算能拿$70pts$。

事实上这份代码是有优化成$O(nm^2)$的潜力的，但因为没有“方程”，“眼睛”对此表示无能为力。

几个问题：不会写转移“方程”；奔着$70pts$去，但数组开得和$100pts$一样大，有$MLE$的风险（冷知识，因为没有“方程”，连滚动数组都做不到）；来自$T3$的背刺，这个到后面再讲。
### T2 观光公交
你是一位观光公交的司机，我们都知道公交能且仅能走一条线（一条链）。有一些游客，他们会从某个时间开始在某个景点等待你的到来，并在后面某一站下车。作为司机，你有义务使每一位乘客去到他们的目的地，所以不能在游客上车前开走车。因为个别讨厌的游客，你和你车上的其他游客都需要等着它们，浪费大家的时间和心情。公司为了防止被投诉，允许你使用若干次氮气加速，可以减少指定两站之间开车的时间（显然不能为负）。你的目标是使所有游客从到站到出站的时间总和最小（和心情相比，时间是可以量化的）。

我在一开始就想到对于每一段路，使用氮气加速的收益不同，排个序取最大的$k$个即可。**但是**这是错的，因为前面的氮气加速会影响后面的，然后就没辙了。

保险起见，先敲了一个$dfs$的暴力，看到过了小样例就以为对了（跑不动大样例），结果没算乘客等车的时间。原本估计是$20pts$，现在看来能拿$30pts$，如果没有那个错误。

实在是没剩多少时间了，我刚好又想到了一个更优的写法，这也是没发现问题的原因之一。新的想法是DP，考虑前$i$个站用$j$个氮气加速的最优解，转移方程什么的都没问题，就差一点写完。但也没什么好悲伤的，因为上一段的问题在这份代码中也有，甚至这份代码的空间超了。

DP的方法调好后，发现只有$30pts$，后面有$WA$，这是因为过早得到站可能会使游客等更久。
### T3 Mayan 游戏
古早的消消乐游戏，要求$n$步内消完所有方块。

本来以为会很恶心，但发现$n\le5$，所以直接暴搜。

只需要一个优化：因为本题要求字典序最小，所以每次都走字典序最小的一步即可，找到答案直接输出就可以结束程序。

唯一的问题：看错了输出格式，导致只拿了无解的分。

啊不，还有一个问题。因为不会在结构体中定义二维数组，所以我把二维数组降为一维数组，使用了$Dev-C++$的黑科技：“替换文件内容”，将所有$[i][j]$替换为$[i*7+j]$，适用范围是所有文件。于是可以揭秘$T1$最后的问题：交之前没有编译。
### T4 数据传输
有一棵树，对于两个节点$u,v$，从$u$跳到$v$，要求每次最多跳$k$步，并最小化途经节点的点权和。

第一眼没思路就打暴力，直接把$u,v$之间的路径拷下来DP，发现过不了样例，因为中途跳的节点不一定在$u$->$v$的路径上。没想到怎么处理，那就只能冷处理了。
### 总结
各种问题不再赘述，下面是改进。

1. 考试预留最少$5$分钟用于检查，包括但不限于：$freopen$，输出格式，能否过编/样例（一定不要只用肉眼观察）。
2. 复习DP关于列转移方程的内容。
3. 写代码前在文件中写上解题思路，写完代码可以一一对应看是否遵守/完成。
4. 写完代码计算时间复杂度和空间复杂度。

正在渲染内容...