[25MAY] 做题记录

· · 个人记录

2025-5-11noip&&noi模拟测验（远八的班级$小篱笆（提答题）

将铺满的方案数转化为完美匹配的方案数。

此时和 2025-4-29noip模拟测验 见证者 类似，不过是三连通版本。

答案为构造的矩阵 G 的积和式。

用类似的证明得到，G 的积和式等于 G 的行列式。

使用主元法求行列式即可得到答案。

2025-5-11noip&&noi模拟测验（远八的班级$房间安排

对于一个非空的未完成的序列，考虑下一个加进来的元素要满足的条件是与之前的点连的边数要是最多的之一，且在此基础上与之后还未加进序列的点连的边数要是最少的之一。

发现对于满足以上条件的所有点，他们之间的顺序可以任意钦定。

枚举序列中的第一个人，每次在满足条件的人中随便选取一个，得到最终序列。

对得到的序列 \text{DP}，将结果乘以选取序列时的方案数累加进答案。

转移是 $\text{trivial}$ 的。 # P4770 [NOI2018] 你的名字 计算一个字符串（这里指 $T$）中本质不同的子串个数是一个标准问题，可以直接利用**后缀数组**和 **Height 数组**的性质来解决。具体来说，本质不同子串的总数等于 $T$ 的长度加上所有后缀的长度之和减去 Height 数组中所有元素的和。 问题的难点在于如何高效地识别并去除 $T$ 中那些同时是 $S(l,r)$ 子串的本质不同子串。我们采取以下策略： 对于 $T$ 的每一个后缀，我们希望找到它的最长前缀 $L$，使得这个长度为 $L$ 的前缀是 $S(l,r)$ 的子串。 为了实现这一点，我们将字符串 $S$ 和 $T$ 连接起来构建一个大的**后缀数组**。为了方便后续计算，我们还需要记录每个位置在其原始字符串中的前驱和后继。 一个重要的观察是：如果 $T$ 中位置 $a$ 的后缀的最长匹配前缀长度为 $L$，那么位置 $a+1$ 的后缀的最长匹配前缀长度至少为 $L-1$。这个性质与 Height 数组的构建原理相似：如果同时去掉两个后缀的第一个字符，它们的最长公共前缀长度至少会减少 1。利用这个性质，我们可以使用**双指针**的方法来线性扫描 $T$ 的所有后缀，从而高效地计算出每个后缀对应的最长匹配前缀长度 $L$。 当我们考虑 $T$ 中位置 $a$ 的一个长度为 $L$ 的前缀是否是 $S(l,r)$ 的子串时，实际上是在询问是否存在一个在 $S$ 的 $[l, r-L+1]$ 区间内的起始位置 $b$，使得 $T$ 中位置 $a$ 的后缀与 $S$ 中位置 $b$ 的后缀的**最长公共前缀**长度大于或等于 $L$（即 $LCP(a, b$\ge L$）。 满足 $LCP(a, b$\ge L$ 条件的所有后缀在后缀数组上会形成一个连续的区间 $[ll, rr]$。这个区间可以通过**二分查找**结合 **Height 数组**和 **ST 表**在 $O(\log n)$ 的时间内求出。 接着，问题转化为：在后缀数组上的区间 $[ll, rr]$ 中，是否存在一个后缀的起始位置落在 $S$ 的 $[l, r-L+1]$ 区间内。这是一个典型的范围查询问题，可以使用**主席树**来解决，单次查询的时间复杂度为 $O(\log n)$。 在计算过程中，可能会出现重复统计的情况。例如，如果 $T$ 中某个子串是 $S(l,r)$ 的子串，并且它在后缀数组上与另一个位置的后缀有重叠，我们需要减去它们的最长公共前缀长度以避免重复计数。即使这两个位置不连续，我们仍然需要使用 ST 表来查询它们的 LCP 值。 # CF1252D Find String in a Grid 由于有多个查询字符串（模式），AC自动机是高效字符串匹配的合适选择。 通过构建包含所有查询字符串的AC自动机，离线处理所有查询。 我们需要考虑“L 形”字符串。L 形字符串由两条段组成：一条水平段和一条垂直段，它们在一个“拐点”或“角”处相遇。 对于网格中的每个可能的拐点 $(i, j)$，我们希望计算所有以 $(i, j)$ 为拐点的 L 形字符串的总贡献。 * 设 $f(x, y, a, b)$ 表示从 $(x, y)$ 到 $(a, b)$ 的 L 形路径上所有子路径对应的 L 形字符串的贡献之和。这个值是通过将这些 L 形字符串与AC自动机自动机进行匹配来获得的。 为了精确计算以**特定**拐点 $(i, j)$ 为中心的 L 形字符串的贡献，我们可以使用容斥原理。 考虑从 $(i, 1)$ 开始到 $(n, j)$ 结束的 L 形字符串的总贡献，即 $f(i, 1, n, j)$。 然而，这个和包含了一些拐点**不是** $(i, j)$ 的字符串的贡献。具体来说，它包括： 从 $(i, 1)$ 到 $(i, j-1)$ 的水平字符串（实际上是拐点在水平段上，且在 $(i, j)$ 之前的 L 形字符串）； 从 $(i+1, j)$ 到 $(n, j)$ 的垂直字符串（实际上是拐点在垂直段上，且在 $(i, j)$ 之后的 L 形字符串）。 因此，以 $(i, j)$ 为拐点的 L 形字符串的实际贡献由下式给出：$f(i, 1, n, j$- f(i, 1, i, j-1$- f(i+1, j, n, j)$。 不要在匹配时直接沿着 `fail` 指针跳跃，而是构建一个**fail树**。在匹配时，只增加当前节点的计数器。处理完所有文本字符串后，对失败树进行DFS遍历，计算其对应节点的子树和，从而有效地统计所有模式匹配。 遍历所有可能的拐点 $(i, j)$ 会产生 $O(nm)$ 的复杂度，其中 $N$ 是行数，$M$ 是列数。 对于每个 L 形字符串，与AC自动机自动机进行匹配的时间复杂度是 $O(\text{文本串长度})$。在本例中，L 形字符串的长度最多是 $O(N+M)$。因此，每次 `modify` 操作的复杂度是 $O(N+M)$。 构建AC自动机（插入所有查询字符串并计算 `fail` 指针）需要 $O(\sum |S|)$ 的时间，其中 $\sum |S|$ 是所有查询字符串的总长度。 最后对失败树进行 DFS 遍历以聚合贡献的时间复杂度是 $O(\text{AC 自动机中的总节点数})$，这也由 $O(\sum |S|)$ 限制。 综合这些，总时间复杂度为 $O(NM(N+M$+ \sum |S|)$。 # P6727 [COCI 2015/2016 #5] OOP 令 $T=A∗B$，其中 $∗$ 为通配符。 我们就是要找到有多少 $S_i$ 的前缀为 $A$，后缀为 $B$，长度 $\geq |T|-1$。 需要前后缀都出现，于是对于正反串建立 $\text{Trie}$，前后缀要求就转化为子树 $\text{dfs}$ 序范围，然后又要求长度，于是就是三维偏序了。时间复杂度 $O(n\log^2n)$。 树套树空间复杂度过高，改用 $\text{KDTree}$ 即可 $O(n\sqrt{n})$ 通过。 # QOJ7773 重排 考虑贪心，最开始是若干个长度为 $1$ 的字符串。 每次将每个最小的字符串后连接均分平均个数的最大的字符串。 发现这么做一定满足条件且是最优情况。 方案结构类似于 $[a...] [a...] [a...]$，其中每一块字典序大于前一块，显然满足条件。 字典序也必定最大，调整法可证。 # QOJ6877 Popcount Words 本题要求我们处理一个关于字符串 S=w(l,r)的多模式串匹配问题。具体来说，我们需要在字符串 S 中查找给定的多个模式串出现的次数。点击这里可以查看原题。核心分析解决此问题需要分几个关键步骤，我们将从理解 w()函数的特性开始，逐步构建解决方案。1. 理解 w()函数的倍增结构首先，我们深入研究 w($函数的性质。直观来看，它具有一种非常重要的倍增结构，这为我们后续的字符串拆分奠定了基础。 既然 $w()$ 函数具有倍增结构，我们就可以利用二进制的特性，将任意区间 $w(l, r)$ 拆解成一系列 $W$ 或 $\overline{W}$ 字符串的拼接。这个过程与**树状数组**的分解思想非常相似。 具体拆解步骤如下 1. **从左端点 $l$ 开始“上升”：** * 我们从 $l$ 开始，每次尝试加入一个长度为 $2^{\operatorname{lowbit}(l)} 的字符串块 w(l, l + 2^{\operatorname{lowbit}(l)} - 1)$。 * 根据上述 $w(k2^n,(k+1)2^n - 1)$ 的性质，我们可以确定这个块是 $W_{\operatorname{lowbit}(l)}$ 还是 $\overline{W}_{\operatorname{lowbit}(l)}$。 * 然后更新 $l = l + 2^{\operatorname{lowbit}(l)}$。 * 这个过程持续进行，直到当前 $l$ 加上下一个 $\operatorname{lowbit}(l)$ 对应的长度会超出 $r$ 的范围为止。 2. **从右端点 $r$ 逆向“逼近”：** * 在第一阶段结束后，$l$ 已经移动到某个位置。现在我们从剩余区间 $[l, r]$ 的右侧开始考虑。 * 每次加入一个长度为 $2^{\operatorname{lowbit}(r-l)}$ 的字符串块 $w(l, l + 2^{\operatorname{lowbit}(r-l)} - 1)$。 * 同样，根据性质确定其类型。 * 然后更新 $l = l + 2^{\operatorname{lowbit}(r-l)}$。 * 这个过程持续进行，直到 $l$ 最终等于 $r$。 通过这两个阶段，字符串 $S = w(l, r)$ 被拆分成了 $O(\log r)$ 个 $W$ 或 $\overline{W}$ 类型的子字符串。需要注意的是，实际拆分的是 $w(l, r-1)$，因此在实际应用中可能需要对右端点进行微调。 现在，问题转化为在由 $O(\log r)$ 个 $W$ 或 $\overline{W}$ 块拼接而成的长字符串 $S$ 中，查找多个模式串的出现次数。这是一个典型的**多模式串匹配问题**，最适合的工具是**AC自动机**。 首先，我们将所有给定的模式串构建成一个 AC 自动机。我们的目标是计算 AC 自动机上每个节点被遍历了多少次，这直接对应了模式串的出现次数（通过统计每个模式串结尾节点及其失败指针链上的节点访问次数）。 由于 $S$ 是由多个 $W$ 或 $\overline{W}$ 块拼接而成，我们可以将这些块看作是按顺序在 AC 自动机上进行分段转移。这是一个典型的**离线查询**问题，并且 $W, \overline{W}$ 本身具有倍增结构，这强烈提示我们可以使用**倍增标记法**。 我们定义以下状态来辅助计算： * $f_{u,n,k}$：表示从 AC 自动机上的节点 $u$ 出发，沿着 $W_n$（当 $k=0$ 时）或 $\overline{W_n}$（当 $k=1$ 时）序列转移后到达的终点节点。这个可以通过倍增预处理得到。 * $h_{u,n,k}$：表示**仅考虑由 $S$ 拆分出来的 $W$ 或 $\overline{W}$ 序列**，从节点 $u$ 出发，经过一个 $W_n$ 或 $\overline{W_n}$ 序列后，路径上经过的模式串结束节点的总计数。 * $g_{u,n,k}$：表示从节点 $u$ 出发，经过 $W_n$（当 $k=0$ 时）或 $\overline{W_n}$（当 $k=1$ 时）序列的转移，这种情况在整个字符串 $S$ 中总共出现了多少次。这是我们最终需要计算的状态，它将用于下放标记。 我们可以写出 $g$ 的递推关系（从大到小，逆序下放）： $$g_{u,n,k} = h_{u,n,k} + g_{u,n+1,k} + \sum_{v \text{ 使得 } f_{v,n,1-k} = u} g_{v,n+1,1-k}$$ 这个递推公式的含义是： * $h_{u,n,k}$：直接由当前 $W_n$ 或 $\overline{W_n}$ 块产生的贡献。 * $g_{u,n+1,k}$：从 $W_{n+1}$ 或 $\overline{W_{n+1}}$ 拆分出来的部分，其中前半段是 $W_n$ 或 $\overline{W_n}$。 * $\sum_{v \text{ 使得 } f_{v,n,1-k} = u} g_{v,n+1,1-k}$：从 $W_{n+1}$ 或 $\overline{W_{n+1}}$ 拆分出来的另一部分，其后半段是 $W_n$ 或 $\overline{W_n}$，且其前半段的终点恰好是 $u$。 通过这种倍增和逆序下放标记的方法，我们可以在 $O((\sum |p|$\log r)$ 的时间复杂度内完成预处理和标记的下放。最终，整个问题的总时间复杂度将达到 $O((N + \sum |p|$\log r)$，其中 $N$ 是 AC 自动机节点数，$\sum |p|$ 是所有模式串的总长度。 # P4482 [BJWC2018] Border 的四种求法 我们发现我们实际上有很多相同的东西，我们本可以预处理出来但是还要跑，浪费了很多时间。 我们肯定要预处理一些东西，我们设一个阈值 $Z$，我们对于字符串 $S$ 中的 $S_{l...l+Z-1}$，将相同的都放在一起，对于每次询问，小于阈值 $Z$ 直接暴力。大于阈值 S 的情况，我们在之前维护的集合中二分找到区间里面的下标，直接枚举所有合法的哈希判断。 # UOJ889 【UNR #8】二维抄袭检测 为了简化后续的计算流程，我们对输入的矩阵进行了一个预处理操作：将矩阵的第 $i$ 行元素整体向右循环移动 $i-1$ 个位置。通过这种转换，每次在矩阵中进行匹配时，我们只需要沿着水平向右或斜向右下方向移动一步。 我们引入一个布尔状态变量 $f_{i,j}$，它表示在处理到第 $i$ 列时，是否能够成功匹配到第 $j$ 行。根据匹配规则（具体条件在此处省略），该状态可以从 $f_{i,j}$ 转移到 $f_{i+1,j}$（即向右一步）或 $f_{i+1,j+1}$（即向右下斜一步）。 值得注意的是，在状态转移过程中，第一维（列索引）总是递增的，而第二维（行索引）的长度被限制在 $\leq 10$。鉴于这种特性，我们可以考虑采用矩阵乘法来加速状态的转移过程。 一个关键的挑战在于，第 $k$ 个状态转移矩阵并非固定不变，它由矩阵的第 $y_i+k$ 列字符与字符串 $s$ 的第 $p_i+k$ 个字符共同决定。这意味着对于不同的查询，其对应的转移矩阵序列是不同的。 为了应对这一挑战，我们提出一种策略：首先确定当前能够匹配的最小行号（即最小的 $j$ 使得 $f_{i,j} = 1$）。接着，计算出在当前列从该行开始能够匹配的最远距离，并在此范围内执行一次暴力状态转移。通过这种方式，我们可以至少处理从 $y_i$ 到 $y_i+j$ 的匹配。 由于 $j \leq n$，上述暴力转移操作的重复次数最多为 $n$ 次。在整个匹配过程中，相关的转移矩阵仅取决于当前正在匹配的子字符串。因此，核心问题转化为了如何高效地计算子串匹配区间内矩阵的连乘积。 一种有效的方法是针对每一行构建独立的树形结构。在处理查询时，我们可以通过向量与矩阵的乘法来完成。这种方法的预处理阶段复杂度为 $O(n \cdot m \log m \cdot n^2)$，而每个查询的时间复杂度为 $O(qm \cdot n)$。 进一步探讨树形结构，对于满足二叉树性质的节点，如果节点 $x$ 和 $y$ 处于相同的深度，则它们的最近公共祖先为 $\max(x,y)+1$，其深度为 $\lceil \log(x$\rceil$（假设根节点深度为 0）。 对于任意区间 $[i,i+2^k)$（其中 $0 \leq i < 2^n$），它唯一对应着一个节点 $i+2^k$，这些节点拥有最深且相同的深度。 对于任意给定的区间 $[l,r]$，它的 LCA 节点可以通过计算区间 $[l,l]$ 和 $[r,r]$ 的 LCA 来确定。 基于上述性质，我们可以在 $O(1)$ 的时间复杂度内定位到根节点，即负责划分区间 $ [l,r] $ 的节点。 在寻找最长匹配距离方面，尽管哈希结合二分查找是一种简洁的方法，但其容易面临超时问题。更优化的方案是将字符串 $ s $ 与字符矩阵 $ t $ 拼接起来，并对拼接后的字符串逐个后缀进行处理。这样，问题就转化为了经典的求两个后缀的最长公共前缀 问题。 综合来看，该算法的整体时间复杂度为 $O((L+nm)\log(L+nm)+n^3m\log m+nr^2q)$。 # CF1062F Upgrading Cities 在DAG中，如果我们只关注一个点最多只能有一个节点无法到达的特定情况，那么可以使用拓扑排序。 首先，在拓扑排序的任何时刻，当前队列中的所有节点都是互不可达的。一个节点只有在其所有前驱节点都被处理并出队后，其后继节点才可能被考虑入队。因此，队列中的节点之间不可能存在直接或间接的路径。 我们现在考虑如何利用这一性质，在拓扑排序过程中识别出那个“几乎全可达”的节点（即能到达除自身外所有节点，或除自身和一个特定节点外所有节点的点）。我们设 rest 为当前尚未出队的节点总数。 队列中只有一个节点时： 如果当前拓扑排序队列中只剩下一个节点 X，那么 X 显然能够到达所有剩余的 rest 个节点。这是因为所有尚未出队的节点都必须是 X 的后继，否则它们不可能在 X 之前没有被处理。在这种情况下，X 是一个潜在的“几乎全可达”节点。 队列中至少有三个节点时： 如果当前队列中存在三个或更多的节点，那么根据拓扑排序的性质，这些节点之间是互不可达的。这意味着，无论我们选择队列中的哪一个节点作为“几乎全可达”的候选，它都至少无法到达队列中的另外两个节点。因此，在这种情况下，队列中的任何节点都不能满足“最多只有一个节点无法到达”的条件，它们不可能是我们寻找的目标。 队列中恰好有两个节点时： 这是最需要仔细分析的情况。假设队列中按照拓扑顺序依次是节点 A 和节点 B。我们希望判断 A 是否能够到达除 B 之外的所有 rest - 1 个节点。 为了让 A 满足这个条件，我们需要确保： A 能够到达所有它自身直接或间接的后继节点。 关键点： A 还需要能够到达所有 B 的后继节点，除非这个后继节点 Z 只能通过 B 才能到达（即 Z 的入度为 1，且 B 是它唯一的直接前驱）。 让我们深入思考 B 的后继节点 Z： 如果 Z 的入度大于 1，这意味着 Z 不仅仅只有 B 一个前驱。考虑到当前队列中只有 A 和 B，那么 Z 必然还有一条路径可以从 A$或者从 A 可达的某个节点）到达。在这种情况下，A 也能到达 Z。 如果 Z 的入度恰好为 1，并且 B 是它唯一的直接前驱，那么 A 就无法到达 Z。在这种情况下，A 就不能满足“几乎全可达”的条件（因为它无法到达 Z 和 B，总共两个节点）。 因此，当队列中只有 A 和 B 时，如果 A 能够到达除 B 之外的所有 rest - 1 个节点，那么 B 的所有后继节点 Z 都必须满足 Z 的入度大于 1（从而保证 A 也能到达 Z），或者 Z 根本就不存在。 # CF475E Strongly Connected City 2 和边双连通分量相关，按边双缩点。 每个点中有 ${cnt}^2$ 的贡献。 考虑外部的点，选择一个点作为割点将树划分成两半。 此时两部分子树大小尽可能相同时贡献最大。（基本不等式） 枚举每个点作为割点暴力统计答案即可。 # P9140 [THUPC 2023 初赛] 背包 首先，我们倾向于采用贪心算法。直觉上，对于大部分背包容量，选取“性价比”最高的物品（即单位体积价值最大的物品）会是最佳选择。 假设物品$k$是性价比最高的物品，其体积为$v_k$，价值为$c_k$。一个显而易见的观察是，用其他体积为$v_k$的物品替代物品$k$并不划算，因为$k$的性价比最高。然而，当总体积不是$v_k$的倍数时，最优解可能并非简单地全部选择物品$k$并留下剩余容量。我们需要量化这种“优劣”程度。 定义$f_i$为在体积模$v_k$等于$i$的情况下，当前解的总价值与全部选择物品$k$且总体积为$V$时的价值之差的最大值。换句话说，$f_i$表示最优解相对于“全部取$k$”方案的收益（或损失）。可以证明，在DP过程中考虑的体积$V$不会超过实际查询的背包容量$V'$。DP 状态转移方程：DP 转移方程如下：$ f_i = \max_{1 \leq j \leq n} { f_{(i - v_j)\pmod{v_k}} + c_j - \left\lfloor \frac{v_j}{v_k} \right\rfloor \times c_k }

这里，原公式中的\left\lfloor \frac{i + v_j}{v_k} \right\rfloor \times c_k实际上是考虑了从i-v_j状态转移到i状态时，由于增加了v_j体积，导致总的v_k物品数量发生了变化，从而需要减去相应的k物品价值。更准确的表示是f_i = \max_{1 \leq j \leq n} { f_{(i - v_j + v_k\pmod{v_k}} + c_j - \left\lfloor \frac{v_j}{v_k} \right\rfloor \times c_k }以确保i-v_j索引的非负性。

由于DP存在“后效性”（即计算f_i可能依赖于f_j而j又依赖于i），我们可以将其转化为图论问题：将每个模v_k的余数i视为一个节点，边权为c_j - \left\lfloor \frac{v_j}{v_k} \right\rfloor \times c_k，然后运行最长路算法来求解。

最终查询的结果是\left\lfloor \frac{V}{v_k} \right\rfloor \times c_k + f_{V \pmod{v_k}}。这表示在全部取k的基础上，加上模v_k余数对应的额外收益。

我们可以将DP过程视为在图上寻找一条最长路径。如果一条路径两次经过同一个节点（即存在环），则意味着可以通过重复选择某些物品来增加价值。然而，如果存在一个正环，那么通过将环中的物品替换为性价比最高的物品k，通常可以获得更优的解。因此，最长路不会两次经过同一个节点，这意味着DP中的V不会超过所有物品体积之和\sum v_i。

在本问题中，\sum v_i \leq 10^{11}，而实际询问的V'可能更大，因此此性质成立。