今日主要学习树论。 一.最近公共祖先（LCA） 最近公共祖先的求解主要分为几个部分： 1.初始化：加边，初始化每个节点的祖先节点，初始化每个节点的深度。 加边：使用vector存储，注意一共输入n−1n-1n−1跳条双向边。 初始化每个祖先节点： f[x][0]表示节点xxx的父亲。 f[x][1]表示节点xxx的祖父（父亲的父亲）。 f[x][2]表示节点xxx的超级祖父（祖父的祖父）。 由此可知：f[x][i]=f[f[x][i−1]][i−1]f[x][i]=f[f[x][i-1]][i-1]f[x][i]=f[f[x][i−1]][i−1] 初始化每个节点的深度：每个节点的深度=每个节点的父节点深度+1 2.求最近公共最先：将两个点提升至同一高度，找寻它们的公共祖先。 将两个点提升至同一高度：一层一层的提升会超时间复杂度，选择倍增的思想。 寻找它们的公共祖先：从后往前找，使用排除的思想。 模版：链接描述 代码： 二.树上路径最小值 其实和上一题差不多。 但是需要求最小点权，所以需要多加一个mi[][]mi[][]mi[][]数组。 mi[][]mi[][]mi[][]和上一道题目中的f[][]f[][]f[][]差不多。 它表示的是节点xxx到xxx的父/祖父/超级祖父节点的最小点权。 这是mi[][]mi[][]mi[][]的计算公式：mi[i][j]=min(mi[i][j−1],mi[f[i][j−1]][j−1]);mi[i][j]=min(mi[i][j-1],mi[f[i][j-1]][j-1]);mi[i][j]=min(mi[i][j−1],mi[f[i][j−1]][j−1]); 代码： 三.树上差分 这是一个比较古怪的题目，要考虑如何在树上做差分的同时，也代表要在树上做前缀和。 题目：链接描述 大概是这样子的： （两个）

LCA,树上差分，树的直径，数论，最小生成树，并查集，逆元，Floyd，树的重心（换根） 15 5 15 kuai 5 10 10 5 15 LCA复习已完成。 树上差分复习已完成，但需要重做。 树的直径已完成，有时间可考虑重做。 快速幂已完成。 逆元已完成。 并查集已完成。 最小生成树已完成。

我知道怎么写，但我就不告诉你，诶，就是玩

诶？不好意思，14行多写了个换行，删了就行

这题还是太难了，我第一遍都错了

在键盘上同时按fn和字母e，就能随时打开表情包窗口啦！大家可以尝试一下哟！

https://www.acgo.cn/discuss/rest/46127

本文将分为五个部分： 进制转换 哈夫曼树 排列组合 表达式 位运算 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 进制转换 首先我们要明白进制是什么 进制：数字的位数规则 比如说我们用的正常的数字就是十进制的，他的每一位上最高只能是9，经典的二进制一样，每一位上最高只能是1，所以k进制每位最高是k-1 那么进制怎么转换能，咱们需要一个借位，也就是十进制，如果x进制要转y进制，则要先转十进制，再转y进制 先来讲x进制转十进制： 我们先来看一个数 107415 随机取一位7 7是7个1000，也就是7*10310^3103，他是第4位，刚好是位数-1，那么其他是不是这样呢？ 我们再来看5，他是5*10010^0100,是第1为，也对上了 那么k进制就是x*kyk^yky,是第y+1位 我们可以推出这样一个式子： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 至于十进制转x进制吗 我直接说吧：短除法 自行理解 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 哈夫曼树 这个可以说是最简单的东西了 就是利用规则构造一个树 规则：将序列里最小的两个数据到一起放回队列并重复 构成的树左边是0，右边是1，某节点的编号就是路径上的数字 注意：合成的元素不一定是最小的，否则就要从新找小的元素 比如序列 {1 4 2 5 9 12 6} ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 排列组合 排列 假如有这样一个问题：有6个不同的人排队，共有多少种解法？ 相信你不会一个一个列，那么我们来看一个思路： 一号有6种方式 二号有5种方式，因为总有一个是被1占了的 以此类推，到6号时只剩一个位置 然后遍历一遍，就能得到一个式子： 6 * 5 * 4 * 3 * 2 * 1=720 假如说有7个位置，但有六个人呢？ 第一个人有7个 第二个人有6个 直到最后1个有两个位置 则能推出式子:7 * 6 * 5 * 4 * 3 * 2=5040 这样，我们就得到了排列公式：A 即=m * (m-1) * (m-2) * …… * (m-n+1) 组合 有10个苹果，我要取三个吃，有多少种方式取？ 还是现将这三个排列，得到10 * 9 * 8=720 但是这是排列，讲究顺序，可组合不讲究顺序，所以我们还需要除以个 即 另外有一种经常考的题型，就是某某某要挨在一起，这种就是把挨在一起的当一个人来算，在乘一下挨着的人排列总数 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 表达式 表达式是我们用的一种式子，由+-*/、数字、括号组成的 表达式的数字永远比符号多1 位缀表达式 表达式氛围前缀种植和后缀 前缀被称为波兰式，而后缀则是逆波兰式，中缀是我们现在用的式子 中缀转前缀： 先转最高运算律的，把符号搁到式子前面，再把式子当成一个数，从新放回表达式 比如（变化步骤）: 中缀：A*B+C-D/E *AB+C-D/E *AB+C-/DE +*ABC-/DE 前缀：-+*ABC/DE 中缀转后缀转后缀也是如此，只是把符号放到式子后面 前/后缀转中缀： （如果是转入中缀，就不分前后缀，唯一的区别就是扫描方向相反） 咱们需要一个栈 然后重复以下操作： 遇到数字放到栈里 遇到符号去除栈里头两个数并转回中缀表达式（把符号放两数中间），再把这个中缀表达式当成数字放回栈 直到栈里只剩一个数字（式子），那个数字就是中缀表达式 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 位运算 位运算分为|,&,!,~,亦或，同或 当然，有时候 与 是这样的^， 或 是∨，而取反是¬ &：1&0=0，0&1=0，0&0=0，1&1=1 |：1|0=1，0|1=1，0|0=0，1|1=1 ！（~）：！1=0，！0=1 亦或：1亦或1=0，1亦或0=1，0亦或1=1，0亦或0=0 同或：1同或1=1，1同或0=0，0同或1=0，0同或0=1 位运算计算规则 将a数和b数转成二进制，然后按位进行运算，空位要补0 把结果转换回十进制，如：

快发题解，根本通不了

一、基础框架代码 二、变量与输入输出 变量定义‌ 输入输出‌ 三、分支结构模板 IF-ELSE结构‌ SWITCH结构‌ 四、循环结构模板 FOR循环‌ WHILE循环‌ 五、数学函数应用 六、字符串处理 字符串遍历‌ 回文判断‌ 七、进制转换代码 十进制转R进制‌ 八、位运算示例

这里是综合目录，各个链接如下： * 赛事讨论帖 * 题解帖 * 获奖通知帖

二分答案 1、确定单调性/二段性 二段性题目：找分界点 2、二分模板 int l=答案可能的最小值, r=答案可能的最大值; int ans=0; while(l<=r){ int mid=(l+r)/2; if(check(mid)){ ans=mid; // 求最大值 l=mid+1; // 求最小值 r=mid-1; } else{ // 求最大值 r=mid-1; // 求最小值 l=mid+1; } } 3、check 函数 具体问题具体分析 需要检查当前二分的答案是否符合题目要求 明确所有变量代表的意义 最后和什么比? 题目中的某一个定值 4、如何提升自己二分答案的能力

动态规划（DP） 解决 最值问题、方案数问题、可行性问题 第一步：设动态规划数组（确定状态表示） dp[i]: 第 i 步的方案数是多少 / 走到第 i 步的最大 / 小花费是多少 dp[i][j]: 走到第 i 行第 j 列的方案数 / 最大值 / 最小值 第二步：写出状态转移方程（递推式） 方案数 dp[i] = dp[i-1] + dp[i-2] + dp[i-3] + ... + dp[i-k]; 最大值 dp[i] = max(dp[i-1], dp[i-2]+a[i]); 最小值 dp[i] = min(dp[i-1], dp[i-2]+a[i]); 第三步：初始化 dp[1] dp[2] dp[3] 最小值 for(int i=1;i<=n;i++) dp[i]=1e9; memset(dp,0x3f,sizeof(dp)) // 把数组中所有的值赋值成某一个数字 dp[1]=0; 第四步：求出答案 dp[n] dp[n][m]

WA\color{red}WAWA ononon222 MLE\color{blue}MLEMLE ononon444

AC代码你提交都提交不上去，包爆内存的，还有字数限制

#include<algorithm> #include<sstream> #include<bitset> #include<conio.h> #include<fstream> #include<iterator> #include<complex> #include<deque> #include<exception> #include<functional> #include<iomanip> #include<ios> #include<iosfwd> #include<iostream> #include<istream> #include<limits> #include<list> #include<locale> #include<map> #include<memory> #include<new> #include<numeric> #include<ostream> #include<queue> #include<set> #include<stack> #include<stdexcept> #include<streambuf> #include<string> #include<typeinfo> #include<utility> #include<valarray> #include<vector> #if __cplusplus >= 201103L #include<array> #include<atomic> #include<chrono> #include<condition_variable> #include<forward_list> #include<future> #include<initializer_list> #include<scoped_allocator> #include<mutex> #include<ratio> #include<random> #include<regex> #include<system_error> #include<tuple> #include<typeindex> #include<type_traits> #include<unordered_set> #include<unordered_map> #include<windows.h> #include<thread> #endif 注： ”#include<bits/stdc++.h>“ “#include<windows.h>” #include<conio.h>//万能头不能导入这两个头文件

自己看

最短路，负环，最小生成树，FLOYD，并查集，树状数组，逆序对，单调栈，扩展欧几里得算法，单调队列，树状数组1,树状数组2. 树状数组1已完成。 树状数组2已完成。 并查集已完成。 负环已完成。 扩展欧几里得算法已完成，但并不熟练。 最小生成树已完成。 最短路已完成。 FLOYD已完成。 逆序对已完成。 单调栈已完成。 单调队列已完成。

今天主要学习了提高组复赛知识点：并查集和相关的最小生成树。复习了最短路的一些相关算法。 一.并查集和最小生成树 并查集，最喜欢找爹的一集。 也就是查找最近公共祖先的算法。 也就是在图论中找父亲节点。 但是仔细想想，一个一个节点的遍历过去时间复杂度太高了，所以就有了所谓“路径压缩”。 听起来很诡异，但其实做法非常简单。 看图：链接描述 所谓路径压缩，就是在查找祖先节点的过程中，将自己的父节点转换为父节点的父节点的父节点的..... 这个查找的过程是递归，递归要有截止条件，其截止条件就是当前的节点，它没有父节点/父节点就是自己（根据初始化不同而不同）。 模版代码： 与其相关的还有最小生成树，那个在此不进行解释（没时间了，还要默模版） 最小生成树模版：链接描述 二.最短路问题 DIJKSTRA 对于这个算法不多进行解释，详情请见坐着的其他文章。 模版：链接描述 SPFA 模版：链接描述 FLOYD(阴间版） 模版：链接描述