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

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

题解： 难度：三星 考察点： 模拟，线段树，二分 解法一：模拟 这个题的测试数据可能比较水，没想到暴力也能卡过去。设置一个数组来记录每一层的香槟体积，对于每一次查询操作，直接输出即可；对于每一次修改操作，如果，则香槟会继续流入下一层，直到不能流为止，否则香槟在当前层终止，并修改当前层的体积。 #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); scan...

题解： 考察点： 链表，迭代，递归 易错点： 题目只给定链表，并不确定链表中元素的个数。很多同学不会读入。因为输入由整数和空格构成，建议当成字符串读入，使用按行读入，因为无法处理空格。同时推荐使用类对输入进行解析 很多同学不会写链表，其实链表的表示非常简单，可以定义为由值和指向下一个结点指针构成的结构体，同时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){ ...

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

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

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

题解： 考察点： 区间合并，双指针 方法一：暴力 一般来说，暴力都是解决问题最直观，也是最容易被同学们想到的方法。题中明确说明每个字母只能在一个子串中出现，因此必须保证子串内的每个字母在字符串中第一次出现的位置到最后一次出现的位置都位于区间中。设置两个指针和，表示区间的开始位置和结束位置。当访问到字符串中位置时，如果不超过，则比较在字符串中结束位置和的大小，如果大于，则把修改为的结束位置；如果大于，则记录区间的长度。因为对于每个位置都需要向后找寻结束位置，一共有个位置需要找寻，时间复杂度是 #include "bits/stdc++.h" using namespace std; string...

题解： 考察点：贪心，动态规划，单调栈 常见错误： 如果除去输入只实现一个类的话，这是一个很经典的面试题目，很多同学在面试中都遇到过。但是因为这里的输入跟大家熟知的不太相同，很多同学拿着无从下手。其实面对这种没有给定个数的输入数据，有很多读入方法，其中最常见的就是当成字符串，以按照一行来读入，然后对字符串进行解析。但是最快的读入方法还是推荐使用。每次读入 1​ byte​ 的数据，并将其转换为类型的函数，且速度很快，可以用“读入字符——转换为整型”来代替缓慢的读入。同时在读入中修改只对数字有效，而略过","，我们一般称这种方法为读入优化，有关于更多的知识，可以上OI-wiki去学习。 方法一：...

字符串价值 题目难度：中等 知识点：数学逻辑，字符串，数组 解题思路：每一次减去当前字符串中出现次数最多的字符，重复K次后，即可得到价值最小的字符串。 方法一 使用优先队列。首先定义一个数组，用于存储字符串中每一个字符出现的次数，然后定义一个优先队列对每一个字符出现的次数由大到小进行排列，每一次循环，对次数最大的数字减一，直至循环到第k次为止，计算所有字符串出现的次数，最后将所有次数的平方和相加。 import java.util.*; public class Main{ public static void main(String[] args){ Scanner ...

排序 题目难度：简单 知识点：数学逻辑，数组 解题思路：将数组按照从小到大的顺序排序，新旧数组中数值不相同的的总位置数即为题中需要移动的个元素的个数。 方法一 首先创建一个新的数组，使用不断循环的方式将旧数组中的值赋给新的数组，完成数组的复制。然后对新数组进行排序，最后对比两个数组在同一位置处的数值是否相同，统计数值不同的数量。 import java.util.*; public class Main{ public static void main (String args[]){ Scanner in =new Scanner(System.in); ...

回文素数 题目难度：中等 知识点：数学逻辑，数组 解题思路：首先判断数字是否为回文，然后判断数字是否为素数，若都是，则为回文素数。下面具体介绍回文和素数的判断方法。 方法一 回文的判断方法：对数字取余得到个位数字，然后对该数字除以十后取余，得到十位上的数字，随后继续除以十后取余获得百位上的数字，直至数字为0时停止。将各个位上的倒着排列组成新的数字，判断新数字是否与原来的数字相等，若相等，则为回文。素数的判断方法：若待判断数字为n,由2至n-1共进行n-2次循环，判断该数字是否能被n整除，若能则不是素数，若都不能，则是素数。 import java.io.*; public class Main...

编程题2 题目难度：中等 知识点：数学逻辑，数组 解题思路：首先，找到初始房间。然后，计算每轮分配情况。最后，计算初始人数。我们分三种情况来讨论初始房间room_i的位置，其中最后一次被分配的房间为room_x，再分配后房间内最少人数为p_min。1.room_i在room_x之后。按照每轮分配原则，room_x+1和room_i之间被分配p_min个人，room_i向后绕回room_x的房间则被分配pmin+1个人，可以计算出room_i的初始人数为 p_min×n+[n-(room_i-room_x)]。2.room_i在room_x之前。同理，room_i+1到room_x之间被分配p_...