题意 给你一个长度为的序列，请你构造一棵二叉排序树，从第二个数开始依次输出每个数的父亲节点。 题解 正常用递归去插入构建一棵二叉排序树，若当其为一条链时复杂度就会变为这肯定是会超时的。所以我们不能直接构建一棵二叉排序树。由于所有的数都是不同的，那么可以用和来模拟构建一棵二叉排序树。对于每次输入的数，我们用中的来找到第一个比输入值大的数，如果找到了且该点的左儿子不存在，就把其插入中该节点的左儿子，若没找到，若没找到，或者左子树已经存在了，那么我们就去找小于这个数最大的数。将输入的数作为其右儿子。 复杂度 时间复杂度为 代码 #include<bits/stdc++.h> using ...

题意 给你一棵二叉排序树的后序序列，求这棵树的先序序列。 题解 我们知道若要构成一棵树需要知道这棵树的前序和中序，或者后序和中序。现在我们只有后序那么如何构建这棵树呢。因为二叉排序树的中序遍历就是序列的排序结果，也就是说我们有了这个序列就有了这个序列的中序遍历即1到n。那么就可以用中序和后序去构建这二叉树了。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; const int N=1e4+5; int post[N]; void dfs(int x,int l,int r) { if(l>r) return;...

题意 给你一个中缀表达式即一般的算数表达式，输出前缀和后缀表达式，中缀表达式只由小写字母，构成。 题解 我们可以考虑利用中缀表达式来建立一个表达式树，考虑表达式树中，操作符是作为父节点然后变量是作为儿子节点的。那么然后建立一个表达式树呢。这实际上和优先级有关，，我们可以每次找最后一个运算的操作符将其作为当前表达式树中的根，然后该表达式中的左边作为左子树，右边作为右子树。若优先级同级，最右边的作为根。然后这样递归来建立一棵表达式树，建立完之后跑一遍先序和后序就可以得到前缀表达式和后序表达式了。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using na...

题意 给你一个的矩阵，其子矩阵的价值为该子矩阵四个角上数字中的最小值，请你求出子矩阵价值中的最大值。 题解 考虑记录下每个元素的坐标和价值，然后对从大到小排序。因为我们要最大价值的子矩阵，所以排序后从按排序的结果去找子矩阵。我们记录下每个相同行点，他们列所构成的元组。即能构成这样的元组。因为是在矩阵当中的点来构成元组的，所以只有不同行的点才会出现相同列构成的元组。所以我们按顺序遍历点以及构成元组，若在构成元组的过程中出现了之前已经构造过的元组，这说明能形成一个矩阵。此时我们所遍历的点的即是答案。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using ...

题意 给你长度为的序列，以及每次要求删除的数的位置，让你输出每次删除一个数后，剩下的子段中，每段和的最小值。 题解 我们可以用和去维护子段的区间以及子段和。我们先求一个前缀和，这样能快速求解出子段和。一开始我们在中压入和表示整个区间的边界，在中压入的和，表示一开始区间和。然后对于每次读入的位置，我们用在中找被分割成两段的区间的有边界，那么其迭代器--就是左边界了，于是我们可以把原来的区间在中删除然后压入新的区间和。再将删除数的位置压入。每次操作的结束时，的就是最小的区间和了。 复杂度 时间复杂度 代码 #include <bits/stdc++.h> using namespace...

题意 给定一个长度为的序列，求其最长的子序列的长度，其需要满足。 题解 考虑，我们开一个数组记录作为序列中最后一个数二进制下若各个位置为时所能达到的最长长度。因为若要，则说明其二进制下某一位都是。由于只要一位相同都是之外，别的可以等价，所以我们可以每次更新的最长长度，为当前可以用的中的最长长度。 复杂度 时间复杂度为 代码 #include<bits/stdc++.h> using namespace std; int f[32]; int main() { int n; scanf("%d",&n); int ans=0; for(int i=1; i...

题意 给你一个排列数求他有多少个质因子。 题解 首先知道排列数，这相当于从开始往后乘个数。令，表示的质因子个数，那么是符合的。所以原式可以看作。若我们预处理出内的数的质因子个数求个前缀和，就可以在的复杂度下实现查询了。那么怎么求解出内每个数的因子个数呢。我们先求解一下内有多少个质数，存到数组中，那么可以得到转移方程，，，其中是第一个能整除的质数。然后我们可以求一个前缀和，然后在的复杂度下实现查询了。 复杂度 时间复杂度预处理查询 代码 #include<bits/stdc++.h> using namespace std; const int N=1e6+5; int prime[...

题意 给你个数字，问你从中取出个数字进行排序后，使得这个相邻数字之间作差的最小值最大，这个最大的最小值是多少。 题解 由于是求最小的最大值，这个其实是满足二分的性质的，我们可以去枚举差值的最小值。那么怎么验证答案呢。考虑先把序列排序了，那么第一个元素肯定是要选的，接下来我们往后找当前元素大于等于的元素，并记录下他作为当前元素。这样遍历一遍，看有多少个数，如果比大说明我们枚举的太小了，反之说明枚举的太大了。即可进行二分。 复杂度 时间复杂度为 代码 #include<bits/stdc++.h> using namespace std; const int N=1e5+5; int ...

题意 给你个序列的长度，根据归并排序，每次选择序列进行合并使得最后只剩一个序列，每次和并的花费是这些序列长度之和。问在排序完之后总的花费不超过，一次可以合并不超过个序列，问最小的是多少。 题解 对于最小的我们可以考虑去二分答案。但是如何去检验这个答案呢。第一点由于是一次可以合并最多个，也就是并不是说能每次合并个然后最后只剩一个的，有可能最后不足个，所以我们需要提前将多余出来的部分合并起来。那么多出来多少个呢。由于每次合并会生成一个新的而少个，且最后需要剩下一个，所以合并剩下的为。所以我们可以提前合并最小的个，这样就能保证后序的刚好能合并完且是最小的。接下来我们就可以每次取最小的个去判断是否总的...

题意 给你整数唯一分解后的结果，即质数以及其对应的次幂。求所有的因子是什么。 题解 有了唯一分解的结果之后，的因子实际上是质因子的组合，所有我们可以用来求的所有的因子，有的因子，且所有因子的次幂总和为个，那么的出口就是但递归层数为时表示我们所有的因子都遍历过了。我们在递归时定义一个中间变量表示当前已经乘了质因子的数，对于，先递归，再乘因子。 复杂度 时间复杂度为 代码 #include <bits/stdc++.h> using namespace std; vector<pair<long long,int> >fac; vector<long lo...

题意 给你个人的之间比赛的胜率，这之间进行单淘汰赛制，问编号为的人夺冠的概率是多少。 题解 首先单淘汰赛制和二进制的关系很密切。设某一轮比赛为，求和两只队伍是否能比赛，下面我们用二进制来表示队伍的队号 0001(1) 0010(2) 0011(3) 0100(4) 0101(5) 0110(6) 0111(7) 1000(8)我们让所有的队伍先减1得到 0000(1) 0001(2) 0010(3) 0011(4) 0100(5) 0101(6) 0110(7) 0111(8)对于第局比赛只能是相连的两支队伍进行比赛，我们观察一下发现，，，，他们除了最后一位，他们的前缀都是相同的，那么我们抹去...

题意 给你个序列，依次合并这个序列，并且每次输出合并后序列的中位数。 题解 可以考虑用两个堆来维护中位数，即对顶堆，假设中位数为，我们让大根堆中存入所有小于的数，让小根堆中存入所有大于等于的数，即小根堆的堆顶是较大的数中最小的，大根堆的堆顶是较小的数中最大的。将大于大根堆堆顶的数（比所有大根堆中的元素都大）的数放入小根堆，小于等于大根堆堆顶的数（比所有小根堆中的元素都小）的数放入大根堆。那么就保证了所有大根堆中的元素都小于小根堆中的元素。那么我们只要去维护大根堆的元素个数和小根堆的元素个数差值不大于1。元素个数较多的堆的堆顶元素即为当前中位数，如果元素个数相同，那么就是两个堆堆顶元素的平均数。...

题意 有种边长为个数为的等边三角形。边长小的三角形可以放入边长大的里面。还需要一个三角形，将所有的三角形可以放入其中，问这个三角形的边长是多少。 题解 首先若大三角形的边长是小三角形的两倍，则一个大三角形可以放入4个小三角形。由于给定的种是边长不相同的三角形们，所以我们可以对于某一种三角形判断其需要多少个别的三角形来装入，对于当前这个三角形的数量，我们第一次除以4向上取整就是需要比他边长大一倍的的三角形的个数了，我们再继续除以4向上取整这样除几次我们就可以得到能装下当前这个三角形所需要的最大三角形边长了。对于给定的每个小三角形，我们都求一个他所需要的最大三角形边长，答案为这些值中的最大值。两种...

题意 给你一个字符串，你可以将里面的字符改变成任意其他小写字母，要求在最小的更改次数下，使得更改后的串能重排出字典序最小的回文串。现在给你这个串，求修改次数最少重排后的回文串。 题解 改变和重排都不会变化字符串的长度，所以我们先考虑每个字母分别有多少个。为了构造回文串，除了中间字母所对应的字母个数可以为奇数个，其他字母应该都为偶数个。所以我们可以按照字典序先遍历字母，遇到一个奇数的字母其个数加一，我们再从逆字典序往回找，遇到第一个奇数时其个数减一。若字符中最多只有一个为奇数则退出。这样能保证能构造出字典序最小的字符串。那么除了唯一一个奇数字母，我们按顺序输出每个字符个数的二分之一，然后再倒转一...