数据结构专题训练赛03解题报告
并查集
目标
- 将两个集合合并
- 查询两个元素是否在同一集合内
构造
每个集合用一棵树表示,用根节点的编号表示整个集合的编号,开一个数组 \(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)
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} \]
CF484D-Kindergarten
描述
有一组数,你要把他分成若干连续段。每一段的值,定义为这一段 数中最大值与最小值的差。 求一种分法,使得这若干段的值的和最大。 \(n < 1e6, a_i < 1e9\)
qt-player
播放器功能介绍
自适应窗口
在播放器的边缘,可以通过鼠标拉伸整个播放器窗口,大小随心
使用数据库管理数据
利用数据库的主键功能,实现了开发文档中所说的选座要求——歌单编号不得重复。
音乐播放控制
实现了开发文档中所说的选座要求——可以形成歌曲的上一首,下一首播放以及循环播放功能。
具备常规播放器具有的前进一首,后退一首,暂停,拖动进度条,调整音量的功能,并支持循环、单曲循环、随机播放的三种播放模式。
搜索
在搜索框输入内容后,会在下方显示搜索结果,包含两个信息,1)一共搜索到相关歌曲的数量,2)相关歌曲。点击歌曲名称的一行可以直接播放歌曲
添加歌单
在”我的歌单“右侧有一个加号的按钮,点击后会弹出添加歌单的对话框,其中歌单是必填项,简介为选填项,若无简介,歌单详情页也不会显示简介相关标签,同时会给歌单添加一张默认图片,添加完后自动加载新建的歌单。
加载歌单详细信息
点击歌单列表中的歌单名称,右侧详情页即会加载该歌单的相关信息。
Trie树与AC自动机专题学习笔记
前置知识
AC自动机的定义与实现
定义
AC自动机是基于Trie树的数据结构利用KMP的思想进行多模式匹配的算法。
具体而言,建立一个AC自动机只需要完成两件事
- 将所有模式串建立Trie树。
- 构建失配指针。
粗略地理解,就是把本来要和原串匹配的一堆模式串合成一棵树,让原串和一棵树去匹配,来获得平均线性的复杂度。
目标
求出每个模式串在原串出现的次数。
字符串专题训练赛04解题报告
BZOJ3916-Friends
描述
对于字符串\(S\),先复制一遍接在\(S\)尾部,然后再在任意位置插入一个字符,给定构造好的字符串\(T\),求原字符串\(S\)。
题解
首先设\(T\)长度为\(n\),如果\(n\)为偶数,那么必然不存在原串,因为一个字符串长度乘二加一必然是奇数,然后,可以知道原串的长度一定是\(\frac n 2\)。
根据这两个结论,我们可以直接枚举每个位置是否是插入的字符,通过哈希去验证去除该字符后剩下的是否是两个完全相同的串,枚举复杂度为\(O(n)\),验证复杂度为\(O(1)\),总体复杂度为\(O(n)\),符合题目要求。
字符串专题训练赛03解题报告
CF985F-Isomorphic Strings
描述
给定一个字符串\(s\),执行\(m\)次询问,每次询问判断\(s\)的两个子串是否同构。对于两个字符串同构的定义可以概括为:如果\(s\)中的字符可以被替换得到\(t\),那么这两个字符串是同构的。所有出现的字符都必须用另一个字符替换,同时保留字符的顺序。两个字符不能映射到同一个字符上,但字符可以映射自己本身。
KMP与哈希专题笔记与题解
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的硬币-题解
题意
warma付钱的决策是多重背包模型,收银员找零是完全背包模型,先预处理,然后从w开始枚举S,求min即可
多重背包不开二进制优化应该会挂,开了优化可能没有推出结论也可以水过去
解法
20分
骗分大法直接输出-1