题意 给你一个区间，问从中挑出两个数字进行按位与，求最大的结果是什么。 题解 首先若时，答案只能是，注意答案不一定为。若，那么当为奇数时其二进制下会比多出个，所以必有，所以输出即可。若为偶数时，为奇数的情况，所以输出即可。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; int main() { int t; scanf("%d",&t); while(t--) { long long l,r; scanf("%lld%lld",&l,&r); if(...

题意 给你一个长度为的数组，你可以进行次操作，每次操作可以对一个数减一，问进行次之后，从小到大排序使得中位数最小是多少。 题解 我们首先先从小到大排序，然后从中间元素向遍历。由于我们是想要中位数尽量小一些，所以我们需要让中位数减小到和前一个数相等的大小，然后要继续减少的话，需要中位数和前一个数一起减少到前前一个数。所以减少的话是一段一起减少。我们每次只要找到这个段有多少长然后所有的数减到和再前面一个数一样即可。若不能够一起减少的话说明中位数也只能这么小了。注意有可能会爆。 复杂度 时间复杂度##代码 #include<bits/stdc++.h> using namespace s...

题意 给你一个有个不同元素的序列，你可以选着一些子序列对子序列内部进行排序，排序后将数放回所取的子序列对应位置，问最多可以去多少个子序列完成排序后使得整个序列递减。 题解 考虑排完序后位置上的数应该是。所以对于位置来说是一定要把加入到这个子序列中的，那么我们找到这个数所在的位置记为，那么我们还需要把这个数加入到子序列中，所以一直重复这个过程，最终会形成一个环，即一组子序列。那么我们做几次这样的，也就表示了最多可以划分多少个子序列。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; const int N=1e5+5;...

题意 给你一个长度为的数组，里面是的元素，但是可能有重复的元素，要求你将改数组改成一个全排列，每次可以选择一个数字将其替换成中的某个数。要求次数尽量小，并且字典序尽量大。 题解 我们先遍历一遍数组将中没有出现过的数按从小到大的顺序入栈，那么栈顶元素就是最大的那个，然后我们再遍历一遍数组，遇到某个元素出现次数大于时，我们判断其大小和栈顶元素哪个大，若栈顶元素大就将其替换成栈顶元素，且原数的个数减一。反之我们可以保留一次，每个数最多保留一次，否则就必须要替换了。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; cons...

题意 给你一个长度为的序列，以的第一个元素开始从左至右从序列中选出递减的序列，并将其从中删除，再重复这个过程，直到序列为空，输出每次挑选的递减序列。 题解 首先我们可以知道的是，每个递减序列的最后一个值它是递增的。例如有，可以得到 5 1 4 2 3每一个序列的最后一个元素是递增的。若某个序列的末尾值加入时导致其不递增了，那么该值应该放到前面某个序列中去。故我们可以创建一个数组来存每个序列的最后一个值，那么每次有一个新的数，我们可以在这个数组中二分来找到他应该在的位置，那么对其进行替换，并且加入到那个序列的末尾中，若二分找不到比起大的，那么就创建一个新的序列。 复杂度 时间复杂度 代码 #in...

题意 有个不同的数组，这个数组的值为，每次将一个数组加入集合中，并对集合求一次函数的值，函数指，集合中未出现的从开始的数。输出次函数的值。 题解 这题要是正着来做，每次合并都求一次数组的话，极端情况下每个数组长度为，那么复杂度就是。所以我们可以离线处理，用逆向思维，首先当所有的数组被加入到集合中时，集合为，那么函数的值就是，逆着来相当于从的数组中删数，所以我们遍历最后一个数组来得到其中的最小值和哪个小，倒数第二组的答案就是这个最小值了，我们重复这个过程就可以得到所有的函数的值了。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespac...

题意 有两个长度为的二进制数,，这里表示按位与，问在中交换一次任意两位上的数字，会产生多少中新的。 题解 由于是对中的两位进行交换，且进行的是按位与操作，什么情况下会导致与的结果不同呢，当 a 0 b 1为这种情况时将的和某一个交换，会使结果不同。或 a 1 b 1为这种情况时将的和某一个交换，也会使结果不同。 那就得考虑贡献的问题了，如何不重复。先预处理出中的所有的个数记为。考虑遇到这种情况时，每一个这里的都有种交换方法，我们令答案加上。那遇到这种情况时我们可以用替换掉来使答案不同，但是我们前面里面已经将这个和这里的交换过了，所以我们这里的应该与所有中的进行交换，所以我们还需要预处理一下的个...

题意 有三个长度为的序列，从三个中各选一个元素相乘等于的组合有多少种。 题解 三重循环的暴力来找的话复杂度为是肯定超时的。那我们可以这样先暴力记录下两个序列各选一个元素相乘的结果，然后我们遍历序列，去之前处理的结果中去找有多少个的值加入到答案中即可。 复杂度  代码 #include<bits/stdc++.h> using namespace std; const int N=1e3+5; int a[N]; int b[N]; int c[N]; map<long long,long long>vis; int main() { int n,k; scanf(&qu...

题意 给你一个的矩阵，每个位置上的元素为或，问你从左上角走到右下角，只能向下或向右走，且路程上的数之积为的路径有多少条呢。 题解 由于，一共有种选择方法，直接的话肯定会超时的，那么折半搜索，先做一遍从搜索到中间值，即的位置，然后记录中点的路径之积以及该积的路径条数，然后我们再从搜索回去，搜索回去的路径之积记为，那么我们去查第一次得到的有多少条，加入答案即可，注意的时中间点的元素是会被重复计算一次的。 复杂度 时间复杂度##代码 #include<bits/stdc++.h> using namespace std; const int N=20+10; int a[N][N]; m...

题意 给定一个长度为整数，你可以交换中的相邻两个数字，但是这两个数字的奇偶性需要不同。问该数的最大值能变成什么呢，对取模。 题解 由于只能交换相邻且奇偶性不同的两个数字，所以所有奇数和奇数之间的相对位置是不变的，且所有偶数和偶数之间的位置也是不变的，所有，我们可以用两个队列一个存入所有的奇数一个存入所有的偶数，我们比较两个队列的队头元素谁大将其输出即可。 复杂度 时间复杂度##代码 #include<bits/stdc++.h> using namespace std; const int mod=1e9+7; int main() { int t; scanf("%d&...

题意 给你一个长度为的序列，可以进行次操作，每次选择一个数对其进行左移操作。问结束后的最大值是多少。 题解 由于异或操作不会使二进制下的位进位，所以若有一位下的在特别高位，别的就异或不到该位了，左移操作就是将二进制位往高位提，所以我们只要将其中的一个数操作次即可，但是对哪个数进行次操作呢。我们可以去一个异或的前缀和和后缀和，然后我们就可以的求出当前这个数左移次的最后答案了，即pre[i-1]^(a[i]<<k)^suf[i+1]。我们遍历一遍求出最大值即可。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std...

题意 给你一个长度为的次幂的串，判断该串是还是，判断其为的方法如下：  其长度为时，其为时为。 其长度大于时，串分为前后长度相等的两部分，且满足如下情况时为：第一部分都为且第二部分都为时为。第一部分为且第二部分为时，其为。第一部分都为且第二部分为时，其为。第一部分为，第二部分都为时，其为。  题解 考虑分治去做，时，若判断串的长度为时，若为则返回，否则为。然后对于长度大于的串，我们先判断其是否是第一部分都是，且第二部分为，若满足直接返回，然后我们递归下去判断两部分的串是否是。然后我们按照规则进行组合来判断是否即可。 复杂度 时间复杂度 代码 #include<bits/stdc++.h&...

题意 给你两棵二叉树和，从和中各选一个节点，并在他们之间添加一条边得到新树，问可能的最长直径和最短直径之差是多少。 题解 首先我们分别求出树和树的直径。首先新树的最长直径怎么连接可以得到呢，我们只用将树和树直径两端各选一个节点相连，那么的直径就是。那么最短直径呢，我们可以取树直径中点和树直径的中点在他们之间连接一条边，即，那么我们就可以得到两者之差了，。如何求一棵树的直径我们做两遍，首先随意取一个点出发，从其达到的最远点就肯定是直径的一端了，我们在以该端为起点再做一次到达最远点的路径就是直径了。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using ...

题意 给你一棵有个节点的树，你可以在树上删掉两条边，使得树变为三棵子树，且要求三棵子树的节点个数要相同。问能否实现，能输出,否则输出。 题解 首先先判断整颗树的节点个数能否被三整除，若不行肯定无法划分为三个节点树相同的子树。然后我们对这棵树进行，来计算出每个节点作为根时该子树的节点个数，记为。再遍历数组找是否有子树的节点数量为，若有将该子树删除，在该子树上的节点的赋值为，再从向上寻找祖先，将。然后我们再遍历一次数组查看是否还有子树的大小为，有则说明可以实现划分输出。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; ...