Dada 的待完成题目

· · 个人记录

前言

由于每天晚上 dadaaa 都会因为补不完题而焦头烂额，为了防止过了一段时间之后胡出来的题不记得做法了，因此写一个口胡记录，等有空再实现。

其实就是写不完的题咕咕存放的地方

洛谷链接

QOJ9406

假设我们选出来的三个子串按字典序从小到大排序为 S1,S2,S3。注意到，我们一定不能够让 S3 非常严格的大于 S1,S2，此时无论 S1,S2 怎么拼也拼不出来 \gt S3 的。

此时 S1,S2 一定有一个是 S3 的前缀，且此时剩下那个字典序大于 S3。此时我们可以枚举 S3 的一个前缀，设其为 S1，那么我们的 S2 取值范围是一个区间，二分即可。

怎么比较字典序大小？把所有串拼起来跑 SA 就能实现。

此时注意到，如果我们选择出 S1 时 S2 合法，选择出 S2 时 S1 合法，那么这会算重。会算重的次数是所有 S1>S3-S2 且 S2>S3-S1。这是一个二维数点状物，问题化成 a_i \gt b_j \cap a_j > b_i，考虑扫描线和树状数组维护。（怎么做待更新）

然后就做完了，复杂度 O((n+|S|)\log (n+|S|))。

n进制加法

主席树维护加法，点分树数，随机二分即可。

二分到底层控精度。

古籍

转换为 S=S_i \cap S_j, S_i \cap S_j \cap D = \emptyset 的数量。注意到后半部分可以用 1 数量刻画，跑 FWT 即可。复杂度为 O(n^2 2^n)。

Haitang and Diameters，16481

点减边容斥，问题变成了求对于每一个点存在两个深度最大值相同的方案数量，可以直接换根解决。

注意到我们是类似于可以前缀和的实现，因此每次合并复杂度为 O(n)，总复杂度为 O(n^2)。

awaw，NFLS18042

按照 w 分块，每次跑单调队列等数据结构找出总共 O(n) 个方块，每个方块用一点办法找出上下左右的连通方块，跑并查集即可。

复杂度排序后 O(n)。

联邦之终，NFLS11255

做过的题，需要把线段树改为平衡树就行了。

第二题，NFLS18061

注意到我们对对于”走一条边最大值的边“这个事情可以颜色段均摊，因此我们只需要写一棵单点修改，区间赋值或区间加减的维护 pair 和的线段树就行了。

切树，NFLSP12956

我们可以很容易的得到一个维护集合的dp，进行一个神秘的 Reduce 操作后，注意到值域跨度原来是 O((R-L)*k)，除掉了一个 O(R-L)，此时我们只需要维护 O(k) 个就行了。

怎么 Reduce 呢？我们注意到对于 a<b<c,c-a<R-L，那此时我们的 b 是显然没用的，b 任何有用的情况都能够被平替掉，因此任意一个的间隔就是 O(R-L) 了。

总复杂度是 O(NK^4) \to O(NK^3)，因为树形背包。

地地铁铁，P8456 NFLS18117

建圆方树分讨。

答案为 All - \text{属于同种颜色的方案} - \text{混合块的特殊处理}。

通过很多个桶把复杂度平衡下去。

偷走零件， NFLSP743 BZOJ4647

注意到，我们除了 k=1，剩下的 F_k 是 F_{k+1} 的前缀。

因此我们只需要处理 k=44 的时候这个超级长的序列，询问直接做就行了。

考虑把 A 串和 B 串都变成比 S 串长的情形，此时我们的 S 串子串出现的位置只有 A-B，B-A，B-B 三种情形。

我们把询问变成：求 \sum_{i=a}^{b-(d-c)} \operatorname{LCP}(C,i)>=d-c+1 状物。然后我们根据 起始点所在串 分类，建出 SA 询问即可。这样做的目的是减少一些分类套路。最后的答案变成一堆 A-B,B-A,B-B 和一个首尾段查询。这东西建主席树是好搞的。

写小心一点。