题解： 考察点： 数学，打表找规律 易错点： 注意最好把和都开成long long类型，因为在计算的过程中有可能会爆 解法：打表找规律 这题第一眼看上去并没有什么神奇的数学结论可以一眼秒掉，但数据范围又这门大，很显然可以通过打表来找规律。于是对以内的小数据进行暴力 #include "bits/stdc++.h" using namespace std; int main() { for(int i=1;i<=100;i++){ int sum=0; for(int j=1;j<=i;j++){ sum+=i/j; ...

题解： 考察点： 搜索 题解： 如果最开始位置是炸弹，则不存在可扩展的可能性，一定输出。否则其他情况一定是可以扩展的。采用广度优先搜索进行坐标的扩展。对于一个位置，对其周围个方向进行遍历，如果有越界，或者不能扩展的位置，则剪掉；如果周围个方向存在数字为的，则将其加入队列，作为新的进行新一轮的扩展，直到所有的点都遇到数字边界或者地图边界。 #include "bits/stdc++.h" using namespace std; typedef pair<int,int> P; const int maxn=1e3+10; int n,m,x,y; char s[maxn][maxn...

题解： 考察点： 思维，数形结合 解法： 题目中要求的是让成为新数列的中位数，则说明把新数列按照从小到大顺序排序后，要正好处于的位置，于是采用数形结合的思想来解决此问题最为简单。首先统计原数组中小于的元素个数，大于的元素个数，等于的元素个数。于是会出现有下图种情况： 如左边所示，若的元素个数多于，为了要使得位于中间位置，应该使得变得一样长，则增加的元素应该为。如右图所示，若的元素多于，由于的位置是取不超过的整数，于是的长度至少要变得比大1，否则中位数位置一定位于半区，所以增加元素应该为。最后，如果和一样长，那如果不存在则要增加个元素，否则自动位于中位数的位置上，复杂度 #include "...

题解： 考察点： 模拟，字符串 易错点： 题目中明确说明了是大数的乘法，很显然会是会爆掉int或者long long类型的，所以切不可用这2种类型来记录数据，进行简单的乘法 方法一：Python 因为语言支持自动高精度，因此本题如果用来写就会显得尤为简单。需要注意的是的输入是字符串，所以需要自己转化为对应的类型；去掉左右两端的空白符，返回；把字符串按空白符拆开，返回；把里面的值映射到指定类型，返回 m,n = map(int, input().split()) print(m * n) 方法二：高精度 语言支持自动高精度，语言有大数类，而C++语言中却不存在这种东西。但C++语言同样可以解决上...

题解： 考察点： 递归，二叉树，栈 易错点： 很多同学对于二叉搜索树的概念理解不清，二叉搜索树又被称为二叉排序树，其性质非常简单。首先二叉搜索树，可以为一颗空树，如果不是一颗空树，一定满足如下性质：若左子树非空，则左子树上所有结点均小于它的根结点； 若右子树不空，则右子树上所有结点均大于它的根结点；同时，它的左右子树也分别为二叉搜索树，也就是说不仅仅是根节点满足性质，其任意一个子树同样都满足上述性质。 解法一：中序遍历(递归版) 在易错点中已经说明了二叉搜索树的性质，根据性质，如果有一种办法能先访问它的左子树，再访问它的根节点，最后访问它的右子树，这样的搜索顺序得到的序列一定满足递增的。在二叉...

题解： 考察点： 滑动窗口，数形结合 易错点： 在本题中数据范围为，如果使用暴力求解是行不通的，因为如果使用复杂度为的暴力，那运算次数将达到，一般来说，在时间范围内所能抗住的运算次数在 解法：滑动窗口 首先，先从下图来观察出一个很重要的结论： 对于一个全由正整数构成的序列来说，如果区间中所有元素的和大于等于，则区间中所有元素的和一定大于等于。这是一个非常显然的结论，但在这里却非常有用。假设位置为区间和的分隔线，中所有元素的和大于等于，则当前位置对答案的贡献为，因为后面无论加上多少个元素，总可以，满足区间的和大于等于。 有了上述结论，可以很自然使用滑动窗口算法来做这个问题。对于当前位置，指针...

题解： 考察点： 栈 易错点： 本题要求、、三种操作都在复杂度内完成，也就是说都必须在常数时间内完成，其中和都是栈本来的操作，很多同学会考虑使用堆来维护最小值，但是这是不对的，因为堆每次找最小值的时间复杂度为 题解： 可以考虑使用两个栈来共同维护，一个栈用来进行元素常规的出栈和入栈操作，另一个栈维护最小值，其中栈顶元素表示当前栈中的最小值。对于入栈操作，首先将入栈，如果比中的栈顶元素小，或者为空，则将加入中。对于操作，直接取栈中的栈顶元素。对于出栈操作，栈直接出栈，如果当前栈顶元素等于的栈顶元素，则把的栈顶出栈 #include "bits/stdc++.h" using namespace ...

题解： 考察点： 栈，模拟 易错点： 由于习惯，日常生活中接触的一般为中缀表达式，导致很多同学不太明白什么是后缀表达式。后缀表达式被称为逆波兰式，是将运算符写在操作数之后的一种形式。简单来说就是如果存在E1 op E2形式的表达式，op是任意二元操作符，则E的后缀式为E1'E2' op，E1'和E2'分别为E1和E2的后缀式。有关后缀表达式的介绍可以参看百度百科 解法：栈 根据易错点中介绍的后缀表达式的知识，则有了如下思路。用一个栈来维护中缀表达式中的操作符，首先，遍历中缀表达式中的每个字符，如果是字母就直接输出，作为后缀表达式的一部分；如果是操作符，则比较其和栈顶元素的优先级，如果优先级低于...

题解：题目难度：三星 考察点： 哈希，思维 易错点： 很多同学在枚举倍数的时候会漏掉当的值为的情况，事实上，这种情况需要单独讨论，的值为1时，集合最大可容纳的元素个数就是集合中元素的种数，也就是让集合中不同的元素只能出现1次。 题解： 这题的数据范围为，因此如果对于每个位置暴力去探寻它的倍是否存在与序列种显然是不可行的，因为这样复杂度为，的时间内承受不住这么高的复杂度。可以通过空间换时间的方法来进行处理，通过哈希表来处理，这里建议选用，的底层是颗红黑树，当作哈希表使用查询的复杂度是的，同时是有序的，可以保证枚举的时候是从小到大进行枚举的。 对于为的情况，可以直接参照易错点中所述，输出元素的类数...

题解： 题目难度：三星 考察点： 哈希表 易错点： 因为和的范围都有，所以不能直接开成的数组，因为这样内存会爆掉，考虑到这是最大也只有，说明这是一个比较稀疏的矩阵，因此可以用来进行存储。 解法： 定义map<pair<int,int>,int>这样一个数据结构来存储方格中的数字。定义两个数组和，分别表示行号和列号，初始化行号为，初始化列号为。 如图所示，每次交换行和，实质上相当于交换和中的值，相当于它们对应的行号发生变化。同理如图所示，每次交换列和，实质上相较于交换和中的值，相当于它们对应的列号发生变化。而对于操作，只需要查询和即可，因为在前面的交换中，已经正确完成了行...

题解： 题目难度：二星 考察点： 贪心，排序，哈希 解法一：贪心+排序 将一个数列中的所有数两两配对并求和，在这些和中选出最大和最小值，使得二者差距最小。很显然就是要让所有的配对的和的大小尽量相等，试想一下，如果让大的和大的配对，小的和小的配对，那么最大值和最小值的差距将会进一步拉大，因此一种可行的贪心思路就是让大的尽量和小的配对，这样最大值和最小值的差距可以缩小，“和”的分布也会尽量平均。因此就会有如下解法，首先将数组从小打大进行排序，然后我们让第一个和最后一个配对，第二个和倒数第二个配对，如此下去。在配对的同时维护这些配对和的最小值和最大值，最后用最大值减去最小值就是所求，复杂度为 #in...

题解： 题目难度：二星 考察点： 思维，数学 易错点： C++中的除法是向下去整，也就是说当和均为整数时，只取整数部分，因此当全由构成时，其结果应该为，否则不能整除时就会少计算一个 解法：数学 当使用时，需要一个回合来蓄力，一个回合来攻击，需要两个回合。因此，当倍的都无法超过时，才使用，否则使用一定是更优的。如果全使用，则需要的次数为。如果全使用，则需要的次数。同时对于余数部分，分为3种情况，一种是直接整除，一种是一个可以完成，一种是需要才能完成。 #include "bits/stdc++.h" using namespace std; typedef long long LL; LL hp...

题解： 题目难度：一星 考察点： 枚举，暴力 解法： 因为只有3个任务，可以放心大胆的进行枚举，每次固定其中一个任务，并求出它和另外两个任务的差的绝对值的和，将3个任务依次固定，选出其中最小值 #include "bits/stdc++.h" using namespace std; int a,b,c; int Min(int x,int y,int z){ return min(x,min(y,z)); } int main() { scanf("%d%d%d",&a,&...

题解： 题目难度：一星 考察点： 数论，贪心 易错点： 很多同学拿到这个题都有一种比较直观的想法，希望使用，维护两个值，一个是当前值，一个是当前步数，然后通过队列去维护所有的情况，当第一次值为时，所对应的值即为最小步数。但是这个题的空间是承受不下所有状态的，所以这种方法并不可取。 解法：贪心+数论 一种正确的贪心策略就是每次都走最大步数，也就是步，这样能够保证最快可以到达，当最后走不了步时，如果刚好到达，输出，否则为，因为在下一步总可以走步 #include "bits/stdc++.h" using namespace std; int main() { int x; sca...