题意 给你一个长度为的数组，问你这个数组中，有多少个区间，其区间内的元素和不等于。 题解 直接求有多少个区间和不等于，是比较难做的。但是我们去求有多少个区间，其区间和为是比较好做的。所以我们可以先求出来区间和为的区间有多少个，然后总的区间个数一减就是最终答案了，总的区间个数为。我们求区间和为的个数，我们可以求前缀和，并把前缀和存到map中去。若在求前缀和的过程中出现当前的前缀和在之前出现过，这说明当前到之前出现过的这段区间内的数字之和为，所以我们可以在map中查询前面是否出现过该数，将该数个数加入到答案中即可。 复杂度 时间复杂度 代码 #include<bits/stdc++.h&gt...

题意 给你一个整数，你可以对进行重排，使得其变小但是不能出现前导零，并且重排之后的结果不能小于。问最小的是多少呢。 题解 首先若的位数比大，那么我们只要将从小到大排序即可，且不出现前导零这样就能得到最小且比大的数。剩下就是考虑和位数相等时，我们可以贪心的处理中的每一位，我们去找到在这一位最小情况下比大的第一个数是什么。我们从这个数的第一位开始处理，对于当前位来说要找到当前位最小且整体大的数，我们可以将从这一位开始到后面的所有数从小到大排序，然后将下一位到最后一位的数从大到小排序，这样可能其还是比小，剩下就是要以最小的步数找到第一个比大的数，这个时候可以考虑next_permutation函数，...

题意 给你两个长度为的字符串，你每次操作必须在两个串中选择一个区间，两个串中的这个区间大小要相同，两个串中区间内的数进行反转。问最后两个串能否相等。 题解 首先若两个串之间和的个数不同那么他们肯定不能变成一样。然后因为区间大小没有限制，所以我们可以考虑长度为的区间，那等于交换相连两个数字。那么我们可以先只考虑第一个串，我们将第一个串排序变为的形式，然后第二个串随意变换。这样我们就得到了第一个串有序，第二个串无序的情况。然后我们可以在第一个串中选择或者的区间进行反转。然后也将第二个串变成有序，这样肯定能保证两个串相等。也就是在两个串和个数一样时是肯定可以相等的。但是存在一种情况就是两个串长度为时...

题意 给你一个序列所有元素的和，以及每个的值，问你将原序列恢复出来。 题解 我们可以求一下前缀和会发现前缀和就变成 那么我们把每个前缀和求个和就会得到，前面可以再拿个出来就会有。所以我们就可以得到的值了，那么剩下每个的值都可以恢复了。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; const int N=1e5+5; int a[N]; int b[N]; int main() { int t; scanf("%d", &t); while(t--) {...

题意 给你一个长度为的排列，让你把这个数组变成从小到大排列，你可以每次选择一个数字将其和前面一个数字进行交换，其条件是必须前一个比现在的小，该操作会一直进行下去直到前一个比当前数大。问最少选择多少个数字。 题解 我们可以贪心的去想，对于当前这个数来说若后面的数比他大的话，后面的数一定会向前移动的，那就等于后面这个数肯定是有被选择的，那我们可以交换当前这个数和后面数的位置以及答案加一。然后由于是当前数和后面的数交换，实际上后面的数换到前面来前面的数据我们以及处理过了，就可以管用管了，继续去找下一个数就可以了。这样遍历下来只要发现后面的数比当前数大就交换，并答案加一，遍历完就是最终要选的数的个数了...

题意 转化一下题意就是让你求区间，这里每个区间内出现次数为偶数的数，将这些数进行异或后整体的求和，即。 题解 首先可以考虑一下求一个区间之内出现次数为偶数次的数的异或值怎么求呢，我们知道，整个区间异或的值等于这个区间内出现次数为奇数的值的数异或的值，若我们有一个这个区间内所有出现过的数的异或值的话，那么出现次数为偶数的数的异或值就是区间异或值异或上所有出现过数的异或值。所以我们在遍历数组的时候可以看每一个数是否出现过了，然后开一个遍历存所以出现过的数，再有一个遍历记录前缀和的异或值。每次答案加上这两个值的异或即可。 复杂度 时间复杂度 代码 #include<bits/stdc++.h&...

题意 给你两个整数，让你将两个整数变为相等，其方法是每次可以选择一个数将其减去。初始为，每进行一次操作，的值加一。求最小操作次数，以及最终和的值。 题解 令和中，为较小值，若把和看作一个整体，即，若考虑进行了次操作，总的减少的数量就是。那么要求最后两个数字相等，所以即满足。但是由于和比较大，我们不可能去遍历的找到，那么考虑最终的结果为。由于一直在做减法操作，所以最终的结果肯定是小于等于的，那么我们就可以得到不等式。转化一下就变成了。又会有。所以就有。就能够大幅度减少能的范围，我们在的基础上向后找一个的结果即可。 复杂度 时间复杂度 代码 #include<bits/stdc++.h&gt...

题意 给你一个问你自增到什么数时，其个位上数字之和为呢。 题解 首先先考虑一开始的数位和的时候，这个时候我们只要贪心的去将最后一位变成，然后模拟进位来做就好了，这样得到的数肯定是这种格式的，当先增一位后将其变为时，会大于的话，那么我们将最高位加上即可。另一种情况，当时，我们可以将最后一个不为的数置零，然后将其前一位加一。这时候还需要考虑进位，所以不推荐转化为字符串来做。若这样处理之后其时由转到了第一种情况。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; int main() { int t; sc...

题意 给你一个长度为的串，将该串分为两部分，要求前一个部分的串是后一个部分的子串，且前一个部分的长度尽量长。 题解 这题可以直接考虑二分前缀的长度，利用string函数划分子串的函数，和find函数，可以很快的判断是否合法。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; string str; bool f(int len) { string s1=str.substr(0,len); string s2=str.substr(len); if(s2.find(s1)!=string::n...

题意 给你一个由组成的长度为的字符串。问该串中没出现过的子串中所代表的整数最小值是多少。例如，，其中没有出现过的最小整数为。 题解 如果要保证每一个数都在串中出现，那么该串最长会长这样，由于题目给的串长度只有，所以，所以没出现的过的数其长度最多为。我们可以把所有长度为的子串存起来，然后看那个数字没出现过，这个时候就可以用整数哈希了，由于数字里面没有出，我们可以用进制来哈希，进制下表示串中的。我们直接去暴力去找那个数字没出现过即可。##复杂度时间复杂度为 代码 #include<bits/stdc++.h> using namespace std; const int N=1e5+5...

题意 代数正规型ANF可以用来描述一个真值表，其统一格式为 其中这里的+表示异或操作，表示两个变量按位与操作。现在给你真值表，请你将这个ANF输出出来。 题解 这题按照题意进行模拟即可，由于，所以系数最多只有16个，我们可以利用dfs或者利用二进制枚举子集去枚举的状态为0还是1。若某次枚举能让整个真值表符合，那么就说明找到了正确的系数。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; const int N=25; int y[N]; int a[N]; int n; map<int,string>vi...

题意 给你一个区间，问你区间之内有多少个数的二进制下的的个数为。 题解 考虑求区间的问题都可以用容斥来简化，如表示中有多少个数的二进制上的个数为的。那么题目就变成了。那么我们考虑如何求中有多少个数的二进制上的个数为。例如。那么我们可以转化一下的区间，将其分解为几个区间： 枚举这个区间中每个区间中有多少个数二进制下的个数为，是和等价的。那么对于每个区间来说枚举就变得简单了，先看第一个区间，在这个区间中我们要挑选比小的并且二进制上只有个的数就是在五个空位上选三个填上，也就是。 再考虑第二个区间，由于首先要大于等于，所以高位上的第一个是必须选的，剩下就只有个需要去填，由于要小于等于，所以这个只能在...

题意 给你一个整数，你可以进行次操作，每次操作可以选择两个相邻的数字然后交换他们的位置，问进行完次之后，这个数最小能变成多少呢，数不能有前导零。 题解 由于，也就是说最多位数字，或等于。那么我们其实可以暴力去枚举所有的可能的最小数字，组合为种，我们不去枚举数字而是去枚举位置下标，即枚举排列。那么我们要去验证一下该排列是否是合法的，也就是要达成这个排列的交换次数是否小于呢，对于来说是不需要任何交换的(这里为下标)，那么将其变为时需要交换的次数是多少次呢，实际上就是该排列的逆序数的个数，交换一次会产生一个逆序数。所以我们对于一个排列是否合法，只要看其逆序数是否小于等于即可，还有一点是该数不能有前导...

题意 给你字符串的生成规则，问你第位上的个数。生成规则如下： 这里表示将的值取反，即中的变为，变为。 题解 首先我们可以得到的长度为，因为长度是递推下去就可以得到了。然后因为取反的性质两次取反等于没取反，稍微打一下表会会发现和(为奇数)中的个数是一样多的。我们只把奇数部分打印出来可以得到 1: 1 5: 1011101 21: 1011101010111011101110101011101 85: 1011101010111011101110101011101010111010101110111011101010111011101110101011101110111010101110101...