xc01

分类

题解(48)

/ 注册

全部文章（共48篇）

题解49 Running Median(POJ 3784)

题目对于此问题，您将编写一个读取 32 位有符号整数序列的程序。读取每个奇数索引值后，输出到目前为止收到的元素的中位数（中间值）。输入输入的第一行包含单个整数 P（1 ≤ P ≤ 1000），这是后面的数据集数。每个数据集的第一行包含数据集编号，后跟一个空格，后跟奇数十进制整数 M（1 ≤ M...

C++ 堆(优先队列)

2025-08-25

0 24

题解48 合并果子(优先队列)

思路:因为每次只能将两堆合并成一堆(堆数-1),所以合并次数一定是n-1次.那么只要让每次合并消耗的体力值最小即可(永远选择最小的两堆).刚好符合最小堆优先队列 PS:注意stl中的优先队列默认是最大堆,不像sort()默认从小到大排序.想要最小堆,就要使用greater<>,并且在中间...

C++ 堆(优先队列)

2025-08-25

0 23

题解47 Largest Rectangle in a Histogram(单调栈)

题目直方图是由一系列在公共基线对齐的矩形组成的多边形。矩形的宽度相等，但高度可能不同。例如，左图显示了由高度为 2、1、4、5、1、3、3 的矩形组成的直方图，单位为 1 是矩形的宽度：通常，直方图用于表示离散分布，例如文本中字符的频率。请注意，矩形的顺序（即它们的高度）很重要。计算直方图中...

C++ 单调栈

2025-08-23

0 27

题解45-46 单调队列与单调栈

题解45:https://ac.nowcoder.com/acm/problem/50528 滑动窗口这道题是求区间最大值,不是区间和最大值属于单调队列的应用(模版题?)(与题解47单调队列区分) AC代码&思路: #include<iostream> #include<...

C++ 单调栈队列栈

2025-08-23

0 31

题解42-44 栈和队列

题解42:https://ac.nowcoder.com/acm/problem/21874 好串思路:a与b要配对,因为是a先b后,而且b是与最近的a配对(插入ab),所以考虑栈有a就入栈,有b就去出栈(与a配对),如果无栈可出,说明配不上对->Bad AC代码: #include<...

C++ 栈队列

2025-08-23

0 20

题解41 Blocks

思路：下降<=>上升两种思路：一. 1.递推中要确定最后一列的积木数量，就一定要直到前一个符合要求的方案最后一列的积木数量，所以用[n块][m列][k最后一列数量]记录求递推关系式，考虑最后一列，若最后一列使用的方块数<k，如从1,2,3,...,k-1，所有的方案...

C++ 状态压缩

2025-08-21

0 25

题解40 小咪买东西

前言：这是一道01分数规划题，要用二分+验证解决。记枚举元素为x，sum(value)/sum(cost)>=x即满足要求,sum(value)-x*sum(cost)>=0;则sum(value-x *cost)>=0 sum()=>最大的前k项加起来 AC代码&思...

C++ 二分查找

2025-08-17

0 23

题解39 [HDU6231] K-th Number

前言：第M大元素，依然可以用二分+验证解决。现在问题是如何验证。记二分枚举元素位x，则应找到>=x的元素大于k的区间个数。因为这种区间的第k大的数在数组b中一定排在x的前面或一块（相等）。如果区间个数>=m，说明枚举的x<=第m大元素，反之，x>第m大元素。注意：二分查找要...

C++ 二分查找数学

2025-08-17

0 40

题解38 [NOIP2012 提高组] 借教室

前言：具有二分性质，在处理到某个人时，教室数量突然就<0，然后就不能再处理请求了。将处理的订单数作为二分枚举对象依旧是一道二分+验证的题,并且同前缀和与差分结合起来（注意：涉及到对区间大量的+-操作，一定不能直接操作，而是要维护一个差分数组，不然时间直接爆表）思路&AC代码： #...

C++ 二分查找前缀和

2025-08-17

0 30

题解37 [CQOI2010] 扑克牌

思路：一道最值问题，故尝试把组成牌的套数当作二分对象，假设需要组成牌的套数过多就一定组不成（有明显的区分点）。故使用二分枚举+验证，现在重点在于如何验证？这要用到抽屉原理的知识。每套牌不能有重复的，则最多一张joker，如果need>套数，则一定有重复的。且给出的joker数量要足够 AC代码...

C++ 二分查找

2025-08-17

0 22