Matrix72's Blog

最寻常或小意外,都欣喜去相爱


  • About

  • Tags

  • Categories

  • Archives

  • Search

从偏序问题到CDQ分治

Posted on 2020-07-27 | | Visitors:
| 文章总字数: 717
偏序关系 设R是集合A上的一个关系,如果R是自反的、反对称的和可传递的,则称R是集合A的偏序关系,并记作 \(\preceq\) ,序偶 \(<A, \preceq >\) 称作偏序集 简单地说,偏序关系就是集合内只有部分元素之间在这个关系下可以比较,全序关系就是集合内任何一对元素在 ...
Read more »

数据结构专题训练赛03解题报告

Posted on 2020-06-05 | In ACM | | Visitors:
| 文章总字数: 4k

并查集

目标

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

构造

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

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

路径压缩

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

Read more »

LOJ1248 Dice(III)

Posted on 2020-06-05 | In ACM | | Visitors:
| 文章总字数: 589

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} \]

Read more »

CF484D-Kindergarten

Posted on 2020-05-20 | In ACM | | Visitors:
| 文章总字数: 1.2k

描述

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

Read more »

qt-player

Posted on 2020-05-17 | In dev | | Visitors:
| 文章总字数: 1.1k
your browser does not support the video tag

播放器功能介绍

自适应窗口

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

使用数据库管理数据

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

音乐播放控制

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

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

搜索

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

添加歌单

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

加载歌单详细信息

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

Read more »

Trie树与AC自动机专题学习笔记

Posted on 2020-03-20 | In ACM | | Visitors:
| 文章总字数: 4.8k

前置知识

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

AC自动机的定义与实现

定义

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

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

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

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

目标

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

Read more »

字符串专题训练赛04解题报告

Posted on 2020-03-19 | In ACM | | Visitors:
| 文章总字数: 4.5k

BZOJ3916-Friends

描述

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

题解

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

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

Read more »

字符串专题训练赛03解题报告

Posted on 2020-03-15 | In ACM | | Visitors:
| 文章总字数: 2.8k

CF985F-Isomorphic Strings

描述

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

Read more »

KMP与哈希专题笔记与题解

Posted on 2020-03-09 | In ACM | | Visitors:
| 文章总字数: 11k

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\)函数。

Read more »

Warma的硬币-题解

Posted on 2020-02-20 | In ACM | | Visitors:
| 文章总字数: 2.3k

题意

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

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

解法

20分

骗分大法直接输出-1

80分

Read more »
12
matrix72

matrix72

matrix72的万事屋

15 posts
2 categories
26 tags
RSS
Friends
  • Yuhi
  • TurboHsu
  • Xjzsq
  • Duinomaker
  • LeukPoint
  • Brethland
  • Stardline
  • 0xfaner
© 2021 matrix72 | 全站共计 45k字
苏ICP备17070415号-2
0%