日记

窝补药军训啊啊啊啊啊啊啊啊啊啊啊

T1 # Link to T1

一眼。

考虑每个形如 $\texttt{ABB...BBC}$ 或者 $\texttt{CBB...BBA}$ 的特殊子串对答案造成的贡献。显然这两种子串对于包含它的子串都会造成 $1$ 的贡献，于是我们就算有多少个子串包含他们就是了。设这个特殊子串的两个端点分别是 $l,r$，那么显然有 $l \times (n - r + 1)$ 个子串包含这个特殊子串，于是把答案加上 $l \times (n - r + 1)$。

T2 # Link to T2

毕特塞特神力！！！！如题面所说，$O(\frac{n^3}{\omega} \times \log \frac{n^2}{4})$ 是可以过的。

首先，我们有简单的 $O(n^3)$ 区间 dp。设 $dp_{l,r}$ 表示区间 $[l,r]$ 删完的最小代价，转移是平凡的。

然后我们看到 最大值最小，直接想到二分答案。我们二分出来一个 $mid$ 之后，就变成了一个可行性 dp。$dp_{l,r}$ 表示 $[l,r]$ 是否可以在小于 $mid$ 的代价删完。转移和上面的差不多。区别在于：如果 $dp_{l,r}$ 可行，那么如果 $dp_{r,k}$ 可行的话，$dp_{l,k}$ 也可行。这里就可以用 bitset 维护，表现为 dp[l] |= dp[r]。

注意枚举的顺序是 $l$ 从大到小，$r$ 从小到大。

T3 & T4 # Link to T3 & T4

没改，军训回来改。

upd: 军训回来也没改

Endless Knight# Link to

设 $dp_{i}$ 表示从 $(1,1)$ 走到 $(x_i,y_i)$ 不经过别的障碍点的方案书。转移就是这样：$dp_{i} = \operatorname{calc}(x_i - 1,y_i - 1) - \sum_{j = 1}^{j - 1}dp_j \times \operatorname{calc}(x_i - x_j,y_i - y_j)$。分别表示所有方案，枚举第一个遇到的障碍点以算出不符合的方案。$\operatorname{calc}(h,w)$ 表示马走日在 $x$ 轴走 $h$ 格，$y$ 轴走 $w$ 格的方案数。

后日谈 # Link to 后日谈

话说这个军训要训 $10$ 天嘞，浪费我 $10$ 天的时间啊，少考好多场模拟赛的喔。