题意 给你一个长度为的数组，可以将其一段区间进行反转，问数组中所有下标为奇数的元素的和最大是多少。 题解 首先若反转的区间长度为奇数那么奇偶的位置实际上没有影响，所以若反转的长度为奇数那么没有贡献。则当考虑反转长度为偶数的区间，只需要判断哪一个区间内的偶数位置的数比奇数位置的数大即可，我们将偶数位置的数和前面一个奇数位置的数做差，或者是将奇数位置和他前面的偶数位置的数做差，并对这两个做差得到的区间求最大子段和即可。这里得到的就是反转区间所能得到的最大贡献，加上原先的奇数和，就是最后的答案了。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using na...

题意 给你一个长度为的数组，由构造出一个的矩阵，其中，问中有多少个子矩阵的和为。 题解 考虑这个子矩阵的和为什么有： 。若我们预处理出数组的前缀和那么上式就可以表示为： 由于的大小为，我们可以统计出所有的区间和的个数。然后再跑一遍每个区间的和，那么答案就是加上当前枚举的和的个数和的个数。当时还需特判一下。若，那么会使得的第行和第列的取值都是，一行会产生个满足条件的子矩阵，而第行和第列同时为的话，就会产生个子矩阵，不过需要注意一下，这个格子被计算了两次，所以需要减去。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; ...

题意 给你一个长度为且各个元素不同的数组，问将数组，划分为个区间，对每个区间内部进行从大到小排序，且让整体是从大到小有序的。问最大的是多少。 题解 由于序列中的每个数都不同，可以将元素映射到。排序完之后就是的形式。我们对于每个数字可以将其现在的位置与排序后所在的位置看成一段区间，也就是说若要到他最终的位置，必须跨越这段区间，所以每个数字可以有一段区间。若两段区间之间有交叉也就是排序时两个区间必须合并。所以我们可以将区间按左端点进行排序之后从头到尾合并一下，最后剩下几个不重叠的区间也就是要找的最大的。 复杂度 排序复杂度合并时间复杂度 代码 c++ const int N=1e5+5; stru...

题意 给你一个长度为的数组，你可以将其重排，使重排结果中对于任意的有。任意输出一个重排结果即可。 题解 由于要重排结果，使得没有两个下标减去其数字是相等的。那么考虑对数组从大到小排序后输出。证明如下：若有则有两边同时减去，有我们对比一下和的大小，会发现，所以有。即两边乘上一个负号有 所以肯定能保证所以只用从大到小重排即可。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; const int N=1e2+5; int a[N]; int main(){ int t,n,i; scanf("%d",...

题意 给你一个长度为的数组。每次可以做一个操作，选择数组中的一个数，对其整除二。求让数组中有个相同的数的最少操作次数。 题解 由于是肯定可以把数组中变为个相同的数的。我们可以开两个数组，一个数组记录每个数现在有的个数，另一个数组表示获取到下标数这么多的个数需要的操作次数。若某个数的个数大于等于个了，那么记录下让其有个的操作次数和原有答案哪个小。剩下的就是暴力了，由于是除二操作，所以每个数的操作次数不超过次。所以我们对每个数将其依次除二直到一，并把其除二的结果表示的记录个数的数组加一，表示次数的数组加上变为这个数的除二次数。然后对数组中的每个数遍历一遍就可以了。 复杂度 时间复杂度 代码 #in...

题意 给你一个长度为的整数，可以删除中的任意位置上的数字(至少删除一个)，删除后按照顺序拼接起来成为新数字。求所有可能数字的和。 题解 可以考虑，表示从所可能的数字的和，那么考虑的转移方程。即第个数字是否选择。若选择的话，由于我们是从高位遍历到低位的，那么若取了这表示原先的每个可能数字都增加了倍，然后个位上增加的是，那么原先有多少个数字的可能呢，由于的数字都存在可选和可不选两种情况，所以可能的数就为个，也就是说在个数字每个数字增大倍并且在个位上加上一个。这是选择的情况，若不选择，那么答案还是，所以可以的到转移方程为。遍历一遍即可，但由于必须至少选择一个数进行删除，所以要把从答案里面减去。 复杂...

题意 给你一个长度为的整数，必须删除其中一段连续的数字，剩下的部分按顺序进行拼接形成一个新的数字，求所有可能的数字的和。 题解 考虑中每个数字的贡献，例如考虑的贡献，当删除的连续数字是在之后的即。那么若删除的长度为，可以有种不同的删法，那么的贡献为。若删除的长度为，同理有种不同的删法。所有贡献为。故在之后的删除可以表示为。那么在考虑在之前删除数字，那么到末尾的长度一直不变，所有总的贡献是一样的有。最后的答案就是统计每个数字的贡献然后加起来即可，可以用快速幂先预处理一下的次幂之和。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespac...

题意 汉明距离为两个二进制数异或后剩下的个数。记汉明距离为。给你两个长度为的二进制数，求。 题解 其实就是把串从右到左平移每次和相同长度的部分进行异或后统计一的个数然后相加。由于可以看作是平移操作，对于串中每一个，我们可以考虑其在串中的贡献。由于可以看作平移操作，所以中的某一个，其实在中是都有扫过的。我们可以记录一下中的个数的前缀和，那么这一段的个数就是长度减去前缀和。对于串中的的贡献，我们就看这个在串中扫过了哪些位置，把串中的这一段的个数加到答案里就可以了。对串中的也同样处理。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespac...

题意 给你一棵树，树中每个节点的类型可能不同。在这棵树中找到一个节点作为根，当其为根时，其每棵子树上的节点类型都是一样的。 题解 从结果的树上进行考虑，若是有解的，那么最终的根节点是满足一定性质的。若与根相连的有棵子树，且每棵子树的根的类型和的类型也是不同的。那么就会满足的度数和一条边两端节点类型不同的数量是相等的。所以说我们只需要统计一下每条边其左右两端的节点类型不同的数量以及，这些点的度数。我们遍历一遍，若找到某个节点的度数和节点类型不同的数量相等，那么其就可以作为根了。 复杂度 时间复杂度为 代码 #include<bits/stdc++.h> using namespace...

不会数论分块的小伙看过来。由于最大能到，可以明确不同的值只有级别个，所以中的在某一个区间之内，向上取整的值都是一样的，那么我们怎么去确定右区间呢。实际上我们可以用二分来确定右区间。二分的左右边界，若当前要除的值为，那么左边界就是，右边界为，若，说明右边界大了即，否则。找了向上取整的右边界，我们就可以快速的求和了。 复杂度 时间复杂度为 代码 class Solution { public: /** * * @param n int整型 * @return long长整型 */ int Find(int n,int i) { int x=ceil(1.0*n/i); int l=i; int r...

题意 给你一个字符串，找到最长的子串，其由连续的一段和连续的一段拼成，求这样子串的最长长度。 题解 我们可以用一个数组来记录一下串中每段连续的长度。那么我们只需要遍历一遍组数来找相邻连续片段中较小值即为最后子串的其中一般，所有我们可以遍历一遍数组，最后的长度乘2即可。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; const int N=1e5+5; int a[N]; char s[N]; int main() { scanf("%s",&s); int n=strlen(s); f...

题意 给你一棵树的广度优先搜索序列，且广搜时，以该节点儿子编号从小到大入队。问由该广度优先搜索序列得到的可能树中高度最低的树是多少。 题解 由于广度优先搜索的序列是按节点编号从小到大入队的。所以在给定的序列用一段连续递增的区间都视为是一个父节点的儿子这样贪心的来是最优的。所以只要看有多少个非递增的序列就说明深度是多少了。 复杂度 时间复杂度 代码 #include <bits/stdc++.h> using namespace std; const int N=1e5+5; int a[N],b[N]; int main() { int n; scanf("%d&quot...

题意 给你个数字，的范围为，每种数字至少使用一次，问能构成多少个不同的合法整数。 题解 可以用dfs来搜。首先将每个数字出现的次数存下来，然后将出现过的数字依次遍历。对于每个要使用的数字我们可以套用组合数组的公式。例如 所能平凑成不同的数字为。这相当于先从六个位置中任选两个地方放然后再任选一个放，减去的是含有前导零的情况，即第一个地方已经放了。 代码 #include<bits/stdc++.h> using namespace std; int num[10]; long long fac[20]; int tmp[10]; long long ans = 0; void dfs...

题意 给你一个长度为的序列，问从有多少个四元组满足最小。 题解 对序列进行排序后，进行分类讨论。若前四个数为，那么有若这说明四元组的个数为重复的个数，即若，这说明四元组的个数为从中取两个数的方法数，即若，这说明四元组的个数为从中取三个数的方法数，即若，这说明四元组的个数为从中取四个数的方法数，即 复杂度 时间复杂度为 代码 #include<bits/stdc++.h> using namespace std; const int N=1e4+5; int a[N]; map<int,long long>vis; int main() { int n; scanf(&q...