Praying_cqf
Praying_cqf
全部文章
未归档
训练总结(1)
题解(1)
归档
标签
去牛客网
登录
/
注册
Praying_最近有点奇怪
被你发现啦~嘻嘻嘻嘻嘻
全部文章
/ 未归档
(共12篇)
所有区间最值问题
这里有一种分治的做法。考虑当前分治区间[L,R],区间中心为mid,我们需要解决的问题是求出所有跨越mid的区间的答案。首先枚举右端点r(左端点也是一样的,这里只是举个栗子),对于所有左端点l和最大值(最小值),可能的情况有三种:1、max(l,mid)>max(mid,r)2、max(l,m...
2021-02-01
0
524
价格的可能性题解
【前言】 非常简单的动态规划题。 【暴力】 搜索,搜出所有可能性。 【不完美的超时做法】 设f[i][j][k]表示,只买前i种商品,共买了j件,能否达到价钱k。 可以转移到f[i+1][j][k]和f[i][j+1][k] 复杂度是O(nm^2*max(v))极限是500^4 【...
2021-01-16
0
482
最大价值问题题解
【前言】无。【暴力】枚举每种物品的选择与顺序。复杂度显然很大。【正解】假设我们知道了一个最优解的集合,但不知道顺序。最优顺序显然是按照代价从小到大排序后依次选择。因此,我们可以把物品先按代价排序,然后进行动态规划。设f[i][j]表示在前i个物品中选择了j个的最优答案,注意,这里的物品是按代价排好序...
2020-09-04
0
553
奇怪的排序问题题解
【前言】无。【暴力】搜索O(2^n)【正解】对于一个位置,如果这个位置后面有比它小的数,那这个位置肯定是要动的,这显然是答案的下限。我们来证明一下这个下限是可以达到的。有一种很显然的排序方法可以达到这个下限。从后往前看每个位置,如果该位置的身高大于后面的位置,则进行一次选择,这样就达到了下限。这种方...
2020-09-01
0
689
挑选方案问题题解
【前言】无。【暴力】直接搜索方案数。【打表】通过对小数据的暴力很容易得知答案就是(n+1)(n+2)/2【正解】我们将盘子2和4看做一类,盘子3和5看做一类,这样是可行的,对于任意正整数m,都可以表示为2x+a或5y+b的形式,这里的x和y分别就是在4和5号盘里面取的件数,a和b分别是是小于2的正整...
2020-08-31
0
601
集中问题题解
【前言】一道简单题。【暴力】枚举坐标系上的点,统计答案即可。【正解】可以发现题目中距离是切比雪夫距离,这样计算距离和非常不方便。我们知道切比雪夫距离和曼哈顿距离是可以相互转化的。切比雪夫距离相同的点可以围成一个与坐标轴平行的正方形,而曼哈顿距离相同的点则可以围成一个与坐标轴成45°的正方形。考虑曼哈...
2020-08-08
0
596
共鸣问题题解
【前言】简单题。【暴力】可以有2^n的暴力。还有其他暴力方式,不赘述。【正解】假设答案为ans,初始时,我们把ans设为所有额外共鸣的和的相反数。并且将额外共鸣分别加到两个音符的优美程度上,得到一个新的价值。最后,只有音符的价值大于0我们才将它加入答案。这样显然是正确的。具体请参照代码理解,非常简单...
2020-08-04
0
929
羁绊计算问题题解
【前言】充满欺骗意味的题目。【暴力】记录每个羁绊是否出现,根据打法不同,复杂度亦不相同。【比较厉害的暴力】我们有一个稍微奇妙一点的做法。用f[i]表示i与i+1到f[i]都建立了羁绊,可以发现f[i]具有单调性,那么在暴力的过程中,f[i]>=r则可以退出了。这样的话可以优化不少,但还不够。【...
2020-07-24
0
859
均衡题解
【前言】非常简单的题目。【暴力】枚举起点和终点即可。复杂度O(n^2)【正解】我们把0看成-1,然后求出前缀和数组s[],可以发现,如果区间[i,j]满足条件,那么s[j]-s[i-1]=0,即s[j]=s[i-1],那么对于每个s[]中可能的取值,保留最前面的那一个,用来更新答案即可。用桶来实现。...
2020-07-22
0
883
回家问题题解
【前言】比较难的题目。【暴力】每次搜索最佳路径。复杂度很大。【正解】正难则反。把问题变成,牛牛要按顺序出村子,尽量不经过有其他牛牛的位置。考虑一个优美一点的暴力,假设我们知道当前每个点出发离开网格时的最小内疚值,一个牛牛出村子可能会影响一些牛牛的答案,我们就暴力地更新,这样做最坏情况看起来是O(n^...
2020-07-10
0
658
首页
上一页
1
2
下一页
末页