thyzzs's Blog
【笔记】Knuth-Morris-Pratt 算法 【笔记】Knuth-Morris-Pratt 算法
Part 1 简介 模式串匹配，就是给定一个需要处理的文本串（理论上应该很长）和一个需要在文本串中搜索的模式串（理论上长度应该远小于文本串），查询在该文本串中，给出的模式串的出现有无、次数、位置等。 Part 2 前缀函数 给定一个长度为
2019-11-13 Life in OI
字符串
【笔记】CDQ分治 【笔记】CDQ分治
CDQ分治，即基于时间的分治算法，最早被陈丹琦引入国内而得名
2019-11-12 Life in OI
离线算法
【笔记】珂朵莉树 【笔记】珂朵莉树
珂朵莉树（Chtholly Tree），又名老司机树（Old Driver Tree, ODT），是一种非常暴力的维护序列信息的数据结构。
2019-11-12 Life in OI
数据结构
【笔记】扫描线 【笔记】扫描线
扫描线一般运用在图形上面，它和它的字面意思十分相似，就是一条线在整个图上扫来扫去，它一般被用来解决图形面积，周长等问题。
2019-11-12 Life in OI
计算几何
【笔记】可持久化线段树（主席树） 【笔记】可持久化线段树（主席树）
可持久化线段树(在中国国内信息学竞赛社区中又称总书记树、主席树或函数式线段树)是一种可持久化数据结构（Persistent data structure）.
2019-11-10 Life in OI
数据结构
CSP-S 2019 冲刺训练计划 CSP-S 2019 冲刺训练计划
根据 luogu-problem-list 2.0 版本 制作
2019-10-26 Life in OI
训练
肥城一中FOI 2019级宣传 肥城一中FOI 2019级宣传
OI是什么？ 信息学奥林匹克竞赛(OI,Olympiad in Informatics)。 与大家熟知的数学、物理、化学、生物竞赛合称为高中五大学科竞赛。 肥城一中FOI为学校官方组织，也是唯一的官方社团，又名信息学奥赛小组。 OI学什么？
2019-09-20 Life in OI
宣传
【笔记】基于链式前向星的图论算法（三） 拓扑排序 【笔记】基于链式前向星的图论算法（三） 拓扑排序
有向无环图(DAG)可用来表示各种事物的顺序。比如以各项工作为顶点，用有向边来表示工作顺序。 如果对这种表示顺序关系的DAG进行拓扑排序， 我们便能得到一个恰当的工作顺序。 拓扑排序不是用于将n个数从小到大排序，而是对于一个DAG，对图上的
2019-09-13 Life in OI
图论
【笔记】基于链式前向星的图论算法（二） 最短路 【笔记】基于链式前向星的图论算法（二） 最短路
Part 1 单源最短路（SSSP） Dijkstra Dijkstra只能用于无负权边的图。 设图$G=(V,E)$所有顶点的集合为$V$，起点为$s$,最短路径树中包含的顶点集合为$S$。 在各计算步骤中，我们将选岀最短路径树的边和顶点
2019-09-13 Life in OI
图论
【笔记】基于链式前向星的图论算法（一） 搜索 【笔记】基于链式前向星的图论算法（一） 搜索
Part 0 缘起 近日整理笔记时发现，初学时的图论算法都是基于邻接矩阵储存的，使用时非常不方便。所以就写了这篇博文，聊作图论学习的回顾。 Part 1 图的链式前向星表示 链式前向星又称为邻接表的静态建表方式，其最开始确实是基于前向星，是
2019-09-08 Life in OI
图论
【笔记】C++的常数优化技巧 【笔记】C++的常数优化技巧
Part 0 时间复杂度常数优化的意义 在科学研究意义上，时间复杂度的常数优化并不是十分重要的。 但在信息学竞赛中，同样的复杂度为$O(n^2)$的程序，对于一组 $n=5000$ 的数据，有的可能常数为20，需要运行1000ms，有的可能
2019-09-08 Life in OI
思想方法
题解 T93279 【最长上升子树链】 题解 T93279 【最长上升子树链】
传送门 30%的题解： 这棵树是一个链，所以直接做一遍LIS和LDS，经典DP算法，不多赘述。 60%的题解： $N<=1000$,可以直接$n^2$地做满分题解所说的DP。 满分题解： $F1[i]$表示以从以$i$为根
2019-08-22 Life in OI
题解
3 / 4