题意 给你一个字符串，这个字符串是在键故障的情况下打出来的求原先正确的字符串，键一直处于锁定状态，当按下时反而为解锁状态，求原先的串。 题解 直接考虑用映射关系即可，开两个字符串记录按下时的大写字母，另一个记录下松开时的小写字母，用或者python等字典结构都可以完成映射，把大写对应小写的映射加入字典，也需要把小写对应大写的映射加入字典。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; map<char,char>vis; string a="~!@#$%^&*()_+QWERTYUI...

题意 一层for循环复杂度是，两层就是，现在有行，字符表示一个循环的开始，表示一个循环的结束。求给定的字符复杂度是多少。 题解 可以用栈匹配的考虑还计算复杂度，用表示一个循环这种情况下复杂度也就只有，所以我们可以遇到的时候就压栈一个元素，否则就弹栈一个元素，在这个过程中，栈的大小的最大值即为最大的复杂度。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; string s; int main() { int n; scanf("%d",&n); int ans=0; int cnt=0; ...

题意 给你一个有个不同元素的数组，你可以通过交换相邻元素的值对数组进行改变，但是数组中有个位置上的元素是不能进行主动交换的，即若存在，不能交换。问当前这个数组能否变为从大到小的顺序排列呢。 题解 首先分析到当存在一个点不能进行交换时，实际上就将数组分成了两部分，分界点的左边的元素是到不了分界点右边的，那么也就是抽象成为以个位置分成了个区间，要让数组整体从大到小排序，也就是所对每个区间内的排完序后数组能实现整体有序，那么现在分析两个相邻区间需要满足什么，也就是左区间中的最小值要大于右区间中的最大值，且每个分界点都要满足那么整体就能实现从大到小排序了。我们可以预处理出前缀的最小值和后缀的最大值，然...

题意 给你一棵树，树上的节点的权值为，给你这棵树每个节点的初始权值，然后希望变化到目标权值，变化方法是每次可以选择一个节点，将其的权值从变为，或从变为，同时其的子树也会发生意义的变化。问最少需要多少次操作可以达成目标。 题解 首先发现儿子节点的改变对于父亲节点来说是没有影响的，并且左右兄弟之间属于两颗不同的子树，所以左右兄弟之间也是不影响的。那么我们就可以从根节点开始遍历判断每个节点是否需要变化，由于其父节点以及父节点的祖先若存在操作次数是影响当前节点的，我们可以在的参数中记录一个当前节点的祖先操作了多少次，若操作次数为偶数次，则当前节点的权值还为初始值，否则变为另一个值，然后我们再判断是否需...

题意 给你一个二进制整数，你可以选择相邻的两位数字进行交换，最多交换次，能得到的最大的数是多少呢，输出10进制下的该数，对取模。 题解 我们只需要贪心去将在后面的往前提即可。我们模拟交换这个过程，由于把这个这个往前提几个位置就是进行交换多少次，我们从第一个出现的位置之后来找，将往前提到这之前，这个时候这个的位置就往后移动一位了。当剩余的移动次数小于时，为了最大我们往前移动剩下次数即可。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; const int mod=1e9+7; string a; int main()...

题解 给你一个有个不同元素的数组，要是数组中存在时可以消除这里两个中的任意一个元素，然后数组按顺序拼接。问最后能否只剩下一个元素。 题解 首先先说结论当时输出，否则输出。由于所有数都不同，那么存在一个数在一个区间内都是最大的，那么我们可以从这个最大的数开始删除其一侧的所有数，当删到最后一个时我们删除该最大的数就可以了，那么我们一定能做到使得最后的数里面为最大的情况。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; const int N=1e6+5; int a[N]; int main() { int t; sc...

题意 给你一个字符串，你可以在其中翻转一个区间，然后求该序列中最长的非降子序列的长度。 题解 由于这里只有和两个数，并且求的是子序列。先考虑和组成的非降子序列是什么形式的，有三种形式，即都是或先后或都是三种。那么在考虑存在翻转时怎么样翻转能够使得贡献最大。实际上这情况下，我们将中间的进行翻转能使答案的贡献最大，这个时候整体的长度和这种形式的长度是一致的。那么我们需要记录,,,四种情况下出现的最多值即可。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; const int N=1e6+5; char str[N]; ...

题意 汉明距离为两个二进制数和，在进行按位异或后，其结果中的个数，记作。现在要求 题意 考虑将二进制写出观察一下规律。 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111我们可以从每一位上进行分析，从第一位上分析，每个数和前一个数的异或值都是有贡献的，也就是说贡献为，然后在看第二位，第二位上的和的变化规律是，也就是每四个数只有两个有贡献。比起个位的贡献就就只有，同理第三位的贡献只有。这样我们就可以得到每一位上的贡献了。 复杂度 时间复杂度 代码 #include<bits/stdc...

题意 给你一个有个数的数组，每次对这个数组进行划分，在当前的数组中找出最大值和最小值，从数组中找出小于等于和大于(向下去整)的两部分，在对每个部分继续如此的操作，当某个数组无法划分出两个新数组时停止该数组的划分，求这个过程中所有产生的新数组的和的和是多少。 题解 首先由于每次找的是小于等于中位数和大于中位数的两部分，所以数组的初始顺序实际上是没有影响的，所以我们可以对数组进行从小到大排序。然后这样对于一个数组找出它的最大值和最小值就是的了，那么关于数组划分点我们可以利用二分来解决。每次通过二分找到数组分割点后，我们进行递归操作，这样就能完成整个过程的划分了，还有一个问题就是求和，对于一个被划分...

题意 给你一个字符串，从开始到，每次向前选个字符进行翻转，求对于不同的来说，的结果中字典序最大的是多少。 题解 由于直接模拟的话复杂度最大能到，所以不太现实，所以进行打表观察一下结果。 str=abcdefg |str|=7 k=1 -> abcdefg k=2 -> gabcdef k=3 -> gfabcde k=4 -> efgabcd k=5 -> gfedabc k=6 -> cdefgab k=7 -> gfedcba发现当长度为奇数时，也为奇数时，是将后翻转后提到前面去，而当为偶数时，是将后个元素提到前面去。 str=abcdefgh |...

题意 给你个字符串，要求穿过这个字符串，初始能量为，当走到时，能量加一，反之能量减一，当能量小于时，回到初始原点，并且初始能量加一。问当穿过字符串时总的步数是多少。 题解 答案实际上就是每次回到原点的位置的累加和，那么我们只要知道什么时候会回到原点即可在的复杂度完成计数，当当前能量小于的时候我们不需要真的回到原点，因为每次回去的时候初始能量会加一，相当于我们可以从原点走到当前这个位置，且能量为0，开始闯关。当能量小于时答案加上所在的位置，然后能量变为0重新计数即可。 复杂度 时间复杂度 代码 #include <bits/stdc++.h> using namespace std;...

题意 给你一个队列和集合，和中各有个元素，这个元素为个以及被随机分配到队列和集合中。每次可以从队列出队一个数字然后将其加入集合中，再从集合中取出一个数入队，问将队列中的元素从队首到队尾变为需要的最小操作次数。 题解 首先操作的上界是次，将队列中都变为，然后按从大到小的顺序入队即可。那么此外首先考虑特殊情况，当队列中一开始的情况是，集合中的元素为和时，这样只需要再次操作即可实现。那么别的情况下怎么操作呢，例如，为时，的初始位置在，但其的目标位置在，所以他必须先完成两次出队之后，再经过两次入队才能到达目标位置。同理的初始位置在，目标位置在，它需要出队次再入队次才可以达到目标。所以对于数字来说它的必...

题意 给你三个整数，表示一开始有个位置，其中个位置是做人的，并给出这个人的位置。任意两个人之间应该空出个位置落座。问还可以让多少个人坐呢。 题解 模拟即可，我们首先记录两个被占座位置之间有多少个空位呢，由于两个人的座位之间要空出个位置，所以假设若当前有个空位在已经坐人的位置之前要空出个位置，所以还剩下个位置可以选择。那么每次选择的是一个坐人的以及个空位置，所以就是个是可以插入的。这样从遍历到即可。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; const int N=2e5+5; int vis[N]; int ...

题意 给你一个由组成的字符串，你可以将其中的替换成，或将替换成，求让字符串中的数量等于的数量，且操作次数最小时的串，若操作次数最小的串不唯一要字典序最小的串。 题解 我们只用贪心的去替换即可，分成两种情况，但的数量大于时，我们就从字符串末尾往前替换个为。若的数量大于时，则从字符串从头到尾替换个为。 复杂度 时间复杂度 代码 #include <bits/stdc++.h> using namespace std; const int N=2e5+5; char str[N]; int main() { scanf("%s",str); int n=strlen(...