口胡记录

先开个坑，不一定填。

主要记录一些口胡了但是没写的题。

String

题面：

给定两个字符串 \(a\), \(b\), 我们称这两个字符串的所有子序列为坏字符串。求最短的非坏字符串。

做法：

首先要解决一个问题，假设你有一个字符串你需要判断这个字符串是否是坏的，怎么快速判断？

我们预处理出 nxta[i][j] 表示 \(a\) 字符串中第 \(i\) 个位置之后第一个 \(j\) 字符出现的位置。

\(b\) 字符串同理。

我们判断时只需要扫一遍当前的字符串，并用 nxt 数组在 \(a\), \(b\) 上跳，如果都跳出去了，那么就是好串，反之坏串。

那么怎么算最短的这个串呢？

考虑 \(\text{dp}\)。

f[i][j] 表示最短的最后一位等于 \(a[i]\), \(b[j]\)，的字符串长度。

假设当前字符串 \(a\) 枚举到位置 \(i\)， \(b\) 枚举到位置 \(j\)，第 \(i + 1\) 位填 \(x\)，转移式子： f[nxt[i + 1][x]][nxt[j + 1][x]] = f[i][j]。最后我们要的答案就是 f[n + 1][m + 1]。

但是这个很对的做法，时间复杂度是 \(O(26 \times n^2)\)，只能获得 \(80\) 的高分。

\(100\) 分也很简单啊，直接将答案和第 \(2\) 位交换一下，注意到答案不会超过 \(\frac{n}{26}\)。

那么我们的转移式子要改变一下，假设当前字符串 \(a\) 枚举到位置 \(i\)，答案字符串长度为 \(j\), 下一位 \(x\)：

f[nxt[i + 1][x]][j + 1] = max{nxt[f[i][x] + 1][x]}。最后只要判断 f[i][j] >= m+1 是否成立即可。

Pack

题面：

给定一个长度为 \(n\)，元素只有 \(1\), \(2\) 元素的序列，你需要将这些元素按顺序装箱，每个箱子的大小为 \(w\)，你可以进行一次操作：取出若干个元素将其随意排序放到最后。问最少需要多少个箱子？

做法：
一个细微的转化，将取出若干个元素将其随意排序放到最后，转化为选出若干元素，按顺序放入，剩下的元素放到最后做决定。（真的是如转化啊）

考虑 \(\text{dp}\)。

f[i][j] 表示前 \(i\) 个数选 \(j\) 个按顺序填所需要的最少车辆数。

g[i][j] 表示前 \(i\) 个数选 \(j\) 个按顺序填最后一辆车最多能剩下多少空间。

转移显然。

前面的所有元素装好之后，因为剩下的元素我们可以按任意顺序放，所以我们贪心的放，先放 \(2\)，放不了了我们再放 \(1\)，再继续放 \(2\)......。