GoPoux4

分类

未归档(36) 题解(2)

/ 注册

全部文章（共38篇）

题解「SPOJ8093 JZPGYZ - Sevenk Love Oimaster」

转载注明来源：https://www.cnblogs.com/syc233/p/13784426.html 广义SAM+区间数颜色。几篇写广义SAM的题解似乎都没写对啊/fad，都是插入新串时直接将 \(las\) 设为 \(1\) 的，在这篇博客中提到这样建出来的广义SAM是有问题的。 ...

后缀自动机SAM 题解树状数组

2020-10-09

0 473

总结「二次剩余」

转载注明来源：https://www.cnblogs.com/syc233/p/13741831.html 二次剩余，之前从数竞同学那听到过这个东西，觉得在OI中没啥用。直到今天T1考了二次剩余，我才流下了没有数理基础的眼泪。二次剩余，其实就是模意义下开根。给定常数 \(n\) ，...

总结数学

2020-09-27

0 521

总结「李超线段树」

转载注明来源：https://www.cnblogs.com/syc233/p/13722356.html 最近复习了李超线段树，发现网上不同人的写法有较大不同，所以写这篇博客总结一下自己的写法。李超线段树是线段树的一个变种，支持在平面直角坐标系中动态插入线段，查询一条竖线与所有线段的...

总结线段树数据结构

2020-09-24

0 443

题解「Luogu3970 [TJOI2014]上升子序列」

转载注明来源：https://www.cnblogs.com/syc233/p/13693730.html 先不考虑序列长度至少为 \(2\) 的限制和去重，那么这道题就是一个简单的DP：令 \(f_i\) 表示以 \(a_i\) 结尾的上升子序列个数，那么很容易写出转移方程： \...

树状数组题解动态规划

2020-09-18

0 395

题解「Luogu1099 树网的核」

转载注明来源：https://www.cnblogs.com/syc233/p/13693027.html 树的直径+尺取法。题意给定一棵带边权无根树，在其直径上求出一段长度不超过 \(s\) 的路径 \(F\) ，使得离路径距离最远的点到路径的距离最短。题解首先，在 ...

题解树上问题尺取法

2020-09-18

0 507

题解「Luogu5251 [LnOI2019]第二代图灵机」

转载注明来源：https://www.cnblogs.com/syc233/p/13673494.html 珂朵莉树+尺取法+线段树。大体思路是珂朵莉树维护颜色段，线段树维护区间和、区间最值，3、4操作在珂朵莉树上做尺取法。主要说一下尺取法的细节：操作3 询问区间 \([l,...

线段树珂朵莉树题解数据结构尺取法

2020-09-15

0 401

题解「Luogu5665 划分」

转载注明来源：https://www.cnblogs.com/syc233/p/13663639.html 丧心病狂卡时空题题意给你一个长为 \(n\) 的数列 \(\{a_n\}\) ，需要找到若干个分界点 \(1 \leq k_1 <k_2 <k_3<\cdo...

单调队列题解动态规划

2020-09-13

0 348

测试「20200912测试总结」

考完后的心情： T1 「MZOI2020」快速班号变换简单DP题，没处理边界，\(100 \to 70\) 。令 \(f_{i,j}\) 表示使得 \(a\) 串前 \(i\) 位变换到 \(b\) 串前 \(j\) 位的最小花费，则有转移：将 \(a_i\) 变成 \(...

测试总结

2020-09-12

0 355

题解「Luogu4774 [NOI2018]屠龙勇士」

转载注明来源：https://www.cnblogs.com/syc233/p/13654606.html 首先发现对每条龙使用的剑是固定的，于是可以用multiset预处理出对每条龙使用的剑 \(b_i\) 。然后发现题其实是要求一堆形如这个的式子： \[a_i-x \cdot ...

题解数学

2020-09-11

0 495

总结「斯坦纳树」

转载注明来源：https://www.cnblogs.com/syc233/p/13650130.html 姑且当作状压DP的复习了。斯坦纳树问题是组合优化问题，与最小生成树相似，是最短网络的一种。最小生成树是在给定的点集和边中寻求最短网络使所有点连通。而最小斯坦纳树允许在给定点...

总结图论动态规划

2020-09-11

0 472