这是啥这是

-1 前言 实际上这个东西和大部分其他诸如点分治，线段树二分之类，听起来很难很复杂，但是至少其内在的原理和模板题并算不上十分复杂。 然而我好像还是学了很长的时间。 我是菜鸡。 这次尝试换一种不同的风格来写。 0 前置芝士 线段树 分治 （可选的）并查集 （可选的）二分图 1 什么是线段树分治 线段树分治，顾名思义，就是把线段树和分治拼一块（不是）。 但是实际上这么说也有道理。

-1 前言 一次课上的浅谈，随听随记。 0 概述 1 各类数据结构 1.1 线段树 线段树，顾名思义，每个节点都代表一个区间。 从原序列建树，然后按照 [l,r][l,r][l,r] 到 [l,mid][l,mid][l,mid] 和 [mid+1,r][mid+1,r][mid+1,r] 来划分。 叶子节点是长度为1的区间。 一颗维护长度 NNN 的序列的线段树总有 2N−12N-12N−1 个

-1 前言 本人写这个东西的时候十分幽默。 太难绷了于是记录下。 0 前置芝士 归并排序 树状数组 分治 1 相关芝士 1.1 什么是三维偏序 首先我们要了解一下一维偏序和二维偏序 一维偏序：给你一个长为 nnn 的序列 aaa，需要求出对于每个 aia_iai​ 有多少个元素比它小。 这非常简单，排序即可。 二维偏序：一个平面直角坐标系上有 nnn 个点，第 iii 个点的坐标是

0 前言 好久没做题了好像 但是不重要 1 题意 原题面写的十分清楚，可以 [去看](P4310 绝世好题 - 洛谷)。 2 思路 拿到这个题，首先想到DP。而且发现没有序列上的区间最优问题，考虑使用线性DP。 我们用 fif_ifi​ 来表示前 iii 个元素中所能选出的 kkk 的最大值。容易发现如下转移： fi=max{fi,flsti+1}f_i=max\{f_i,f_{lst_i}+1\

-1 前言 许久不见，甚是思念。 0 前置芝士 图论相关基础知识 DFS 1 什么是Tarjan TarganTarjan是一位计算机科学家，全名Robert Tarjan（中文一般译为罗伯特·塔扬）。现在常说的Tarjan一般指Tarjan发明的，以他自己命名的算法。 这个算法可以用于求一个有向图中的SCC，同时其拓展出的很多的方法也用于缩点，割点，割边等问题。 2 一些定义 强

-1 前言 源于一次校内NOIP模拟赛的第一题。 那道题是一道非常板的数位DP，可惜我没学过，只能打一个40pts暴力~~，最后甚至暴力都挂了。~~ 于是乎学习数位DP，写了这篇笔记。 0 前置知识 无 1 用途 数位DP，顾名思义就是对数字的每一位进行DP的一种算法。一般用于解决具有以下特征的问题： 给定一个区间，令你求区间内满足某一特征的数的个数。 数据范围非常大，暴力枚举会超时。

0 前言 某天上午闲着摸鱼的时候看zqq说他们模拟赛出了道很水的紫，于是乎过来品鉴一下。 1 题意 给你一个 nnn 个点 mmm 条边的无向联通图,你每次可以选择一个点,让跟这个点直接相连的点之间两两连边(原来有边的就不用连),问至少进行几次操作才能使这个图变成完全图,并输出任意一种可行的选择序列. 2 思路 一眼 m≤22m\leq 22m≤22,状压. 这道题看上去没啥思路,但是可以稍作转化

0 前言 这道题是一道比较经典的状压DP. 需要先将题目里的条件稍作转化,然后再来处理,进行DP. 1 题意 lg上这道题已经翻译成了形式化题面,这里不再赘述. 2 思路 观察数据范围,发现 m≤20m\leq 20m≤20,从而联想到状压DP. 考虑可以用 fi=1/0f_i=1/0fi​=1/0 表示 iii 这种选择方案是否合法.但是我们发现,这样的话不好直接转移,所以需要进一步处理后再转移

-1 前言 迅速糊出来的一篇东西。 算得上是朝花夕拾了。 0 前置知识 树形DP 1 什么是换根DP 一般来讲,树形DP都是记录一个点的状态,然后在遍历这棵树的过程中转移到相邻的点. 通常,大部分的树形DP题目都会指定或者有一个固定的根.但还有一部分题目,通常不会指定根节点,或者说根节点不是固定的,并且根节点的变化会对树上的一些信息产生影响(比如节点深度).这种题目需要记录根节点的状态,通过转