题意 给你一棵二叉排序树，由于一个序列构造出来的二叉排序树其也可能可以被其他的序列构造出来。所以判断该序列构造出的二叉排序树是否是唯一的是的话输出，否则输出 题解 首先，对于二叉排序树中的一个子树的根节点来说其左右儿子作为序列中的输入值，两者序列位置是不影响在二叉树的位置的，即交换序列中左右儿子的位置树中的位置不变。所以可以得到结论，当树当中有一个节点有两个儿子时其的构成序列就是不唯一的。所以我们判断输出的序列是否一根链即可。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; const int N=1e4+5; s...

题意 给你一棵二叉排序树，由于一棵二叉排序所构造其的序列是不唯一的，求有多少个序列可以构造出该树。 题解 首先我们可以看到题中的的的大小比较少，所以我们可以考虑通过遍历的全排列的方式来找到所有可能的同构序列，每次对遍历序列构建一棵二叉排序树，判断两棵二叉树是否同构用判断对应节点是否相等即可。也可以通过从二叉排序树的最小字典序序列到啊最大字典序序列进行剪枝。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; const int mod=1e9+7; const int N=1e5+5; struct BiTree { ...

题意 给你一棵二叉排序树的构建序列，由于一棵二叉排序树可以用来构建出它的序列不唯一，求字典序最大的序列。 题解 首先根据规则构建出这棵二叉排序树，然后考虑字典序最大的序列如何构造出呢，首先要知道的是对于构建一棵二叉排序树时，其左右儿子的顺序是不影响该树构建的。所以例如对于一棵二叉排序树来说： 4 / \ 2 6 / \ / \ 1 3 5 7我们优先遍历的是右儿子而不是左儿子，由于要保证树的结构，所以每次根节点是优先输出的，这样我们就找到了的规则，以根右左的顺序来遍历该二叉树，就可以实现字典序最大了。 复杂度 时间复杂度 代码 #include<bit...

题意 给你一棵二叉树的前序和中序序列，以及每个节点的权值，让你构建出这棵树，并且再书中找到一棵子树，子树的权值和是最大的，并且该子树是一棵对称树。对称树，指交换其所有左右子树与原树相等称为对称树。 题解 首先考虑一下一棵树如何判断其是否是对称的呢，若当前节点为，那么他的左右儿子为。要满足 ，并且递归下去其子树都满足该性质，，那么其左右子树也要满足即有，递归下去就可以判断以该节点为根的子树是否是对称了，那么如何求求大权值和的子树呢，我们可以先一遍存下以每个节点作为根的子树权值和记为。然后遍历一下每个节点即可。从上面的分析来看，我们需要存的是每个节点的左右儿子是什么，所以我们没必要用链表构建出一棵...

题意 给你一个长度为的数组，可以删除其中的区间，删除一次算一次操作，让剩下的元素的都为一样，且个数与中的这个元素个数相同。问最小的操作次数。 题解 可以先将连续的区间进行合并，例如为，然后统计每个元素出现的次数，第一个出现的元素前面没有元素，最后一个出现的元素后面没有元素，所以都要减一，最后求得最小的出现次数即为答案。因为最少出现的数字说明将数组划分为的区间也是最少的，也就是代表了要删除几次额外的区间。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; const int N = 2e5+5; const int i...

题意 给你一个长度为且元素都不同的数组，将其从小到大排序，但是只能每次选择一个元素将其移动到数组的头部或者尾部，问完成排序的最小操作次数。 题解 首先可以将数字进行离散化，那么就得到了一个的排列，然后考虑哪些数字是不需要移动的，发现递增且差值为的连续子序列不需要移动，其余元素均需要移动。那么问题就转换为找到数组内最长的相差为的子序列，考虑用 ， 表示以数字 为结尾的最长子序列长度，则转移方程为 如果出现了，则在的基础上长度加一，否则是开头，长度为 复杂度 时间复杂度为 代码 #include<bits/stdc++.h> using namespace std; const int...

题意 给你一个长度为的数组，求有多少个区间的和等于区间长度的。 题解 假设区间为，若要使得，我们可以让每个元素，转化为，然后我们统计前缀和有多少个即可。另一种情况是前缀和中出现了两个相同的元素，这说明这段区间的和也是等于长度的，所以我们需要一个映射来记录每次前缀的和。 复杂度 时间复杂度 代码 #include <bits/stdc++.h> using namespace std; const int N = 1e5+5; map<int, int> vis; int a[N]; int main() { int t; scanf("%d&q...

题意 给你一个有个元素的队列，你可以先从队列的队首出队个元素，然后对于剩下的元素你可以任意选择从队首或队尾出队，使得之后的元素出队组成的序列为一个非递减序列。求最小的。 题解 首先若队列中的元素一开始就递增或递减，那么不需要提前出队答案就是。否则我们从队列的后边开始考虑，从后往前找到第一个先递增后递减的序列(逆序考虑)，答案就是减去这个序列的长度，若含有两个这个的序列，这说明无论怎么出队都会出现递减的情况。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; const int N=2e5+5; int a[N]; i...

题意 给你一个，需要将其变为，每次操作可以选择对减一花费元，或对除以花费元，求将变为的最小花费。 题解 如果当前，只能执行次第一种操作，然后答案加。 如果当前不能被整除，那肯定只能执行第一种操作，次。也就是，然后答案加。 如果能被整除，则判断从到那种操作花费更小，设，判断是和哪个小 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; int main() { int t; scanf("%d",&t); while(t--) { int ...

题意 给你一个长度为的数组，中有种不同的数，若则记录加一，现在可以删除一种数使得最终的记录尽量小，问最小的记录是多少。 题意 一个开始总的记录值记为，我们要计算的就是考虑去掉某一种数字所能减少的记录值最大，连续一样的数字都可以合并成一个，例如，就可以转化为。接下来我们考虑的都是处理过的数字，例如对于，这种组合，我们若去掉，答案只会减少，当遇到的是这种情况时，去掉时，答案会减少。遍历一遍处理过的数组，然后记录若去掉该数的贡献是多少。最后遍历找一遍贡献最大的数即可。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; co...

题意 给你一个长度为的数组，每次可以选择一对，将或替换成。求将整个数组变为的最少步骤。 题解 首先若数组中存在，那么就用这个去替换所有就可以了，只需要次操作。否则我们可以考虑先构建出一个来，然后用这个去替换所有的元素。我们可以暴力每次先显然相邻的两个元素进行一次，即嵌套多次，当嵌套到某次时出现了，若当前嵌套层数为，那么最后答案就是次即可。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; const int N=1e3+5; int a[N]; int main() { int t; scanf(&q...

题意 给你一个原始都为长度为的数组，需要将插入到数组中，插入的规则为，每次选择数组中长度最长的连续的区间，将中间的替换成插入的数，若该区间长度为奇数则插入中间，否则插入中间靠右的位置。若含有多个最长的区间，则选择最右的区间插入。 题解 这并不是一道找规律的题目。可以直接去模拟实现，那么然后快速找到需要的区间呢，我们可以考虑使用优先队列，我们将每个区间的长度以及左右边界作为节点入队，优先队列中的排序为第一个是长度，第二个是左边界。这样就能保证每次出队的区间是最长且最右的区间了，然后我们将区间分成两部分再入队。就可以模拟出数组了。 复杂度 时间复杂度 代码 #include <bits/st...

题意 给你，构造一组长度最短的数满足。 题解 因为 ，所以只要能写成的形式，就满足正确性，所以这组数最多也就3个数。如果和的各个二进制位上，没有一位是两个都是1的，即，那么按要求最短，这时候就可以把和合并成，输出和这两个数就可以了。否则，就输出，，三个数。还需特判若时只用输出一个数即可。 复杂度 时间复杂度 代码 #include <bits/stdc++.h> using namespace std; int main() { long long x,y; scanf("%lld%lld",&x,&y); if(x==y...

题意 给你个长度为的环形数组，每次可以选择一个数，将，并和删除。求最后剩下一个元素时的最大值是多少。 题解 首先合并一共可以进行次，从贪心的角度去想最终的数的最大值是个数的和。由于每次和并所选择的数是没有贡献的，那就要考虑要去选择的哪个没用的数。我们可以每次间隔一个来删除。因为中间的数是没有贡献，删除的(n-1)/2数是不相邻的才最优，那么留下的数一定存在两个数相邻，确定这两个相邻的数就能确定其他被删除的数，O(n)枚举一下这两个数即可。计算不相邻数的和可以对奇偶位置分别计算前缀和来做。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using name...