基础数论学习总结
原本打算先学Splay的，但想到提高组一般不考，而且我其它东西还差的多，就先把基础数论的东西复习一下，并且加深一下难度，还做了n多道水题，虽然主要是之前没过的。
1.整除
这里就把整除的性质列一下：
如果 $a \mid b$ 且 $b \mid c$，那么 $a \mid c$
$a \mid b$ 且 $a \mid c$ 等价于 $\forall x,y$，有 $a \mid (b...
点分治总结
我自己感觉点分治是一种比较玄学神奇的算法，感觉自己也只是理解了一点皮毛而已。这里就谈谈点分治的实现方法和一些运用。
方法
点分治其实是将一棵树的点不断分为多棵子树，分别得到子树节点到子树根的距离来进行处理。
既然要有一个点为根节点，那么应该选取哪一个点呢？
既然要向下分治，如果把一个原来的叶节点作为分治的根节点，那么遍历每一个点的时间开销是非常大的。然而如果这个点的左右子树都达到最大，那么...
题解-洛谷P4092 [HEOI2016/TJOI2016]树
第一次写树剖没看题解A题，发现题解洛谷题解区大佬里竟然没有一个做法一样的，实在是太激动了
树剖学习：https://llf0703.com/p/shu-lian-pou-fen.html
题目链接 洛谷 P4092 BZOJ P4551
方法
裸树剖 ，直接用线段树维护每一段区间中被标记的最深的节点就行了。先全部赋值为-1，然后向上传递时直接取两段中的最大值即可（因为越深的点d...
二分图匹配
我是看这篇学懂的，真的写得很好，所以我就不在这里总结了，只发个模板
https://blog.csdn.net/dark_scope/article/details/8880547
模板题：洛谷 P3386【模板】二分图匹配
#include<bits/stdc++.h>
using namespace std;
bool edge[1005][1005];
bool used[...
题解-洛谷P2486 [SDOI2011]染色
题目链接：
洛谷 P2486
BZOJ P2243
方法
可以想到，颜色段的个数也是具有可加性的，但是如果两段连接处（即线段树中左子树的最右边的点和右子树的最左端的点）的颜色是相同的话，中间就只能算作一段，需要将颜色段个数-1。
所以我们在线段树里多加两个变量，分别为这一段最左端的点颜色和最右端的颜色，合并时和查询时判断一下即可。
注意的是查询链上时也需要判断。每次查询时记录一下左端点...
树链剖分总结
作为一个上个月刚学完线段树的蒟蒻，看Splay又看不懂，便直接跳着来学树剖了。又在一个博客上看到说学树剖之前最好还要把LCA给学了，便去花了一天学了一个Tarjan求LCA（然而后来发现并不怎么需要），然后是几乎照着别人的代码把树剖抄懂的。在这里我就讲一下我理解的树剖。
准备工作
链表/链式前向星
线段树/树状数组/Splay等可以维护一段数据的数据结构
LCA （其实只涉及到一些思想，...
LCA问题总结
概述
最近公共祖先（LCA）问题指的是在一棵树中，求出任意两个点的最近的公共祖先。如在下图中：
2号节点和1号节点的LCA是4,3号和2号的LCA也是4.
求LCA的方法主要有：暴力，倍增，RMQ和Tarjan。
这篇文章以洛谷P3379 【模板】最近公共祖先（LCA）为例。
Tarjan算法
Tarjan算法能够通过dfs将树上节点信息和查询的信息一次性解决，但是无法应对存在修改的情况，...
RMQ问题_ST表总结
RMQ问题
RMQ问题是指多次询问一个区间中最小或最大值的问题。但是因为不包括修改，只涉及离线操作，所以线段树或者树状数组显得有一些多余了。而且数列中的元素个数可能非常大，像线段树开四倍空间肯定是要MLE的。这里介绍一种高效的ST表来解决这种问题。
ST表
我的理解：ST表运用动态规划和二分的思想来完成。
ST表查询问题包含初始化和查询操作，其中初始化的时间复杂度为$O(n\times \l...
题解-洛谷P1309 瑞士轮
原题链接 洛谷博客该题解链接
题目内容
题目背景
在双人对决的竞技性比赛，如乒乓球、羽毛球、国际象棋中，最常见的赛制是淘汰赛和循环赛。前者的特点是比赛场数少，每场都紧张刺激，但偶然性较高。后者的特点是较为公平，偶然性较低，但比赛过程往往十分冗长。
本题中介绍的瑞士轮赛制，因最早使用于1895年在瑞士举办的国际象棋比赛而得名。它可以看作是淘汰赛与循环赛的折中，既保证了比赛的稳定性，又能使赛程不...
几种排序方法总结
冒泡排序
方法
第一次将每一个元素和它的后一个元素比较大小，如果不满足顺序则交换，这样即可确定最后一个数的位置。然后再从头开始，可以确定倒数第二个数的位置。循环n次后即可完成排序。因为每一轮排完序后都会确定一个，即“冒”出来一个，故被称作冒泡排序。
时间效率：$O(n^{2})$
代码
以 洛谷 P1116 车厢重组 为例
#include<bits/stdc++.h>
usi...