在刷题的单身狗很开心

题解

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

/ 注册

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

题解 | #Look Up#

类似于滑动窗口，但比滑动窗口要简单。在本题中因为是向坐看（其实是向高下标的方向看）。所以从后向前去遍历，如果栈为空那么直接加入即可，如果当前的数比栈顶的数要大，那么栈顶里面的数不可能成为那个被仰望的了，所以弹出，又因为可能不止一个，所以用循环。如果比栈顶数要小证明还有可能称为那个背仰望的，接着加入栈...

C++ 栈滑动窗口

2023-09-12

2 348

题解 | #Sliding Window#

本题是一个滑动窗口问题，在移动过程中改变的是第一个数被丢掉和下一个数加进来。那么可以建立一个队列，如果当前进来的这个数比前面的某些数要大的话就需要出队，因为由于这个更大的数的存在前面的数就不可能变成最大的数。那么就需要直接从队列里面删除。如果第一个在窗口移动的时候被丢掉了同样也要删除。如果新加进来的...

C++ 双向队列滑动窗口

2023-09-12

1 329

题解 | #[NOIP2016]蚯蚓#

使用优先队列会超时，因为优先队列的内部实现是小根堆或大根堆。并不是O(N)的时间复杂度。在本题当中可以使用三个队列，一个原始序列排序好的队列，一个切完后左边蚯蚓的队列，一个切完后右边蚯蚓的队列。这样只需要每次比较队首的蚯蚓长度就可以得到刽子手需要去砍的蚯蚓。然后本题的输出比较麻烦，需...

C++ 队列

2023-09-11

4 456

题解 | #好串#

和括号匹配一样，左括号压栈右括号与栈顶的左括号匹配出栈，如果中间无法与右括号匹配或最后A有剩余，即为Bad。 #include <bits/stdc++.h> using namespace std; int main() {...

C++ 栈

2023-09-11

0 356

题解 | #栈和排序#

每次都选取尽可能大的即可，一个简答的贪心。所以需要记录后面的最大值，来判断当前是不是有可能的最大的那个数，从而判断值不值得弹出。 #include <bits/stdc++.h> using namespace std; int a[100...

C++ 栈

2023-09-10

0 313

题解 | #Rails#

就是查看出队序列合不合理罢了，只要和数组中的数一致按需出队即可。 #include <bits/stdc++.h> using namespace std; const int maxn = 100000+10...

C++ 栈

2023-09-10

2 360

题解 | #[SHOI2017]期末考试#

//思维还是不够灵活，以前的二分答案基本上都是以题目中要求的入手的。二本题题目所要求的是求总的不愉快度之和最小。 //如果以总和的不愉快度入手的话难以验证是否满足，动不动就从问题出发了。 //看大佬的题解才知道，这道理可以利用的一个固定点在于课程的最晚公布时间，如果最晚公布时间太早可能会因为要调整策...

C++ 三分

2023-09-08

0 336

题解 | #神奇盘子#

题目中情况要么从边界传送，要么直接直接过去。那么就是要求出从边界传送的最短路，由于边界传送的特点，在圆周上是一个凹的函数图形，所以使用三分去求解即可。那么问题就到了如何定三分的左右边界呢？在园的方程里面有一个参数方程。在里面可以从0,2*PI的范围内将圆表示出来。所以通过参数方程即可求解。 ...

C++ 三分几何

2023-09-08

1 459

题解 | #Greedy Gift Takers#

首先可以看出是按照奶牛的编号进行二分去寻找第一个没有礼物的奶牛。但如何验证某个编号的奶牛前面有死循环存在呢。因为是从后面插空的所以会因为后面牛数量的改变而改变。但可以转化到插第几个位置，如果位置2上有两个及其以上的牛的目标都是它，那么就会造成死循环。同样如果3这个位置上有三个及其以上的牛目标...

C++ 二分查找

2023-09-08

1 317

题解 | #小咪买东西#

可以采用二分总价值的方式，已知总价值为x了，那么需要对分数进行价值和/花费和>=0进行变形得：总（价值-x*花费）>=0.势必要贪心的选取价值-x*花费最大的前k个东西。那么就可以得到是否满足。之后二分就行。值得注意的是本题的答案是在实数范围内的。所以采用足够的循环来界定要二分多...

C++ 二分查找 01分数规划

2023-09-07

1 548