题解： 题目难度：三星 考察点： 哈希表 易错点： 因为和的范围都有，所以不能直接开成的数组，因为这样内存会爆掉，考虑到这是最大也只有，说明这是一个比较稀疏的矩阵，因此可以用来进行存储。 解法： 定义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,&b,&a...

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

题解： 题目难度：三星 考察点： 深度优先搜索，回溯，剪枝 易错点： 这个题目对于同学们来说做法非常直接，就是递归+回溯，也很容易想。但是因为物品的数量达到了，如果用简单的不进行剪枝的话，是无法跑过所有数据的，因此需要做一些剪枝。 题解：深度优先搜索+剪枝 这个题目的做法很显然，就是使用递归+回溯，每次从编号枚举物品，如果当前物品的数量不为，且已经排好了的上一个和当前物品不同，则可以把当前物品加入序列，然后不断递归下去，直至所有的物品都被取完。然后这里存在一个可以剪枝的地方，如果当前序列中数量最多的物品都数量的倍，大于剩余物品数量加，则说明当前的摆放方式是不合法的，可以直接剪掉。因为这种情况下...

题解： 题目难度：二星 考察点： 数形结合，找规律 易错点： 很多同学看到这个题目首先想到可以暴力，但是由于这个题的和都太大了，如果暴力的话，无论是时间还是空间上都无法承受，所以这是一种不可取的做法。 解法：数形结合+找规律 首先有一条非常重要的性质：对于一个位置，如果被翻偶数次，它一定维持原来的状态，如果被翻奇数次，则一定跟原来的状态相反。有了这种重要的性质我们可以很容易画图来解决这个问题。  显然如图a所示，对于的，它被翻奇数次，所以是。如图b所示，对于的，黄色部分会被翻转偶数次，因此维持原状不变，红色部分会被翻转奇数次，因此状态发生改变，而黄色部分仅为最边上的个，所以答案是。同理，推广到...

题解： 难度：二星 考察点： 思维，数形结合 题解：数形结合 显然如果把个连续排在一起，则一个满足条件的都不存在，很显然最小值为，接下来难点变成了求最大值。最大值的排列情况如下图所示：   红色表示住户，黄色表示空地。显然上图所示这种情况能够组成最大值，假设有个住户，则会占据个方格，所以当时，满足条件的位置共有个。当时，则必然有些住户要连续排在一起，这样的住户数量为，然后剩下的位置拿去做最大的排列,也即是满足求出满足的最大 #include "bits/stdc++.h" using namespace std; typedef long long LL; int main() { int T...

题解： 难度：三星 考察点： 模拟，线段树，二分 解法一：模拟 这个题的测试数据可能比较水，没想到暴力也能卡过去。设置一个数组来记录每一层的香槟体积，对于每一次查询操作，直接输出即可；对于每一次修改操作，如果，则香槟会继续流入下一层，直到不能流为止，否则香槟在当前层终止，并修改当前层的体积。 #include "bits/stdc++.h" using namespace std; const int maxn=200000+10; int a[maxn],b[maxn],n,m; int main() { //freopen("in.txt","r",stdin); scanf("%d%d"...

题解： 考察点： 链表，迭代，递归 易错点： 题目只给定链表，并不确定链表中元素的个数。很多同学不会读入。因为输入由整数和空格构成，建议当成字符串读入，使用按行读入，因为无法处理空格。同时推荐使用类对输入进行解析 很多同学不会写链表，其实链表的表示非常简单，可以定义为由值和指向下一个结点指针构成的结构体，同时C++ 中最好使用构造函数为和赋上初值 方法一：迭代 当链表和均不为空时，分别设置两个指针指向和，当中元素较小时，选取中的元素，并把的指针后移；当中元素较小时，选取中元素，并把指针后移。此时，如果还有剩余，将排序好的链表直接指向；如果还有剩余，则将排序好的链表指向 #include &am...

题解： 考察点： 暴力 易错点： 从位置开始，长度为的字符串为 的大小可能为0 解法： 由于每次选取长度为n的字符串输出，同时结合易错点中所述，需要枚举的值为，建议使用中类里面的函数输出结果比较方便，该函数第一个参数为子串开始位置，第二个参数为子串长度。注意当的值大于或者小于时不合理 #include "bits/stdc++.h" using namespace std; string s; int n; int main() { cin>>s>>n; int len=s.length(); if(n>len||n<1){ cout<<"-1"...

题解： 考察点： 深度优先搜索，字典树，剪枝 易错点： 本题的输入不是直接可用的，需要对输入进行字符串解析，同时由于输入带有空格，如果直接用会无法读入，建议使用按行进行读入。对于输入的解析，建议使用标记法，设置一个变量，当处于有效区域时，把标记为，当处于无效区域时，把标记为。这样保证有效部分能够很好的被解析出来。 本题的输出结果是按照字典序从大到小降序输出的。 方法一：深度优先搜索+剪枝 这题最直观的想法就是，对于字符串中每个位置，如果其前缀在集合中能找到，其可以以它为起点，往后找寻剩余部分是否在集合中，如果在集合中，则可以继续往后递归。这里加入一个剪枝，表示从到是否满足条件，如果在进行以后发...

题解： 考察点： 深度优先搜索，动态规划 易错点： 方格的大小为，但是格点数却为 方法一：深度优先搜索 选用深度优先搜索是解决这类题目最直观的思路，因为格点只能往下走或者往右走，所以对于方格中位置，一定只能由它的上方位置和左边位置走过来。那么令为走到位置的方案数，则根据加法原理，它一定由左边位置的方案数加上上方位置的方案数。同时记得处理一下边界情况，也就是递归结束的条件，对于位置，它的方案数一定为1，而对于越界的位置，方案数一定为0 #include "bits/stdc++.h" using namespace std; int n,m; int dfs(int x,int y){ if(x...

题解: 考察点：深度优先搜索，回溯，剪枝 易错点： 字符串中的字母有重复，直接使用全排列生成的字符串会有重复，需要通过剪枝或者等手段去重。 方法一：回溯+去重 回溯法是一种深度优先搜索中常用的一种手段，基本思想是首先按选设定条件进行深度搜索，当探索到某一步时，发现原先搜索的路径并不满足，就退回上一步重新选择。在全排列问题中，首先设置一个指针，代表当前生成的字符串中的元素个数，设置一个数组表示每个位置是否被访问过，然后按照从前往后的顺寻，选择未被访问过的字母进入字符串，每次被选择的位置把标记为已访问，在进行深度优先搜索之后再将标记释放，进行回溯。注意，因为字母有重复，因此生成的全排列也会有重复，...