在刷题的单身狗很开心

题解

2023河南萌新联赛第（八）场(3) c++(1) 动态规划(5) 差分与前缀和(4) 洪水填法(1) 牛客小白月赛78(4) 牛客练习赛115(2) 牛客练习赛116(2) 算法(1) 算法刷题(2)

/ 注册

全部文章 / 题解（共176篇）

题解 | #牛可乐与NCPC#

这题好难。。。，题目上要求不存在一个队伍j使得链接：aj≤ai,bj<bi 或者 aj<ai,bj≤bia_j< a_i,b_j\leq b_iaj<ai,bj≤bi 那么就可以加入观察里面。单纯从数据上看两个变量都需要满足，有点麻烦。但如果放到坐标系上可以看出其实是...

C++ STL set multiset

2023-09-15

3 432

题解 | #任务#

本题是一个贪心问题，如果进行任务和机器的匹配是我们要考虑的问题。首先如果按照任务的要求去找机器的话，那么任务可以先定时间，去机器里面找时间上符合要求的机器，然后肯定是要选择满足难度级别的最小的那一个，这样可以为后面的任务腾出最大的空间。但题目要求数量和利润都达到最大，但从利润的计算公式上看，时间的占...

C++ STL 贪心

2023-09-15

3 423

题解 | #Let'sPlayCurling#

算是一道考验思维的题吧，关键在于看出来如果要距离红球比篮球近的话那必然不能跨越篮球。那么就需要红球扎堆，也就是说红球扎堆的越多就有更多的胜利。那么就到了统计红球的个数了。可以使用前缀和来求解。 #include <bits/stdc++.h> using&nbs...

C++ STL

2023-09-15

2 330

题解 | #星球大战#

本题的数据范围有点大，所以得使用map去进行离散化。由于map的key不能重，而一行里面又有多个y坐标，所以要用map里面套set的方式去求解。在消除某一行的时候自然需要把这一行里面列相关的给消除掉，毕竟题上说了死人不能再死一次。让我奇怪的是得要用multiset？难道有可能在一个坐标处建立...

C++ stl

2023-09-14

4 297

题解 | #[JSOI2007]建筑抢修#

先按照最晚修理时间进行排序，从最早的开始进行遍历。进来后如果可以达到最晚修理时间那么直接加入即可，如果达不到的话，与我已有的建筑的修理时间进行比较如果修理时间比原有的小的话那么就需要对原来的建筑进行一个调整，如果大的话不变就行，总之是一个一换一的过程，但同时也为后面腾出了更多的修理时间，所以贪心成立...

C++ 贪心堆(优先队列)

2023-09-14

2 369

题解 | #tokitsukaze and Soldier#

本题是一个可后悔的贪心，首先从简单来看，如果单纯根据战力选择可能会因为人数现在而没有达到最优，如果根据人数限制选择，可能会出现极端战力导致错误。但如果两个条件其中之一我们已知的话求解起来就比较简单了，如果我们已知人数限制，那么只需要在所有人数限制超过这个的人里面选最好的几个就行了。这看起来很...

C++ 贪心堆(优先队列)

2023-09-14

2 297

题解 | #[JSOI2010]缓存交换#

本题是一个贪心问题，关键在于贪心策略如何选择。想要缺失的可能性尽可能少，首先可能就想到丢掉后面出现次数少的，但比起出现次数顺序更加重要。最后得到贪心策略为：去掉最近的。在本题中算法如何实现也不容器，应当保存下标才方便，否则如果相同的时候会有不必要的麻烦。 #include&nbs...

C++ 贪心

2023-09-14

3 374

题解 | #Running Median#

使用对顶堆可解，左边的堆维护中位数前半部分，右边的堆维护中位数后半部分。在新的数进来的时候判断应该插左边还是右边，然后对左右如果差值超过1进行调整。这样要么左堆的顶端是中位数，要么当左右相同大小的时候就是两个堆顶的数取平均数。 //对顶堆，以左边为承载多出来的那个中间数的堆 #inclu...

C++ 对顶堆优先队列

2023-09-13

3 440

题解 | #第k小#

//建立两个堆，一个大根堆，一个小根堆。从K处劈开 #include <bits/stdc++.h> using namespace std; int n, m, k; const int maxn&nb...

C++ 优先队列堆

2023-09-13

4 335

题解 | #Largest Rectangle in a Histogram#

限制大小的关键在于某一个矩形向左可以到什么地方，向右可以到什么地方。如果可以得知这个长度，再乘以该矩形的高度就是我们所需要的该矩形的最大面积。然后枚举求出所有矩形的最大面积，求最大的那一个就可以了。那么如何去向左和向右寻找最远的地方呢？我们可以将问题转换成找最近的阻挡点，那么就可以使...

C++ 栈

2023-09-12

1 359