日记

连着 $4$ 天没更日记，这下可有的写了。

灾后重建↗

我们考虑对于 $t$ 扫描线。题目里给定 $t$ 是单调不降的，所以我们甚至不用离线。设我们现在扫描到的 $t$，当前在处理村庄 $u$，满足村庄 $u$ 在 $t$ 时刻通车。

我们发现 $n$ 十分的小啊，所以考虑 Floyd。我们处理 $u$ 的时候，拿 $u$ 松弛一下就行了。

Protect the school↗

其实就是一道 tarjan 强连通板子题。

Bit Counting Sequence↗

我们记录 $val$ 表示当前确定的值，$k$ 表示当前确定的位数。

当我们循环到 $a_i$ 时，设 $x = a_{i - 1} - a_i + 1$，我们发现 $x$ 就是它进的位数。于是我们就可以确定在 $i - 1$ 处 $val$ 的第 $[0,x)$ 位都是 $1$ 了。于是我们就依次可以确定 $val$，如果发现 $val$ 已经确定的在 $[0,x)$ 之间的位置不全是 $1$ 就说明不对，无解。

Help Yourself G↗

将线段按照左端点排序。设 $dp_{i}$ 表示前 $i$ 条线段所组成的集合的复杂度之和。

考虑如何转移。我们发现：第 $i$ 条线段可选可不选，于是就有一个 $2 \times dp_{i - 1}$。那么选它对于复杂度的影响呢？它会对所有的 $r_j < l_i$ 的 $j$ 组成的集合都会造成 $1$ 的贡献，设有 $x$ 个 $j$，那么就会造成 $2^x$ 的贡献。

所以我们有 dp 方程：$dp_i = 2 \times dp_{i - 1} + 2^x$，$x$ 可以用桶 + 前缀和预处理，时间复杂度 $O(n)$。

迎接仪式↗

这道题的 dp 状态设的也是十分神秘啊。

设 $dp_{i,j,k,p}$ 表示循环到了第 $i$ 位，改了 $j$ 个 $\texttt{j}$，$k$ 个 $\texttt{z}$，当前这位改过后是 $\texttt{j}$ 还是 $\texttt{z}$ 的最大子串数量。统计答案：$ans = \max_{i = 0}^{K}\max\{dp_{n,i,i,0},dp_{n,i,i,1}\}$。

考虑如何转移。

• 这一位本来是 $\texttt{j}$
  • 不改
    那么这一位也不可能和前面组成 $\texttt{jz}$ 子串，所以有 $dp_{i,j,k,0} \gets \max(dp_{i - 1,j,k,0},dp_{i - 1,j,k,1})$。
  • 改
    这一位就可以和前面一位组成 $\texttt{jz}$ 子串了，有 $dp_{i,j,k,1} \gets \max(dp_{i - 1,j - 1,k,0} + 1,dp_{i - 1,j - 1,k,1})$。
• 这一位本来是 $\texttt{z}$
  • 不改
    同理：$dp_{i,j,k,1} \gets \max(dp_{i - 1,j,k,0} + 1,dp_{i - 1,j,k,1})$。
  • 改
    同理：$dp_{i,j,k,0} \gets \max(dp_{i - 1,j,k - 1,0},dp_{i - 1,j,k - 1,1})$。

这题最神秘的地方就在于这个神秘的状态设定。

一个关于序列的游戏↗

区间 dp 好题。

设 $dp_{i,j}$ 表示区间 $[i,j]$ 能获得的最大价值。有显然的转移：$dp_{i,j} = \max_{k = i}^{j - 1}dp_{i,k} + dp_{k,j}$。但是对于那写最初并非在一起的区间呢？

我们考虑如何处理这些区间。设 $up_{i,j}$ 表示将 $[i,j]$ 变成一个单调递增的合法区间的最大价值，$dn_{i,j}$ 表示将 $[i,j]$ 变成一个单调递减的的区间的最大价值。那么我们有 $calc(l,mid,r)$，表示求 $[l,r]$，峰在 $mid$ 的最大价值：

1
int calc(int l,int mid,int r)
2
{
3
    int len = (a[mid] << 1) - a[l] - a[r] + 1;
4
    if (a[mid] < a[l] || a[mid] < a[r] || len > n)
5
        return -inf;
6
    return up[l][mid] + dn[mid][r] + v[len];
7
}

那么我们的转移又要加一个：$dp_{i,j} = \max_{k = i}^{j}calc(i,k,j)$。

如何维护 $up$ 和 $dn$ 呢？

• 维护 $up$
  我们发现只有在 $a_{i - 1} + 1 = a_{j + 1}$ 的时候，才可以进行转移。所以有：

1
if (a[i - 1] + 1 == a[j + 1])
2
    for (int l = 1; l < i; l++)
3
        for (int r = j + 1; r <= n; r++)
4
            up[l][r] = max(up[l][r],up[l][i - 1] + up[j + 1][r] + dp[i][j]);

• 维护 $dn$
  同理：

1
if (a[i - 1] - 1 == a[j + 1])
2
    for (int l = 1; l < i; l++)
3
        for (int r = j + 1; r <= n; r++)
4
            dn[l][r] = max(dn[l][r],dn[l][i - 1] + dn[j + 1][r] + dp[i][j]);

总时间复杂度 $O(n^3)$.

数列↗

唐成啥了。

设 $dp_{i,j,k,p}$ 表示正在处理二进制下的第 $i$ 位，有 $j$ 个数已经确定值了，总共有 $k$ 个 $1$，要往下进 $p$ 位的权值和。

考虑填表法转移。设要给 $x$ 个数赋 $i$，那么 $j$ 肯定是变成 $j + x$ 了，$k$ 变成 $k + [(x + p) \mod 2]$ 了，$p$ 变成 $p + \lfloor \frac{x + p}{2} \rfloor$ 了。

那么贡献呢？显然，加上 $x$ 个 $i$ 会在 $\binom{n - j}{x}$ 中情况里造成 $v_i^x$ 的贡献。所以有转移方程：$dp_{i + 1,j + x,k + [(x + p) \mod 2],p + \lfloor \frac{x + p}{2} \rfloor} \gets dp_{i,j,k,p} \times v_i^x \times \binom{n - j}{x}$。

最终的答案呢？我们已经处理完了 $m$ 位，所以正在处理的应当是 $m + 1$ 位。而我们填完了 $n$ 个数，要 $k + \text{popcount}(p) \le K$ 时就统计进答案，所以有 $ans = \sum_{k = 0}^{K}\sum_{p = 0}^{\lfloor \frac{n}{2} \rfloor}[k + \text{popcount}(p) \le K]dp_{m + 1,n,k,p}$。

金字塔↗

太唐了不写了。

Rectangles↗

我们钦定 $n \le m$（如果不是的话转置一下就是了）。然后枚举 $u,d$ 表示矩阵的上下边界，枚举 $i \in [1,m]$，如果有 $mp_{u,i} = mp_{d,i}$，我们就把 $(u,d,lst,i)$ 这个矩阵标记出来，并将 $lst$ 置为 $i$。

然后我们对于第 $k \in [1,m]$ 列进行区间 dp。设 $dp_{i,j}$ 表示能覆盖 $x \in [i,j],y = k$ 的所有点的矩形最小是多大。那么有转移：$dp_{i + 1,j} = \min(dp_{i + 1,j},dp_{i,j}),dp_{i,j - 1} = \min(dp_{i,j - 1},dp_{i,j})$。但是实现太优秀了调了一上午也没调出来

Happy·Lovely· Everyday！↗

考完这场模拟赛，这辈子都不会想玩 pjsk 了。

我们发现，题意可以变成这个样子：把 $a$ 分成几个字串，都给替换成它的异或和，得到的数组记为 $b$，求本质不同的 $b$ 的数量。我们发现，如果定义 $a'_i = \bigoplus_{j = 1}^{i}a_i$，$b'_i$ 同理，那么每个 $b'$ 都对应一个 $b$，而 $b'$ 又一定是 $a'$ 的字序列，那么就相当于求 $a'$ 的本质不同的子序列的数量就是了。

敬启，致那时的我↗

神秘数位矩阵 dp。

后日谈

今天给 Frosti 更新了一下。

早上那叫一个颓废，我也不知道为啥这么颓废，多半是因为没做出来 T1 的缘故。

希望明天早上不要这样。

Thanks for reading!

日记

周二 10月 14 2025

1560 字 · 7 分钟

life 日记

---

© 伊埃斯 | CC BY-NC-SA 4.0

分享

分享这篇博客

X (Twitter) Telegram Reddit Facebook Email

关闭

关闭