题意 给你一个数组，要求该数组的任意两个子数组都不同，子数组的定义是任意两个不同区间元素所构成的。例如的子数组有。所以对于该数组你可以修改数组中的元素值，使其满足牛牛的要求，求最小的修改次数。 题解 由于题目中的范围比要小，所以当时，根据鸽巢原理，个物品放入个篮子，必有一个篮子中的物品数量大于，所以此时是无解的。那么其他情况下我们只要把个元素都改成不同的值就可以了，因为题目中并没有要求任何更改，所以我们不需要去管他。那么我们只用统计一下数组中重复出现的元素的个数，答案就是把重复的元素更改即可。 复杂度 时间复杂度为 代码 #include<bits/stdc++.h> using ...

题意 给你一个，有，求最大的是多少。 题解 首先先分类讨论一下，若为偶数，那显然最大的为。那么若为质数，那么答案为，因为若，那么有，与是质数矛盾。考虑最后一种情况，为奇数。任何一个合数都可以拆成两个数的乘积的形式，即，且有一个数小于等于，那么我们从遍历到，找到第一个能整除的数即认为是，那么对应的即为最大的了。这个时候可以将拆为，这样能保证出来的最大公约数是最大的。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; int main() { int t; scanf("%d",&t); wh...

题意 给你一个序列，将其划分为几个子序列，要求每个子序列中的元素是不重复的。求最少可以把序列划分为多少个。 思路 由于这题并没有要求划分的具体方案也没有说需要子序列满足什么顺序。所以只用考虑不重复，那么根据贪心策略，我们只用考虑哪个元素出现次数是最多的，那么其出现次数就是最少的划分方案数。因为你必须将这重复最多的元素划分到不同的子序列中。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; const int N=1e5+5; int vis[N]; int main() { int n; scanf("%d...

题意 给你一个数，将其分为个数字的和，且用这个数字能组合出到的所有数字，求最小的。 题解 先说结论，最小的就是二进制下的位数。先考虑的二进制。任何一个数都是可以表示成这样的形式的。假设的二进制有位，那么若先将分解成和，对于第一部分可以表示的数，那么的数如何表示呢，其可以表示成和中的数组合相加构成。所以最少的至少为的二进制位数。 复杂度 时间复杂度为 代码 #include<bits/stdc++.h> using namespace std; int main() { int t; scanf("%d",&t); while(t--) { int n; ...

题意 给定一个字符串，求其循环左移过程中会产生多少个不同的字符串。 题解 由于字符串长度较小，所以我们只用模拟循环左移的过程，然后将新产生的字符串进行一个hash看看是否是新的字符串即可，C++可以使用map进行映射，python可以使用字典。除了暴力模拟，若字符串长度较长可以考虑分析一下。若字符串是全由一个字符组成的那么答案就是1，若字符串是由一段字符重复几次拼成的那么答案就是其重复的次数，非则答案就是字符串的长度。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; int main() { int t; scan...

题意 有根长度为的木头，表示对长度为的木头进行每米切割一次，例如木头会被切割成三段。现在进行的操作。操作完之后剩下有段木头，求原来的是多少。 题解 题面的中转换一下就可以变为，先解决第一个问题，这个求和如何快速求解，由于是取整操作，对于不同的值其取整的值可能是一样的，而且不同数的级别的的，因为一个数是由构成的，所以不同的数只会有级别个。所以在某个区间内的值是一样的。那么已知该区间的左端点为，如何求解右端点呢。由于的值是单调递减的，所以可以考虑用二分来查找右端点。 int Find(int n,int i) { int x=(n+i-1)/i; int l=i; int r=n; while(l...

题意 给你一棵树的中序遍历序列和层次遍历序列，判断这棵二叉树是不是完全二叉树。 题解 首先在于建树，首先若我们有了某棵子树的层次遍历序列，对于这棵子树来说肯定是这棵子树的根节点。那么我们获取到根节点后我们可以利用这个根节点通过中序遍历序列来获取这棵树左右子树的层次遍历序列。我们首先是知道这棵树左右子树在中序遍历序列中的区间范围的，然后我们遍历一开始的层序遍历序列，判断该节点是否在左子树中，若是加入左子树层次遍历序列，若不是我们让其加入右子树层次遍历序列，然后对左右子树重复上述过程就可以构建出一棵二叉树了。 对于一棵二叉树，判断其是否是完全二叉树，用BFS的方法即层次遍历的方法来判断，若遇到一个...

题意 有个选手和场比赛的结果，让你求编号为的选手可能的排名。 题解 场比赛的结果可以看作个偏序结构，可以构造一个有向图。那么可能在位置，就是对这个图进行拓扑排序，在拓扑排序中可能排在第几位。那么如果直接进行枚举所有可能的拓扑排序序列的话，时间复杂度是阶乘级别的，这样做肯定会超时。那么我们分析一下拓扑排序的性质。若某一个节点可以用来排序了，那么该点的入度肯定为0了。那么该点的最早能够被排序也需要对其有入度的节点进行排序完之后才能进行。也就是说若反向建图之后，点至少要排在，从点出发所能遍历的点的个数+1的位置。而最大排在哪里呢，就是正向建图后，-从出发所能遍历的节点个数。这相当于除了这部分子图之外...

题意 给你一个长度为的不重复序列，请你对这个序列重排使得用重排后的序列构造的二叉排序树是一棵平衡树。 题解 根据二叉排序树的性质，中序遍历二叉排序树是一个升序序列，为了让每棵子树尽量平衡，让每棵子树的根节点作为该子树中序遍历出的升序序列中的中间元素是较为优的做法。所以我们对于给定的序列可以先从小到大排序，然后一开始将元素作为根节点，然后中的元素作为左子树，中的元素作为右子树。而每个区间的中的中间元素都作为该子树的根，这样构建出来的二叉树能保证是平衡的。 复杂度 时间复杂度为 代码 #include<bits/stdc++.h> using namespace std; const ...

题意 给你和求的小数表示，其中若是循环小数，输出到第一个循环节为止。 题解 首先判断以下能否整除，若能整除直接输出即可。否则那么整数部分就是，那么我们怎么输出一个数的任意位小数呢。考虑模拟竖式除法，每次都是余数借十然后除以，这样就能输出到任意位的小数了，但是怎么寻找循环节呢，实际上小数部分的循环节可以认为有两个元素所控制，即每次的商和余数，若这次的商和余数在之前出现过了，那么也就说明下面开始都是循环部分了，那么我们就可以记录以下每次的商和余数。例如c++可以使用map来记录，python使用字典等。 时间复杂度 一个数倒数的循环节长度不会超过其本身，所以认为时间复杂度为 代码 #include...

题意 给定一棵个节点的树，树根为，树的每条边有一个权值，有次询问，每次询问求节点到之间路径上边权的异或和。 思路 由于询问较多，每次都dfs一遍两点之间的路径然后求其异或和肯定是不行的，那么考虑记录每个节点到根节点的异或值为，表示为节点到的路径异或值。那么两个节点之间的路径我们可以考虑为绕个远路，例如从出发先到节点，然后再从到，由于我们处理过和所以这两段的异或值都有了，那么到的异或值，实际上绕远路的公共部分去掉就行了，而和中都包含了公共部分，根据异或的性质，一个值异或了两遍等于没异或。所以就是到路径的异或值。所以我们可以先跑一遍DFS求出根节点到每个节点的异或值存在数组中，后续询问就可以的解决...

题意 其中表示向上取整。求第个斐波那契数对取模。 思路 首先若是一个常数那就是一个简单的矩阵快速幂题目了。但是由于的值在不断变化所以并不好直接去套用矩阵快速幂。但是由于在某一段的区间之内其值是不变化的，而且这样的区间大概有只有个。那么我们就可以通过这个角度来加速矩阵快速幂了。假设当前区间的开始值为，结束值为，那么构建的矩阵就是 我们只要每次记录下新一段的和就可以利用其求解出下一段的值。那么如何去求的值呢。由于的值是递减的，所以我们可以利用二分去找第一个大于当前值的下标。 int Find(int n,int i) { int x=ceil(1.0*n/i); int l=i; int r=n;...

题意 给你和，求到之间所有数字的异或。 题解 首先区间之间的异或怎么计算呢，若知道和之间的异或值，那么最后的答案就是。那么如何计算的异或值呢，我们可以打个表先来看看。 1 1 2 3 3 0 4 4 5 1 6 7 7 0 8 8 9 1 10 11 11 0 12 12 13 1 14 15 15 0 16 16 17 1 18 19 19 0 20 20会发现规律实际上很明显，以4个一组即，所以对于给定的我们对其取模4就知道的异或值了，后续就好做了。 复杂度 时间复杂度空间复杂度 代码 class Solution { public: /** * * @param l long长整型 * ...

题意 ，给你，求 题解 我们先打表看看这个函数的信息 1 1 2 3 3 1 4 7 5 1 6 3 7 1 8 15 9 1 10 3 11 1 12 7 13 1 14 3 15 1观察发现的值都是二进制下都是1的情况。若我们考虑右移操作和除二，那么可以得到 ，那么对于求和序列中奇数都是1，我们对偶数部分进行提取出个2的操作可以得到。  即有如下递推式。 这样的话也就是说能够递归在的级别来求解答案了。 复杂度 时间复杂度空间复杂度 代码 python # # # @param n int整型 # @return long长整型 # class Solution: def Sum(self ...