例题：（板子） 洛谷板子题P3806 洛谷第二个板子题p4178 说一下 点分治、感觉还看的懂。 经典问题：找一个树上距离为k的有多少对点。 怎么找呢？ 分治思想：递归 也就是找一个合适的根然后把问题分为跨过这个根的两个点 和 不过这个根的距离也就是在一个子树上的两个点和不在同一个子树上的两个点。处理的时候只处理不过这个根的距离（在同一个子树上的）有没有为k的。因为不过这个根的情况在以后会处理到的。然后删掉这个根对他的子树进行上述操作。 找根的时候如果按题上给的根做可能会超时;最坏的时候，对于1->2->3->4->5这种情况时间复杂度是n^2，但是理想的是n*logn...

树链刨分 瞎bb会 重儿子：重儿子是每个节点的儿子节点中子树节点数最大的那一个。 树链刨分，把一个树砍成好多份变成一个数组p，p数组里存的是点的访问到的顺序，但是点的顺序是根据什么来的？先访问重儿子，因为这样可以尽可能多的一下找好长的链。 经典问题：1.给树上两个节点之间的最短边上加上val；2.查询两点的最短距离； 用到好多数组，解释一下数组的含义： int p[maxn];//遍历的顺序 时间戳 或者说是位置 感觉主要用这个  int fp[maxn];//p的相反 fp[p[i]]=i; int fa[maxn];//父节点 int dep[maxn];//深度 int son[maxn...

区间合并 说一道例题：poj3667 题意: 两种操作： 1 s 查询有没有连续为s的区间有的话输出最左端的那个位置并把那个区间里的值都减了 2 a s 左端为a长度为s的房间退房 也就是a~a+s-1这个区间值都加一 考虑怎么做。。 可以给线段树里放一个lnum，rnum，num分别代表左边连续最大，右边连续最大，总的连续最大，的空房，然后up的时候当前的lnum就等于左边的lnum；当前的rnum就等于右儿子的rnum；num就等于目前的和 左儿子的 和 右儿子的 和 左儿子的右加右儿子 的左最大值；这里注意计算lnum和rnum的时候 如果左儿子里的区间是满的然后 lnum就不是左儿子的...

突然发现自己好菜~这都不会。。。 来记录一下我学的扫描线 扫描线可以解决矩形面积的问题,如:给出n个矩阵有重叠部分，问你面积（各种面积）。 然后，原理：  画的歪歪扭扭好歪好扭 黄线就是扫描线了。 然后 线段树里一般维护的是矩形所在当前扫描线上的长度。（说的不太清） 就是 好歪好扭 凑合吧 画括号的长度就是所要维护的长度 横着的长度不用线段树维护 因为横着的长度就是a[i]-a[i-1] 。 然后线段树维护的时候 有一个特别的地方 就是 比如： 正常的线段树区间是1~5 子节点：1~3 4~5 但是这里就会把3~4区间里的东西丢了 所以是1~3 3~5 然后叶子结点的l、r ： l+1==r ...

最小路径覆盖？ 概念：最小路径覆盖就是找出最小的路径条数，使之成为P的一个路径覆盖． 前置知识： 匈牙利算法 为什么要用匈牙利算法？ 首先 每个点都可以代表一个简单路径 答案是n 但是要求最小的 路径覆盖 用匈牙利匹配他的下一个节点 （他的下一个节点只能有一个,因为是有向无环图）。 意思是把这两个简单路径连起来 合为 一条路径，然后答案个数就会-1。这也就是为什么最小路径覆盖=n（节点个数）- 最大匹配数。 这个算法比较简单。。。 例题（板子）： poj1422 题意：给你一个有向无环图。然后往点上放人 问你 最少放多少个人在不重复走相同的点的情况下可以把这些点走完。显然是最小路径覆盖问题。 ...

读大佬的博客 附上链接，，图也是人家的 对不起 QAQ 曼哈顿距离 曼哈顿距离：d(i,j)=|X1-X2|+|Y1-Y2|. 也就是横纵坐标差的绝对值的和。 切比雪夫距离 切比雪夫距离：二个点之间的距离定义是其各坐标数值差绝对值的最大值 一个是和、一个是最大值 。废话  曼哈顿距离的图 两者可以相互转换，  切尔雪夫的图 很像？两者可以相互转换 原坐标系中的 曼哈顿距离转切尔雪夫：坐标：(x+y,x-y); 原坐标系中的 切尔雪夫转曼哈顿：坐标：((x+y)/2,(x-y)/2); 两个式子互逆 换了之后 原图中的曼哈顿就等于现在图里的切尔雪夫 有的题中 如果用曼哈顿比较麻烦 就可以换成切尔...

可持久化并查集 简单来说就是两颗主席树 一颗维护 父亲节点是谁 一颗维护 深度 为什么要维护深度？ 降低时间复杂度 并查集如果不优化的查询的话是这样: int findx(int x) {  return x == fa[x]?x : findx(fa[x]); } void hebing(int x,int y) {  int xx = findx(x); int yy = findx(y); if(xx != yy) {  fa[xx] = yy; } }  这个时间复杂度最坏可以到达O(n) 的 优化一： 路径压缩是这样： 基本是常数复杂度? void hebing(int x,int ...

Educational Codeforces Round 69 (Rated for Div. 2) D 题目链接 题目大意： 输入一个数组 n m k 求在数组中找一段连续的数求 ∑ai − k * ⌈(r−l+1)/m⌉ 的最大值 显然 r - l + 1 是找的连续的数的长度； 这个题m大小才10 于是长度只要每增加 m 当前答案就会相当于第i-m个减少 k 增加 sum[i] - sum[i-m]；但是 还有一种 ： 就是不接到第i-m后面 也就是说起始点在 i-m ~ i 里 所以可以枚举i-m ~ i 再与接到 i-m 后面（起始点在i-m之前）取个最大值 最后取个答案就完了 代码...

牛客练习赛 56 E 题目链接 这道题其实并不难，为什么要写他呢？ 因为被他坑了 题目： 给一个图，自己加上一条边后，问随机删去一条边后让图不连通的最小概率。 很明显缩点建图 然后 跑个树的直径 设直径为 d 缩点图上共 m 条边 原先图*** s 条边 答案就是 (m-d)/(s+1) 但是 只能过%95的样例 为什么？？ 有重边 好吧 我的板子有问题 那个Tra……的算法 无向图求缩点：我本来写的是防止回到他的上一个节点 x==fa continue； 但是这样的话如果这两个节点间有两条边 他就是一个强连通分量 就可以回到上一个节点所以板子改进一下。。。 #include<stdio...

最长树链 题目链接 这道题让我明白了运气是实力的一部分 暴力出奇迹 题目大意： 给一棵树 让求最长的树链: ***，这不就树的直径吗 给每个点权值，找出的链要满足链上的点的权值的 gcd > 1 然后 找一个最长的 所以怎么做呢？ 一直想不出来没想到就是暴力，怎么暴呢？就是枚举质数，但是枚举所有质数太多了，所以先找出所有点权的质因子，然后%这个质因子是0的点才能走，所以就是暴力？ 但是我还是会tle 于是加了个快读。。此时语言:c++11毫不留情的tle，加了快读但是更慢？ 于是t了几发换成了c++14直接ac？？ 大佬博客说 质因数个数是log级别的 然后 枚举再跑图 就是 O(能过)...

区间gcd 题目链接 题目大意： 两种操作 ： Q l r 查询 l~r 的区间gcd C l r x 将l~r 区间的数都加上x 怎么做？ 我这tm都不会 好菜 想一下怎么求gcd？ 辗转相减？ gcd(a,b) == gcd(a,b-a); 所以 gcd(a1,a2,a3,a4,……) == gcd(a1,a2-a1,a3-a2,a4-a3,……) gcd(al,al+1,……) == gcd(al,al+1-al,……) 所以维护差分数组的gcd就好了 为什么维护差分数组呢 因为区间修改 可以改为 单点修改 这样维护gcd很舒服 维护一个差分数组 还得维护 一个a[l]的值 怎么维护？ ...

小魂和他的数列 题目链接 题目大意 给出一个数列，让求长度为k的严格递增子序列有多少个 怎么做呢？ 显然dp 这个是很好想的 for (int i= 1; i <= n; i ++ ) {  dp[i][1] =1; } for (int i = 2; i <= m; i ++ ) {  for(int j = i; j <= n; j ++ ) {  for (int k = 1; k < j; k ++ ) {  if(a[k] < a[j]) {  dp[j][i] += dp[k][i-1]; } } } }  这个dp显然tle 所以 当时没有做出来。 ...

分块 分块是啥？ 暴力？ 以前看分块看了一半，放在那里了，，今天想起来了，就又看了一下 分块的思想：把n分成根号n块然后暴力， 这也没啥，主要是记录一下 大段: 被分成的块 一大块 假设要维护的区间是 l~r 把在这个区间里的大段区间暴力维护一下，把两旁的不是一整段的小段暴力维护就好。 时间复杂度：根号n 例题：acwing 243 题目是 给出一个数组 两种操作： Q l r 查询l~r的区间和 C l r x 把l~r区间里的数都加x 为什么不用线段树？树状数组？ 因为我在学分块hhhhh 以下代码 代码： 代码下面有解析 粗心使人心态崩 ——我说的 #include<stdio.h...

cf1189d1 题目链接 题目大意 有一种操作： 选择两个叶子结点，把两个点的最短路径上的权值同时加或减任意一个数 给出一棵树，问你是否可以经过操作把这棵树上的权值变成任意数 刚开始我的想法：在每一个非叶子节点上必须直接相连一个叶子结点（错的） 比如这样：  因为我感觉只有这样才可以满足条件 正当我准备大大大大大大大大写特写的时候， tg来了，这道题我写过，特判度数为二的点就行了。 嗯？？？ 我怎么想不到 好吧 是我菜了 我的那个思路是错了 大错特错了 明显错了。。 代码： #include<stdio.h> #include<algorithm> using nam...