字符串，太深刻了。 Lyndon 理论，太神奇了。 本文详细介绍了 Lyndon 理论的相关内容，并且几乎所有定理和推论都给出了相关证明，同时部分算法给了几道配套例题。 希望读者阅读后能对 Lyndon 理论有深刻的理解。 全篇太长了，故分开来发。 0. 初步的定义 & 约定 长度：记为 $|s|$。 字符：用 $s[i]$ 表示串 $s$…

圆的扫描线算法 引入 平面上有 $n$ 个圆，圆之间没有公共点，即圆之间要么包含，要么相离。此时圆要么都是一个包含一个，要么都是同级并列的，不难发现这很像树的结构，那我们不妨将圆的包含关系看做树的边然后建树，这样就会形成一个森林。我们可以给森林一个超级源点，将森林中所有树的根连起来，此时森林就变成了一棵树，相当于此时原点处有一个半径无限大的圆，所有…

简介 珂朵莉树，又名老司机树（Old Driver Tree）。珂朵莉树起源于 Codeforces 的一场比赛 CF896C。 这种想法的本质是基于数据随机的「颜色段均摊」，而不是一种数据结构。 ——OI Wiki 珂朵莉树本质上并不能算一种数据结构，仅仅只能算一种思想。并且其适用范围较为有限，只能适用于以下情况：维护一个序列，数据随机，只有区间…

定义 顾名思义，“分层图最短路”就是在分层图上跑最短路。 模型 在图上，有k次决策，问起点与终点之间的最短路径。 k个决策不会影响图的结构，只会影响当前的代价或状态。 做法 一般有两种做法： 第一个方法：建 $k+1$ 的分层图。 第二个方法：多开一维的数组记录决策信息。 方法一 对于同一层的图，每一层都按原图建边。 对于相邻两层的图，若原图中从 …

定义 中国剩余定理（Chinese Remainder Theorem，CRT），可用于求解如下形式的一元线性同余方程组（其中 $a_1,a_2,...,a_3$ 两两互质 ）： $\begin{cases} x \equiv a_1\ ({\rm mod}\ n_1) \ x\equiv a_2\ ({\rm mod}\ n_2) \ ... \…

<!-- wp:heading {"level":3} --> <h3><a href="https://www.luogu.com.cn/problem/P2916" target="_blank" rel="noreferrer noopener…

通信原理学习笔记（二）——通信系统模型。初步了解模拟通信系统模型和数字通信系统模型中各部分的功能，以及数字通信的特点

通信原理学习笔记（一）——消息、信息与信号。初步理解通信的基本概念，了解消息、信息、信号的概念及联系