题意分析  给出一个二维矩阵，矩阵的每个位置有一个数字，我们需要任意选择一个起点，然后从这个起点出发，每次只能走比当前数字更大的位置，问我们最多可以走多少步。 每次走的位置只能是上下左右四个方向，同时不能越界。每个格子最多只能走一次。  思路分析  一个DFS的操作，我们发现，我们可以枚举某一个起点，然后进行递归操作，用一个递归函数表示从这个位置开始可以最多走多少步。然后由四个方向的位置进行转移过来。一旦发现在过程中不符合题目的条件，我们直接进行返回0即可。  解法一 暴力DFS  我们直接暴力枚举每个起点进行DFS，在过程中维护最大值即可。递归直接往四个方向进行即可，但是首先需要先判断四个方...

题意分析  给出一个合法的表达式，需要我们计算这个表达式的值。  思路分析   对于这种表达式的求值，我们在确实输入的序列是合法的情况下我们可以使用递归的方法进行求解。我们可以递归计算每个括号的值，然后我们将整个表达式切分成数值和运算符的形式，我们将我们得到的数值放到栈里面，然后将所有的符号都尽量转化为加法的操作，比如减法的话就取个反，乘法的话就先计算出来。   我们重点来讲一个如何对一个序列进行切分，这里我们需要把一个括号里面的计算的值看作是一个数字，因为我们最后肯定是可以将这个表达式计算出来的。即使有括号的嵌套也是这样的，我们进行递归操作。这样下来，我们的表达式就变成了只有数值和运算符两部...

题意分析  给出一个二叉树的前序遍历的序列和中序遍历的序列，我们需要找到这个二叉树的右视图结点的权值构成的数组。这里的右视图就是从右边向左边进行投影能看到的序列有哪些?  思路分析   前置知识   我们首先需要知道二叉树的先序遍历的序列和中序遍历的序列是什么？   如下图 我们把一棵树分为根结点，左子树和右子树。先序遍历就是先遍历序列的根节点，然后遍历序列的左子树，然后遍历序列的右子树。中序遍历就是先遍历序列的左子树，然后是根节点，最后是右子树这样的顺序。后序遍历就是先遍历序列的左子树的所有的结点，然后遍历树的右子树的所有的结点，最后遍历序列的根结点。通过以上的描述我们可以发现，其实这个先，...

NC591 题解 | #牛牛的Fib序列# 题意分析  题目给出一个序列的前两项，需要我们计算这个序列的第n项的值，并且题目给出序列满足f[i]=f[i−1]+f[i+1]f[i]=f[i-1]+f[i+1]f[i]=f[i−1]+f[i+1]  思路分析  首先，我们对上面的公式进行推导  f[i]=f[i−1]+f[i+1]f[i+1]=f[i]−f[i−1]f[i]=f[i−1]−f[i−2]f[i]=f[i-1]+f[i+1] \\ f[i+1]=f[i]-f[i-1] \\ f[i]=f[i-1]-f[i-2]f[i]=f[i−1]+f[i+1]f[i+1]=f[i]−f[i−1]f...

NC565 题解 | #分石子# 题意分析  给出n堆石头以及每堆石头的数量，然后我们可以将任意堆石头数量大于1的分为两堆，问最后分为m堆中，分得的所有堆里面的最小值最大是多少？  思路分析   对于这种最小值最大，最大值最小等的问题，一半都是采用的是二分的方法进行处理。我们先判断怎样二分具有单调性。我们二分数组里面的最小值，假设当前的最小值为mid，然后对于这个mid，我们看可以分为多少块，如果我们可以分成k块，k>=m，那么说明我们的最小值可以更大，左边界向右边移动，否则，就将右边界向左边移动。继续二分新的边界。如此下去。   对于每个二分的值，我们如何进行处理呢？我们遍历整个数组，...

NC564 题解 | #牛牛打怪兽# 题意分析  1-n个位置，每个位置有一个怪兽，每个位置上的怪兽有一个血量，每攻击一个怪兽依次这个怪物会掉一滴血。牛牛攻击在第i个位置的怪兽的时候，会连带攻击到怪物i+i和i+i+1的位置的怪兽。但是只有i+i和i+i+1都在范围1-n之间才能执行这次的攻击的操作。问最少执行多少次操作才能将所有的怪兽都打败（怪兽打败是怪兽的血量为0，同时对怪兽血量为0的怪兽还能继续进行攻击操作)如果不能实现，那么返回-1  思路分析   这是一个贪心的题目，我们先来分析一下哪些是-1的情况，我们发现，如果n<3，那么不能执行任何攻击的操作，返回-1，否则如果输入的n是...

NC563 题解 | #吃汉堡# 题意分析  一个人需要吃n天的汉堡，每天会给两种汉堡及其数量，分别为牛肉汉堡和鸡肉汉堡，对于吃这n天的汉堡，需要满足如下条件  每天吃的汉堡的数量都不一样。 在吃的总的汉堡的数量最多的前提下，吃尽可能少的牛肉汉堡。 注意每天给的汉堡不一定要吃完    思路分析   首先，这个题目是一个贪心的思路，我们来看一下怎样的贪心的方法。我们先来看一下优先级，首先要确保总的数量最多，然后就是相同的数量下要尽可能使得其中的牛肉汉堡的数量少。那么我们肯定先满足数量最多，我们需要找到数量最多的是哪些天。这一点我们就可以使用结构体排序或者优先队列进行处理。   处理完之后，我们观...

NC562 题解 | #牛牛的魔法卡# 题意分析  在一个一维坐标轴上面给出若干个位置，每个位置有一个数字，两个位置的距离就是这两个位置的差值。可以从任意一点出发，问恰好经过k个不同的数值的最短的距离是多少？  思路分析  我们先分析思路，我们发现，为了使经过的距离尽可能短，我们应该选择的是一段区间，这段区间内不同的数值的个数为k个。走的距离就是区间的长度。所以我们需要先对题目的输入数据按照坐标的大小进行排序。方便我们进行后续的初始。 特判-1的情况就是所有的数值中不同的数值的个数小于k。  解法一 暴力求解   我们暴力枚举每个起点，然后从这个起点开始往右边移动，直到区间范围内的不同的数值的...

NC561 题解 | #单词消消乐# 题意分析  给出n个字符串，从第一个字符串开始，和下一个字符串执行消除的操作，也就是如果当前这个字符串的最后一个字符和下一个字符串的第一个字符相等，那么这两个字符就消除，一直执行这样的操作直到字符不相等或者是其中一个字符串为空，然后将这个两个字符串剩下的字符按照先后顺序拼接成一个新的字符串，继续和下一个字符串执行类似的操作。问最后得到的字符串是什么？  思路分析  这个题目，我们需要先知道上一个字符串的最后的那个字符是什么，然后遍历这个新的字符串依次进行比较，最后执行相应的操作，其实就是一个很简单的模拟题。  解法一 栈模拟  首先，我们想到先用栈来执行模...

NC 560 题解 | #打字# 题意分析  依次打出一个字符串，其中字符<表示将前一个字符删除，问最后打出的字符串是什么？  思路分析  一个很简单的模拟题目，我们可以明显的看出需要使用栈的思想来进行解决。我们首先需要了解什么是栈？栈是一种先进后出的数据结构。如下图     其实利用栈的原因是我们可以在O(1)的情况下取到上一个字符。所以我们大致的思路就是先将所有的字符按照顺序依次放进栈里面，如果遇到<字符的话。我们就将栈顶的元素拿出去，直到为空。最后，将栈里面的字符依次取出来，然后进行反转就能得到最终的答案了。  由于本题的思路比较单一，这里我用了两种语言实现。  写法一 C+...

NC559 题解 | #原根# 题意分析  给我们n个字符串，对于某一个字符串，如果除了这个字符串本身之外的字符串都不是它的前缀，那么我们就称这个字符串为原根。问这n个字符串里面有多少个原根。  思路分析 解法一 暴力求解   首先，我们来进行暴力求解。我们先枚举每个需要进行判断的字符串a，然后枚举这个字符串之外的其他字符串b，对于两个字符串相比较，我们需要判断b是否为a字符串的前缀。直接循环遍历比较即可。   代码如下  最外层需要枚举每个字符串，执行n次操作，需要遍历所有的字符串的所有的字符，次数为O(∑Si(1<=i<=n))O(\sum{S_i(1<=i<=n)...

NC558 题解 | #相似和# 题意分析  给出n个字符串串s1,s2,...sns_1,s_2,...s_ns1​,s2​,...sn​  定义两个字符串s,ts,ts,t的相似度f(s,t)f(s,t)f(s,t)为他们的最长公共前缀长度 求 ∑i=1n−1∑j=i+1nf(si,sj)\sum_{i=1}^{n−1}\sum_{j=i+1}^nf(s_i,s_j)∑i=1n−1​∑j=i+1n​f(si​,sj​), 保证所有出现的字符均为'a'~'z'的小写英文字母 思路分析 解法一 暴力法  我们直接利用双重for循环枚举两个字符串，然后再一个for循环逐个比较前缀和，累加到答案即...

NC557 题解 | #好多牛牛# 题意分析  给出一个字符串，需要找出里面"niuniu""niuniu""niuniu"这个字序列的数量。子序列可以通过在原串上删除任意个字符(包括0个字符和全部字符)得到  思路分析  这里，我介绍两种空间优化的方法  解法一 动态规划 + 滚动数组  我们先定义状态方程dp[i][j]，表示前i个字符中以"niuniu"这个字符的第j个字符结尾的子序列的个数。然后就可以进行一个正常的转移了，转移方程如下  dp[i][j]={dp[i−1][j]+dp[i][j]s[i]==c[j]dp[i−1][j]s[i]!=c[j]dp[i][j]=\left\{...

NC556 题解 | #平衡的选择题# 题意分析  有n个多选题，每个多选题可以选择的情况有15种，(A,B,C,D,AB,AC,AD,BC,BD,CD,ABC,ACD,ABD,BCD,ABCD)(A,B,C,D,AB,AC,AD,BC,BD,CD,ABC,ACD,ABD,BCD,ABCD)(A,B,C,D,AB,AC,AD,BC,BD,CD,ABC,ACD,ABD,BCD,ABCD).现在，我们需要设计n个选择题的正确答案种，A和C选项数量差值不超过1，B和D选项数量差值不超过2.问有多少种情况。答案模1e9+7  思路分析  思路应该比较清晰，对动态规划熟练的话应该一眼就能看出这个需要用动...