跳转至

2024

  • 分类于 String
  • 需要 4 分钟阅读时间

后缀数组

后缀数组是处理字符串的利器。

定义

对于长度为 \(n\) 的字符串 \(s = s_1 s_2 \cdots s_n\)，定义 \(s[i,j] = s_i s_{i+1} \cdots s_j\)，即 \(s\) 的第 \(i\) 个到第 \(j\) 个字符形成的子串。

定义 sa 为 \(s\) 的后缀数组，sa[i] 表示第 \(i\) 小的后缀的编号。

定义 rk[sa[i]]=i，即 rk[i] 表示后缀 \(i\) 的 rank。

  • 分类于 Misc
  • 需要 1 分钟阅读时间

杂项

这里是一些杂七杂八的东西。

  • 分类于 Misc
  • 需要 2 分钟阅读时间

VSCode 配置

前言

作为 VSCode 资深用户，从第一次下载到如今，踩了一个又一个坑，在这里记录一下我的配置方法以及遇到的一些问题。

  • 分类于 GMOJ
  • 需要 2 分钟阅读时间

8113. 【2022.10.7联考noip模拟】Talulah

题意

给定长度为 \(n\) 的排列 \(p\)，定义集合 \(S_i = \{j \mid j \ge i \land \max_{k \in [i,j]} p_k = p_j\}\)。

给定 \(q\) 次询问 \(l,r\)，求 \(\sum_{x,y \in [l,r]} |S_x \cap S_y|\)。

\(n,q \le 2.5 \times 10^5\)

  • 分类于 Graph
  • 需要 1 分钟阅读时间

图论

这里是图论相关的算法笔记。

  • 分类于 Math
  • 需要 5 分钟阅读时间

行列式

定义

定义 \(n\) 阶方阵 \(A\) 的行列式为：

\[ \det A=\begin{vmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \\ \end{vmatrix} =\sum_{p_1,p_2,\cdots,p_n} (-1)^{\tau(p_1,p_2,\cdots,p_n)} \prod_{i=1}^n a_{i,p_i} \]

其中 \(\{p_1,p_2,\cdots,p_n\}\) 是一个 \(n\) 的排列，\(\tau(p_1,p_2,\cdots,p_n)\) 表示 \(\{p_1,p_2,\cdots,p_n\}\) 的逆序数。