20250827 总结 - 洛谷保存站

拿到题，旁边的都说全做过，直接懵了。

---
前三题写的比较简略，因为考场都快想到正解了。

# T1
[P2679 [NOIP 2015 提高组] 子串](https://www.luogu.com.cn/problem/P2679)。

## 考场想法
```
f[i][j][k] 表示现在到了 i，已经选了 j 个子串，B 已经填到了 k

f[i][j][k] = f[i-1][j][k] + f[ii][j-1][x-1]

然后滚动数组优化。

但还是要 TLE，先写完暴力再说。
```

然后考试数据没洛谷强，然后 AC 了。

考场上很多人没有算空间，然后直接 MLE $0$ 分，所以一定要注意空间。

当时还好想到了滚动数组。

## 思路
我考试的思路有点问题，但是很接近了，可以加上前缀和优化。

```cpp
f[j][z]=(f[j][z]+(sum[j][z]=a[i-1]==b[j-1]?sum[j-1][z]+f[j-1][z-1]:0))%mod;
```

## 总结
dp 先暴力，然后再优化。

优化需要优化时间和空间。

如果能过大样例，基本上卡掉你的数据就很少，$80$ 或 $90$ 基本没问题。

# T2
[P1315 [NOIP 2011 提高组] 观光公交](https://www.luogu.com.cn/problem/P1315)。

只有 $5$ 分。。。

没有暴力。。。

## 考场想法

```
首先这道题是一条链，差点以为是图然后不会做了
每一次如果接到乘客是向前的，就跟着车走，
否则可以到后面调头，也可直接掉头
直接掉头会让向后的一车人多等
我在干什么？？？A_i<B_i

这样的话对于 k=0 就直接向后走
否则，就需要找出走的最多的一些点，可以用差分计算
但是会有等乘客的时间，不过车只能向后开

重新梳理思路：
我们需要用差分记录每一个点对答案的贡献
然后遇到等待的情况还需要判断
因为在只有对这个之前下车的旅客有贡献
所以需要在要等待时更新贡献为等待之前的旅客

先写出 k=0 的代码

3 3 0
 1 4
 0 1 3
 1 1 2
 5 2 3

能不能二分答案，二分当贡献值为多少时总和最小
check 只需要判断是否每一个贡献值小于 mid 的都用上了。
好像没有大问题
```

现在看来思路还是比较乱。

甚至最后我连暴力都没有。

其实我应该先写出暴力，然后这道题 $O(kn^2)$ 的代码能过，只不过后面被我 Hack 了。

## 思路
我现在写的还是 $O(kn^2)$ 的。

我们可以枚举每一个 $k$，然后寻找当前贡献最大的点，然后就在这里使用氮气，重复执行。

这其实我是想到了，但是我并没有直接写，而是选择去写时间复杂度更好的东西了。

之后考场写思路需要写框架，需要干什么，不要直接上算法，然后思路就乱了。

## 启示
从思路中获取暴力，从暴力中获取正解。

# T3
[P1315 [NOIP 2011 提高组] 观光公交](https://www.luogu.com.cn/problem/P1315)。

爆搜有 $90$。
## 考场想法
这道题我想着，反正这道题数据小，搜索还是有分的。

## 思路
其实就是搜索。

听说卡时能 A。

我的搜索没有任何优化，直接当作大模拟来写。

其实有一个比较好的优化，就是枚举向左的数时，如果左边有数，就不需要遍历了。

能优化一半以上的时间。

当时我想到了这个，但是写完代码就忘了。

## 启示
好的发现要记录，很可能有用，即使这是暴力。

# T4
思路差不多 get 了，但是代码还没有写。

## 考场想法
当时我直接求出路径，然后 dp，发现旁边的点也会有影响，所以只能过第二个大样例。

有 $36$ 分，很好了。

其实建图也能骗一些分。

## 思路
设 $f_{x,0}$ 表示跳到节点 $x$ 的最小代价，且最后一步跳了 $1$ 步（从父节点直接跳来）
设 $f_{x,1}$ 表示跳到节点 $x$ 的最小代价，且最后一步跳了 $2$ 步（从祖父节点跳来）
设 $f_{x,2}$ 表示跳到节点 $x$ 的最小代价，且最后一步跳了 $3$ 步（从曾祖父节点跳来）

### 当 $k = 2$ 时

$$
\begin{cases}
f_{x,0} = \min(f_{y,0}, f_{y,1}) + v_x \\
f_{x,1} = f_{y,0}
\end{cases}
$$

其中 $y$ 是 $x$ 的父节点。

#### 转移矩阵
这道题设计的转移矩阵是：$C_{i,j}=\min\{A_{i,k}+B_{k,j}\}$。

$$
[f_{y,0}, f_{y,1}] \times 
\begin{bmatrix}
v_x & +\infty \\
v_x & 0
\end{bmatrix}
= [f_{x,0}, f_{x,1}]
$$

### 当 $k = 3$ 时

$$
\begin{cases}
f_{x,0} = \min(f_{y,0}, f_{y,1}, f_{y,2}) + v_x \\
f_{x,1} = \min(f_{y,0}, f_{y,1} + w_x) \\
f_{x,2} = f_{y,1}
\end{cases}
$$

其中：

- $y$ 是 $x$ 的父节点
- $w_x = \min\limits_{z \in \text{neighbor}(x)} v_z$（$x$ 所有邻居的最小点权）

#### 转移矩阵

$$
[f_{y,0}, f_{y,1}, f_{y,2}] \times 
\begin{bmatrix}
v_x & 0 & +\infty \\
v_x & w_x & 0 \\
v_x & +\infty & +\infty
\end{bmatrix}
= [f_{x,0}, f_{x,1}, f_{x,2}]
$$

#### 初始状态

从起点 $s$ 开始：

$f_{s,0} = v_s,~f_{s,1} = +\infty,~f_{s,2} = +\infty$

----
然后就能用倍增记录状态优化。

正在渲染内容...