题目考点：bfs题目大意：从S走到E，其中W是墙壁不能走，D是门，必须找到钥匙K才能经过门，求能从S走到E所用的最少步数题目思路：bfs模板，找到钥匙前，走过的地方标记为D；找到钥匙后，走过的地方标记为W，这样能避免重复走，同时处理了有无钥匙的情况；代码： #include<iostream> #include<algorithm> #include<cstring> #include<queue> using namespace std; const int N = 510; char mp[N][N]; int stx, sty, edx, ...

题目考点：位运算+01串枚举 题目大意：n*m由'w'和'b'石子组成的矩阵，每次选择一个石子按一下，按下之后，该石子以及上下左右的5个石子都会翻转（'w'变成'b','b'变成'w'），问讲矩阵全变成'w'或全变成'b'最少需要按几次，若无解输出Impossible 题目分析：经分析得知，若第一行元素确定，则可通过按第二行把第一行全变成指定元素，例如：bwbw wbwb wwww wwww如上例，如果想要把第一列的第一个b变成w同时不影响第一列，则可以且必须按第二列第一个w，即b后面的那个石子，所以，如果第一列的状态确定，那么第二列的状态也确定了，由此推之，只要确定第一列，后面的石子是否需要...

题目考点：01串枚举+贪心 题目大意：从n*m的矩阵中进行k次选择，每次选择一整行或者一整列，得到这一行/列的和，每次选择过后，该行数字将会被消除；求k次选择能得到的最大和。 题目分析：初步分析似乎是贪心，每次取最大和的一行或一列，但是很快能想出反例：  举一个反例： 3 4 2 0 0 0 100 100 0 0 100 10 10 10 0  如上例，若按贪心选第二行+第四列得到300，不如选择第一、四列得310； 一番分析后，我们可以由n、m小于等于15想出，先按01串枚举选行，再对列进行贪心，这样保证不遗漏所有情况，对每一行选或不选进行枚举，算法复杂度2^n，n在15以内，复杂度完全o...

考点：差分大意：在一个长区间内取走n和小区间，问取完后剩余的点数代码： #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 10010; int n, a[N]; int main() { int t; scanf("%d%d", &n, &t); while(t--) { int l, r; scanf("%d%d",&l, &r); a[l] -= 1,...

题目考点：分治（二分） 题目内容：给出一个01串，将其不断二分成一颗二叉树，求后序遍历；遍历过程中，若某一节点儿子均为1，输出‘I’，若均为0，输出‘F’，否则输出‘F’； 题目分析：如题目样例：3 10001011则有：  #include<iostream> #include<algorithm> using namespace std; int n; string s; char FBI(int l, int r) { if(l == r) //若已经到了叶子节点，直接返回 { if(s[l] == '0') { cout<<'B'; return '...

题目考点：二分 + 验证答案 题目内容：给n种牌和一种Joker牌，问能合成几套牌，其中每一套牌要包含n种不同的牌（其中给定的n种牌中若有一种不够用，可以用Joker代替，Joker也只能在一套牌里出现一次）。 题目分析：二分答案，例如题目样例：  3 4 1 2 3 //即第一种牌1张，第二种2张，第三种三张，joker 4 张，每套牌3张，至少含三种不同的牌我们来模拟验证答案为2、3、4时的答案：观察到以下情形：1、如图①和②，当第一种牌或者第二种牌不够用时，可以用joker替换；2、如图①和②，使用的joker小于4，说明够用，则ans = 2 或 ans = 3能够组成 ；3、如图③，...

题目考点：dp -- 01背包 （无脑dfs肯定T ，后面附上60分dfs吧） 题目大意：将a数组中的数分成两组，使得两组中的数的和尽量接近，输出两组数的和（若无法平均，优先输出较小的数） 题目分析：01背包问题，若a数组中的数总和为sum ，可以假想一个体积为sum / 2的背包，将其尽量装满即可代码如下：  #include<iostream> #include<algorithm> using namespace std; const int N = 10010; // 100个苹果每个质量都是100的话，需要一个10000的背包 //所以dp数组至少需要5000...

题目考点：曼哈顿距离（搜索算法里面会用到） 题目内容：判断能否恰好使用 m 步从( a, b ) 走到 ( 0 , 0 )； 题目分析：在坐标轴上从一个点走到另一个点需要的最短距离叫做曼哈顿距离，即 ; 而判断从A点恰好用m步走到B点时，有两种情况： 第一种：m = distance，即走了曼哈顿距离恰好到达B点，对应上图绿色路线，需要3步； 第二种：m > distance 时，需要判断能否走到，观察上图黄色（7步）和蓝色（11步）路线，即可发现若走到B上下左右四个格子时，若剩余奇数步（比如蓝色走到8的时候离11步用完还剩下3步），则可以“绕路”，花完剩下的步数；相反若m 为 10， ...

题目考点：离散化（其实怎么写都行，以个人目前能力感觉离散化+前缀和比较好上手） 题目大意：一条线上红蓝两种石头随机排列，易知存在若干点使得这些点前后均为红色石头，且绝对不含蓝色石头，找到这些点中的前后红色石头数量最多的那个点，输出最大数量 题目分析：如图，我们可以确定a[4]和a[5]之间的点，前后含有红色石头最多（绝对不含有蓝色），因此我们的目标就是以相邻两个蓝色石头为基准，计算他们之间红色石头的数量（即连续红色石头区间）的最大值；计算区间和，首先想到前缀和（假定我们不知道线段树 =_=||）； 注意点：1、对于这道题，存在数组最前面和最后面是红色石头的情况，因此我们在a[ 0 ] 和a [...

题目考点：尺取法（双指针）题目大意：给定一个字符串，问集齐26个字母所需要的最短区间是多长。题目分析：右指针字符串，当26个字母集齐之后移动左边界，维护最短长度即可；代码： #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 26, M = 1000010; int n, ans = M, ch[N]; string s1; bool jud() //判断26个字符是否集齐 { for(int i = 0; i < 26;...

题目考点：区间dp 题目大意：将一个空白模板涂成目标颜色的模板，一次涂色的长度任意，求最少涂色次数，参考题目样例： 例如第一次把木版涂成RRRRR，第二次涂成RGGGR，第三次涂成RGBGR，达到目标。  题目分析：用dp[ i ] [ j ] 表示从i涂到j所需要的最少涂色次数，则有以下两种情况： 第一种情况：a [ i ] 和 a [ j ]颜色相同，如NIUKEN，则这种情况和涂NIUKE需要次数相同，因为我们可以在涂第一个N的时候一下涂到第二个N，两端点颜色相同可以看成其中一个端点是拓展来的；即 dp [ i ] [ j ] = min ( dp [ i + 1 ] [ j ] , d...

错误思路：dp+贪心 86%测试点（题解里也有大佬用这种写法wa了，对我自己来说就是初学dp总是想贪）因此谨记：求解 全局最优 不要用 局部最优 思路！！！！！！！！！！！ 正确思路：四维dp 题目大意：n*n的地图上分布数字，从左上角走到右下角，走两趟，第一趟走过的地方变成0，求两次走完取到的总数字相加的最大值。 题目分析：先说一下错误思路吧，走两趟，第一趟取能取到的最大总和，想到花店橱窗那道题（我的博客里也有题解，不嫌弃蒟蒻的话可以去康康啦~~），倒推求路径，再走一趟。错误代码以及自己造的样例：  //错误代码！！！ //错误代码！！！ //错误代码！！！ //错误代码！！！ /* 1 2...