[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 去围观【考前冲刺Day4】关于我不开long long见祖宗这桩事
T1 增援前线 实锤乱搞题，考试的时候写了一个错误的dp，只拿了一半的分。 实际上这一题应该属于贪心吧 我们用f[i]表示i号点能站多少人。 显然，前l个点的f[i]=a[i]； 对于其他情况，f[i]应由i-l到i-1这段区间内的点更新而来。 具体来说，就是“能跳则跳，满员为止” 我…
332 2018-11-06 去围观