冒泡ioa
冒泡ioa

数据结构
文章归档

[HAOI2016]找相同字符(后缀数组)

题目链接 题解 最近学后缀数组学得有点晕,还是要多练啊。 题目就一句话:求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。 根据容斥原理,只要分别求出两个子串合并后的答案和两个子串单独的答案,最后的答案就是它们相减。 问题的关键就是如何在…

   251   2019-05-05   去围观

[CF427D]Match & Catch(后缀数组)

题目链接 题解 题目大意:求最小不重复相同子串。 考虑把两个字符串合并起来,求出sa,rk和Height数组。 我们可以从小到大枚举子串长度k,然后再枚举后缀。 具体来说,我们是根据子串字典序从小到大枚举后缀的 如果Height[i]不小于k(即第i-1个子串和第i个子串的…

   254   2019-05-03   去围观

[GZ/GXOI2019]与或和(单调栈)

题目链接 题解 看到这个首发平台就觉得是rainbowcat出的题,一看题面——都有Freda了,就确定是rainbowcat出的了。 这一题第一次写我写挂了orz 由于与运算和或运算在每一位上都是独立的,我们可以考虑对每一位进行计算。 我们先考虑与运算(其实两个运算是一样的)…

   573   2019-04-16   去围观

[CF817F] MEX Queries (线段树+离散化)

题目链接 题解 一道线段树模板题,离散化需要注意下,居然交了10次,丢人…… 细节还是很多的,最近都在写平衡树,一开始把线段树写成和权值树那样的分治方法了orz 代码 [crayon-6094b8cabc2d2679642094/]

   211   2019-04-13   去围观

[ZJOI2007]报表统计

题目链接 题解 又是一道题一晚上系列(数据结构一生之敌) 调了很久的原因其实是写错了一个变量,其实还是很简单的 这里用的平衡树是Treap 你可以把原始数列看成n个链表,首尾相连的那种,但是我们要分段存 用vector就很舒服 然后对于第三个操作,其实只要每次进入平…

   200   2019-03-26   去围观

[ZJOI2006]书架

题目链接 题解 这道题一开始用的是Treap写的,死活调不出来,题解又全是指针的 然后就用splay来写,发现思路自然了许多 引用自FlierKing 平衡树,需支持五个操作: 1. 将某元素置顶:将元素旋到根,然后将左子树合并到该元素的后继 2. 将某元素置底:将元素…

   186   2019-03-25   去围观

[CQOI2014]排序机械臂

题目链接 题解 这道题坑了我好久,其实不难,就是有个地方与模板不一样导致错误(死背模板的后果) 考虑用splay维护区间翻转,每次的翻转左边界是确定的,而右边界则是第i小的数所在位置 输入存在a数组里,按高度排序,每次我们就取出a[i].id,它的位置作为右边界,每次输出…

   218   2019-03-25   去围观

[P4886]快递员

题目链接 题解 这个淀粉质点分治有点意思,与其他的点分治的题目不同的是,这题目并没有让你费劲心思怎么去用log的复杂度进行内层的统计,而是让你想到如何确定当前答案是否最优。 (下面不会讨论点分治的具体实现,此题不适合作为点分治入门题) 在此我们可以将情…

   244   2019-03-16   去围观

点分治学习笔记

导言 淀粉质点分治是一种统计方法,具体来说,是对树上的点的一些值来进行统计,标准的点分治统计复杂度为 $O(Nlog^2N)$ 是解决树上疑难杂症的不三之选(还有一个是树形dp) 算法思路&&具体问题 【洛谷P3806】点分治 给你一棵树,有m个询问,每个询问包…

   223   2019-03-01   去围观

【考前冲刺Day4】关于我不开long long见祖宗这桩事

T1 增援前线 实锤乱搞题,考试的时候写了一个错误的dp,只拿了一半的分。 实际上这一题应该属于贪心吧 我们用f[i]表示i号点能站多少人。 显然,前l个点的f[i]=a[i]; 对于其他情况,f[i]应由i-l到i-1这段区间内的点更新而来。 具体来说,就是“能跳则跳,满员为止” 我…

   332   2018-11-06   去围观
加载更多