比赛的时候写了个假算法，跑的贼快还AC了，现在看了下确实相当不妥，当时写的两个dp并不同步，运气好，数据刚好没有能卡的罢了，现在来补一下正解。 Solution 遇到问题毫无头绪的时候先从暴力的方法入手然后逐步优化。首先能想到01背包的暴力解法。 表示前 个数满足: 对于 这一维，我们可以对 的数取 不影响答案，这样就得到了一个 的做法。 现在该思考的是如何优化，注意数据范围: 。这里要用到单调队列优化DP。 表示前 个数满足: 单调队列维护一个队列满足 ： 单调递增的同时 单调递增 在 的条件下求 对于空间上的优化，我们发现只会用到 的状态和 的状...

Solution 遇到比较困难的题目可以先从比较暴力的方法开始入手在结合题目的一些性质、数据范围开始进行优化。思考一下能够想到比较暴力的dp: : 表示第 行选了 列，一共选了 个数的最大值。 按上述式子写复杂度是 毫无疑问会TLE、MLE，接着开始优化，我们降一维则可以通过本题。 仔细观察发现我们可以把 提到 max 函数外面。时间：我们可以通过后缀最大值来优化这个式子，每次对当前行求完的同时进行后缀最大值。空间：滚动数组 时间复杂度: 坑点：一定要清空 ， 因为不清空的话 是上上一行的后缀最大值，他的列是对不上的。 Code #include <bits/stdc++...

Solution 每次遇到这种比较复杂的问题的时候，可以先从比较直观的暴力方法去考虑再去思考如何优化。比如这道题，我们比较容易的想到的是的dp转移。定义： : 到第 个建筑物的最大美丽值。 : 到 之间最矮的建筑物的美丽值，即。 为了降低复杂度，DP存在很多种优化方式，而这道题需要用到单调队列优化。 仔细观察，我们可以发现 是单调递增的， 是固定的。利用单调栈维护单调递减的 数组对应的下标，对于 , 我们可以找到左侧最近的 , 使得 ，此时 有两种可能： 将 和 放入到一张照片，此时答案为 将 放入到一张照片, O(NlogN) #inclu...

Solution 首先很容易看出这道题是一道换根DP。我们首先可以写一个DFS求出以某个节点为根的答案，一般根节点就取1号节点，是因为,一般1号节点是存在的，当然也可以随便取别的。重点是考虑答案的转移。假设已知节点的答案，我们需要哪些信息能够通过一定的方式转移到呢？ 将转移分为部分维护，左边部分为部分，右边部分为部分。 我们需要维护表示其他所有节点到节点的距离和，即。还需要维护表示以为根节点的子树的大小，表示子树的，。对于对于的转移：对于部分的转移：对于部分的转移：（我们需要减去时的部分，然后加上时的部分。） Code #include <bits/stdc++.h> #defi...

Solution 首先容易分析有两种走法： 先右再下(包含只右不下) 先下再右 对于第1种走法，我们只需要遍历第一行第一个障碍物之前的列，计算每一列遇到第一个格子之前的长度即为贡献。问题在于如何计算第2种走法的同时不重复计算第1种走法。下面为了方便我用表示每一行的限制，表示每一列的限制，及第一个遇到的障碍物。 我们此时只需要计算第1种走法无法走到而第2种方法可以走到的格子即可。有2种格子： 显然的格子的贡献我们都没有计算，但是在第2种走法的情况下，我们可以走到这些格子，我们将其放入数组中。 从开始第列被的石子挡住了，因此无法通过第1种走法走到，而可能可以通过第2种走法走到，我们将放入。 ...

Solution 扫描线读题的时候发现重点是，这就大大简化了这道题。首先我们先考虑如何计算某一行的贡献，我们发现如果我们知道连续的白色块的，那么他的贡献就是，那么我们创建一个set<pair<int, int>>去维护当前行的连续白色格子的断点即可，我们对每一列的计算可以将列旋转90度看作行来处理，将改为互换即可。需要注意的是当的时候，两次扫描的结果都是的格子，是一样的，所以只需要横竖里任选一遍扫描即可。扫描线同理，标记入边操作和出边操作，进行排序之后维护。del：入边的时候插入黑色格子，即删去set中的（若存在），这点和珂朵莉树很相像。add:出边的时候我们插入之前被...

Solution 哈希 + DP复杂度：首先利用Hash字符串将所有的字符串一一哈希，这样的好处在于我们可以高效的比较两个字符串[l, r]的部分是否相等。转移方程：表示有多少匹配的方案数。首先利用Hash字符串将所有的字符串一一哈希，这样的好处在于我们可以高效的比较两个字符串的部分是否相等。然后暴力枚举转移即可，倒序转移的原理同背包可以节省一维。 坑点：第一次用unsigned long long MLE了，改用unsgined int就过了。 Code #include <bits/stdc++.h> #define fi first #define se second #d...

Solution 比赛的时候手推，发现规律，然后打了个表。看到了如下的规律: 0 : 1 1 : 1 1 1 2 : 1 2 0 2 1 3 : 1 0 0 1 0 0 1 4 : 1 1 1 1 1 1 1 1 1 5 : 1 2 0 0 0 0 0 0 0 2 1 6 : 1 0 0 2 0 0 0 0 0 2 0 0 1 7 : 1 1 1 2 2 2 0 0 0 2 2 2 1 1 1 8 : 1 2 0 1 2 0 1 2 0 2 1 0 2 1 0 2 1 9 : 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 10 : 1 1 1 ...

Solution 枚举贡献,当前的数量为个。 对于贡献挑选的有对， 对于确定的情况有多少种的选法问题，其实等价于个不同的盒子里放个相同的小球，有多少种放法。下面求个盒子里放个相同的小球，有多少种放法，这本质就是重复组合的问题。有种方法，具体可以看重复组合的定义和证明。将代入，对于确定的情况有种选法。 Code #include <bits/stdc++.h> #define fi first #define se second #define mp make_pair #define lowbit(x) ((x) & -(x)) using namespace...

Question 给定点权无向图，求任意由到的路径中最大的第小的点权。 Solution 二分答案，假设答案为，则对于第小的点权，我们将其转化为该路径上有的点，他们的点权值。我们将路径上的点染色分为两种点： ，染为。 ，染为。 有如下情况：一. 与不联通，二. 与联通， 路径上存在两个连续的号点，则显然我们可以通过反复横跳，来无限增大路径的长度，则必然能够满足使得。 由于上面的情况已经除去，所以目前来说最好的情况是间隔，此时反复横跳已经没有任何意义。a. ，则所求点为中位数，由于首尾为，所以，b. ,则所求点为第小的点权,， 此时都有可能，我们DFS染色验证即可。 Code #in...

Solution 一遍贪心的差分就够了，从开头往后插有三种情况： 代表a[i]处的差分前缀和 说明两者相等，无需操作。 a. ​ 说明前方的数都要增加，那么显然。 ​ b. ​ a. ​ 说明后方的k个数都要增加$ ​ ​ ​ b. ​ Code #include <bits/stdc++.h> #define fi first #define se second #define mp make_pair #define lowbit(x) ((x) & -(x)) using nam...

#2020我的牛客回忆# 2021 让我们一起加油！ @牛妹

# [NC15553](https://ac.nowcoder.com/acm/problem/15553) ## 题意 给你n个数，选2个长度为k的连续区间，求他们加起来的和最大为多少？ ## 思路 前缀和预处理，然后利用前缀和计算k个数的最大数为多少，然后预处理从左边遍历到i为止最大的区间长度为k的和为多少，从右边遍历到i为止最大的区间长度为k的和为多少。 扫一遍要选的第一个区间，扫的过程如果左右还有可以选的区间，则取他们的最大值和选的区间相加，记录最大值即可。 #include<bits/stdc++.h> using namespace st...

牛客题霸汇总 1.NC61两数之和 C++题解/答案 2.NC103反转字符串 C++题解/答案 3.NC105二分查找 C++题解/答案 4.NC88 寻找第K大 C++题解/答案 5.NC52 括号序列 C++题解/答案 6.NC61 两数之和 C++题解/答案 7.NC1 大数加法 python题解/答案 8.NC75 数组中只出现一次的数字 C++题解/答案 9.NC32 求平方根 C++题解/答案 10.NC7 买卖股票的最好时机 C++题解/答案