题目链接 题解 最近学后缀数组学得有点晕,还是要多练啊。 题目就一句话:求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。 根据容斥原理,只要分别求出两个子串合并后的答案和两个子串单独的答案,最后的答案就是它们…
分类:数据结构
[CF427D]Match & Catch(后缀数组)
题目链接 题解 题目大意:求最小不重复相同子串。 考虑把两个字符串合并起来,求出sa,rk和Height数组。 我们可以从小到大枚举子串长度k,然后再枚举后缀。 具体来说,我们是根据子串字典序从小到大枚举后缀的 如果He…
[GZ/GXOI2019]与或和(单调栈)
题目链接 题解 看到这个首发平台就觉得是rainbowcat出的题,一看题面——都有Freda了,就确定是rainbowcat出的了。 这一题第一次写我写挂了orz 由于与运算和或运算在每一位上都是独立的,我们可以考虑对…
[CF817F] MEX Queries (线段树+离散化)
题目链接 题解 一道线段树模板题,离散化需要注意下,居然交了10次,丢人…… 细节还是很多的,最近都在写平衡树,一开始把线段树写成和权值树那样的分治方法了orz 代码 [crayon-600a3c5c4c74898703…
[ZJOI2007]报表统计
题目链接 题解 又是一道题一晚上系列(数据结构一生之敌) 调了很久的原因其实是写错了一个变量,其实还是很简单的 这里用的平衡树是Treap 你可以把原始数列看成n个链表,首尾相连的那种,但是我们要分段存 用vector就…
[ZJOI2006]书架
题目链接 题解 这道题一开始用的是Treap写的,死活调不出来,题解又全是指针的 然后就用splay来写,发现思路自然了许多 引用自FlierKing 平衡树,需支持五个操作: 1. 将某元素置顶:将元素旋到根,然后将左…
[CQOI2014]排序机械臂
题目链接 题解 这道题坑了我好久,其实不难,就是有个地方与模板不一样导致错误(死背模板的后果) 考虑用splay维护区间翻转,每次的翻转左边界是确定的,而右边界则是第i小的数所在位置 输入存在a数组里,按高度排序,每次我…
[P4886]快递员
题目链接 题解 这个淀粉质点分治有点意思,与其他的点分治的题目不同的是,这题目并没有让你费劲心思怎么去用log的复杂度进行内层的统计,而是让你想到如何确定当前答案是否最优。 (下面不会讨论点分治的具体实现,此题不适合作为…
【考前冲刺Day4】关于我不开long long见祖宗这桩事
T1 增援前线 实锤乱搞题,考试的时候写了一个错误的dp,只拿了一半的分。 实际上这一题应该属于贪心吧 我们用f[i]表示i号点能站多少人。 显然,前l个点的f[i]=a[i]; 对于其他情况,f[i]应由i-l到i-1…