日记

纯粹是被吓的。

Counting Binary Strings# Link to

露头就秒。

我们看到一个“好的子串”有且仅有一个 1，于是我们想着把这个序列分成 $114514$ 段形如 00...001 的段，设 $dp_i$ 表示已经有了 $i$ 个好的子串。但我们发现，如果对于一个 1，想要算他对于子串个数的贡献，我们不但要知道它后面有多少个 0，我们还要知道它前面有多少个 0。我们又看到 $n,k \le 2500$，直接 $dp_{i,j}$ 表示已经有了 $i$ 个好的子串，这个 1 前面有 $j$ 个 0。转移很简单：

写代码的时候不用像式子里那么麻烦，只要判 (k + 1) * (j + 1) <= i 就行。

Array Collapse# Link to

数组崩坏还在发力。

设 $dp1_i$ 表示 $i$ 被不取走有多少种，$dp2_i$ 表示 $i$ 被取走。设 $j$ 为第一个使得 $a_j \lt a_i$ 的。转移如下：

$j$ 用单调栈维护，$\sum\limits_{k = j - 1}^{i - 1}dp2_k$ 用前缀和优化即可。最终答案为 $dp1_n + dp2_n$。

Transitive Graph# Link to

这题能有 2100?

我们看到：

If there exists a triple of vertices $a$, $b$, $c$ of $H$, such that there is an edge from $a$ to $b$ and an edge from $b$ to $c$, but there is no edge from $a$ to $c$, add an edge from $a$ to $c$.

这就很缩点。我们又看到：

Among all the longest simple paths in H, find the one with the smallest value.

细说这个 longest，我们结合上面的，如果在一个强联通分量里，结合第一个条件，我们不用考虑从哪里进从哪里出，于是为了最长，我们肯定要把整个强联通分量走完再出来。那么这就是一个 tarjan 和拓扑排序板子题。

后日谈 # Link to 后日谈

下午胸口疼的厉害，我才 14 岁我不想死，于是晚上出来看医生。得出结论：纯粹被吓的。我还能再熬。

但是却因此丢失了晚上回家 van you see 的机会，大悲~~~