🔖 算法字符串回文串manacher

前言

Manacher 算法可在线性时间内求出一个字符串中所有以任意位置或相邻两个位置为中心的最长回文串。

算法原理

记给定的字符串为 $S$，其长度为 $N$。为方便描述，在 $S$ 中的任一对相邻字符间插入一个特殊字符 $，目的是保证新串中所有的回文子串长度都为奇数（只是为了方便讨论算法，实际实现时并不需要此操作）。设以

🔖 acmbfs图论状态压缩解题报告

题意简述

在一个 $N\times M$ 的矩形方格地图中，有一条长度为 $L$ 的贪吃蛇。地图的 $(1,1)$ 位置是一个出口，如果贪吃蛇能移动到出口，输出最短步数（头到达出口的步数）；否则输出 $-1$。

贪吃蛇的移动规则如下：

  • 只能朝边相邻的格子移动
  • 不能朝障碍物移动（身体及四周墙壁都视作障碍物）

🔖 acm数据结构树链剖分线段树解题报告

题意简述

一棵 $N$ 个节点的树，节点编号 $1 \sim N$，且根节点编号始终为 $1$。初始时，节点 $i$ 的颜色为 $c_i$。执行 $M$ 次操作，每次操作为下述操作之一：

  • 0 u c: 将以 $u$ 为根节点的子树中所有的节点颜色染成 $c$
  • 1 u: 输出以 $u$ 为根节点的子树中颜色种数

数据范围： $1\leqslant T\leqslant 100$，$1\leqslant N, M\leqslant 10^5$, $1\leqslant c_i\leqslant N$。

🔖 acm大数乘法fft快速傅里叶变换

这是一篇旧文，当时采用 tex 编写的，仅将其编译成的 PDF 挂在此处。

小记

说起来，实在要感谢 lyl 学长（可能他并不想我写上他的名字，以下以他常用的名字 SparklingWind 指代）。大一的时候看了 SparklingWind 的《高中生学 FFT 算法》，当时自己实在太弱（虽然现在还是弱。。）以至于看得云里雾里。后来 SparklingWind 教我用 LaTeX，实在是让我受益匪浅。LaTeX 是一款精致的排版系统，可以漂亮、准确的表达出你心中所想。于是，我决定要基于自己的理解用 LaTeX 写一份 FFT 的学习笔记云云的东西，我把它命令为 SomethingAboutFFT

🔖 acm数据结构线段树解题报告

题意简述

$N$ 个点的序列，编号 $0 \sim N-1$。初始时，点 $i$ 的权值为 $a_i$。进行 $M$ 次如下操作：

  • 0 x y t: 令 $a_i=\min\, \lbrace a_i, t \rbrace$，其中：$x\leqslant i\leqslant y$。记作 $op_0$
  • 1 x y: 输出 $\max\, \lbrace a_i \rbrace$，其中：$x\leqslant i\leqslant y$。记作 $op_1$
  • 2 x y: 输出 $\displaystyle \sum\limits_{x\leqslant i\leqslant y} a_i$。记作 $op_2$

数据范围： $\displaystyle 1\leqslant T\leqslant 100, \quad 1 \leqslant \sum N, \; \sum M \leqslant 10^6$。

© 2017-2025 光和尘有花满渚、有酒盈瓯