偏序关系 设R是集合A上的一个关系，如果R是自反的、反对称的和可传递的，则称R是集合A的偏序关系，并记作 \(\preceq\) ，序偶 \(<A, \preceq >\) 称作偏序集 简单地说，偏序关系就是集合内只有部分元素之间在这个关系下可以比较，全序关系就是集合内任何一对元素在 ...

并查集

目标

• 将两个集合合并
• 查询两个元素是否在同一集合内

构造

每个集合用一棵树表示，用根节点的编号表示整个集合的编号，开一个数组 \(p[x]\) ，表示编号为 \(x\) 的元素的父节点编号

• 若 \(p[x] = = x, x\) 为树根。
• 求 \(x\) 的集合编号：while(p[x] != x) x = p[x]
• 合并两个元素所在集合，设 \(px,py\) 表示 \(x,y\) 的集合编号，p[px]=py

路径压缩

这样的确可以达成目的，但是显然效率实在太低。为什么呢？因为我们使用了太多没用的信息，我的祖先是谁与我父亲是谁没什么关系，这样一层一层找太浪费时间，不如我直接当祖先的儿子，问一次就可以出结果了。甚至祖先是谁都无所谓，只要这个人可以代表我们家族就能得到想要的效果。 把在路径上的每个节点都直接连接到根上 ，这就是路径压缩。——OI-Wiki

LOJ1248 Dice(III)

描述

给定一个 n 面的骰子，每个面出现的概率相同，现在要所有的面都至少出现一次，求投掷次数的期望。

题解

设 \(f[i]\) 表示投出 \(i\) 个面需要投掷的期望次数，投掷出现 \(i\) 个面后，当前的一次投掷，可能是投出的面原先投出过，这种情况有 \(\frac{i}{n}\) 的概率，也可能是当前投出的面未出现过，这种情况有 \(\frac{n - i}{n}\) 的概率。

对于已经投掷出 \(i\) 个面后的状态，此时的投掷，实际上是一个伯努利实验，事件即为是否投出新的一面。因此，根据几何分布的公式 \(E[X]=\frac 1 p\) ，易得投出新的一面的期望是 \(\frac n {n-i}\) ，因而可以得出 \[ f[i] = f[i - 1] + \frac n {n-i} \]

描述

有一组数，你要把他分成若干连续段。每一段的值，定义为这一段 数中最大值与最小值的差。 求一种分法，使得这若干段的值的和最大。 \(n < 1e6, a_i < 1e9\)

播放器功能介绍

自适应窗口

在播放器的边缘，可以通过鼠标拉伸整个播放器窗口，大小随心

使用数据库管理数据

利用数据库的主键功能，实现了开发文档中所说的选座要求——歌单编号不得重复。

音乐播放控制

实现了开发文档中所说的选座要求——可以形成歌曲的上一首，下一首播放以及循环播放功能。

具备常规播放器具有的前进一首，后退一首，暂停，拖动进度条，调整音量的功能，并支持循环、单曲循环、随机播放的三种播放模式。

搜索

在搜索框输入内容后，会在下方显示搜索结果，包含两个信息，1）一共搜索到相关歌曲的数量，2）相关歌曲。点击歌曲名称的一行可以直接播放歌曲

添加歌单

在”我的歌单“右侧有一个加号的按钮，点击后会弹出添加歌单的对话框，其中歌单是必填项，简介为选填项，若无简介，歌单详情页也不会显示简介相关标签，同时会给歌单添加一张默认图片，添加完后自动加载新建的歌单。

加载歌单详细信息

点击歌单列表中的歌单名称，右侧详情页即会加载该歌单的相关信息。

前置知识

• KMP算法（之前写的一篇KMP解析博客：传送门）
• Trie树（推荐OI-Wiki上的文章：传送门）

AC自动机的定义与实现

定义

AC自动机是基于Trie树的数据结构利用KMP的思想进行多模式匹配的算法。

具体而言，建立一个AC自动机只需要完成两件事

1. 将所有模式串建立Trie树。
2. 构建失配指针。

粗略地理解，就是把本来要和原串匹配的一堆模式串合成一棵树，让原串和一棵树去匹配，来获得平均线性的复杂度。

目标

求出每个模式串在原串出现的次数。

BZOJ3916-Friends

描述

对于字符串\(S\)，先复制一遍接在\(S\)尾部，然后再在任意位置插入一个字符，给定构造好的字符串\(T\)，求原字符串\(S\)。

题解

首先设\(T\)长度为\(n\)，如果\(n\)为偶数，那么必然不存在原串，因为一个字符串长度乘二加一必然是奇数，然后，可以知道原串的长度一定是\(\frac n 2\)。

根据这两个结论，我们可以直接枚举每个位置是否是插入的字符，通过哈希去验证去除该字符后剩下的是否是两个完全相同的串，枚举复杂度为\(O(n)\)，验证复杂度为\(O(1)\)，总体复杂度为\(O(n)\)，符合题目要求。

CF985F-Isomorphic Strings

描述

给定一个字符串\(s\)，执行\(m\)次询问，每次询问判断\(s\)的两个子串是否同构。对于两个字符串同构的定义可以概括为：如果\(s\)中的字符可以被替换得到\(t\)，那么这两个字符串是同构的。所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。

KMP与前缀函数

前缀函数的定义

给定一个长度为\(n\)的字符串\(s\)（下标从\(1\)开始），约定\(s[l,r]\)表示从\(s[l]\)开始到\(s[r]\)结束的字符串，\(s\)的 前缀函数 被定义为一个长度为\(n\)的数组\(\pi\)。其中\(\pi[i]\)为既是字符串\(s[1,i]\)的前缀同时也是该字符串的后缀的 最长 真前缀字符串（真前缀字符串指不为这个字符串本身的前缀字符串）长度。

换言之，\(\pi[i]\)只关心字符串\(s[1,i]\)，且若\(\pi[i]=j\)，则有字符串\(s[1,j]=s[i-j+1,i]\)。抽象的数学定义即为：\(π(i)=max\{j|s[1,j]=s[i−j+1,i], j≤i\}\)

求解与优化

根据定义可以得出两个结论来帮助我们快速求解\(\pi\)函数。

题意

warma付钱的决策是多重背包模型，收银员找零是完全背包模型，先预处理，然后从w开始枚举S，求min即可

多重背包不开二进制优化应该会挂，开了优化可能没有推出结论也可以水过去

解法

20分

骗分大法直接输出-1

80分