日记 - 伊埃斯的博客站

纯粹是被吓的。

Counting Binary Strings↗

露头就秒。

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

dp_{i,j} = \sum_{k = 0}^{\lfloor \frac{i}{j + 1} \rfloor - 1}dp_{i - (k + 1) \times (j + 1),k}

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

Array Collapse↗

数组崩坏还在发力。

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

\begin{cases} dp1_i = dp1_j + dp2_j \\ dp2_i = dp1_j + \sum\limits_{k = j - 1}^{i - 1}dp2_k \end{cases}

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

Transitive Graph↗

这题能有 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 和拓扑排序板子题。

后日谈

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

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

Thanks for reading!

日记

周四 3月 27 2025

537 字 · 3 分钟

life 日记