活泼泼

分类

zngg数据结构专题班(6) 题解(21)

/ 注册

全部文章（共27篇）

题解 | #Defeat the Enemy#

2014上海区域赛真题uva一直连不上，下面的代码是我在vjudge上提交的首先，敌人按照防御从大到小排序，先解决防御强的敌人，这里用结构体数组保存就可以了。我方按照攻击力从大到小排序。每次解决防御最强的敌人：先把我方攻击力高于对方防御的人加入集合s，则集合s中的人都是这次行动的可能人选。由于对方防...

multiset

2021-05-17

2 699

题解 | #Efficient Solutions#

源自雨巨的课程ppt首先考虑一下静态的情况：如果给定了n个点，如何求其中优势点的个数？要找一个优势点A，就是以A和原点O为对角点的各边平行于坐标轴的矩形中，没有其他的点。也就是说，如果不存在一个点的x和y都比A小，那么A就是优势点。所以要想找优势点，就是要同时比较x和y的大小。考虑x用于枚举，y用于...

2021-05-16

3 699

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

可反悔的贪心。从小到大对倒塌时长排序，先修快倒塌的（从小到大枚举修理时长）。如果时间不够修当前的楼，就先判断这个楼是否有必要修（修它的用时<修之前楼用时的最大值，就有必要修）。如果没必要就不修，如果有必要就把前面修的时间最长的楼去掉，不去修它。 #include <bits/stdc++...

2021-05-16

0 536

题解 | #tokitsukaze and Soldier#

按照s从大到小排序。先选s大、宽容的人，他能接受的人最多，然后再不断选s小的人。如果人数超了，就把战斗力最低的人踢掉（贪心完的后悔）。这样其实是决定枚举最大人数的人，先找s大的人，就不会对后面有影响，不会出现：我的s满足了，但上一个选进来的人s不满足。这样保证后面来的人能容忍的人少，前面人的s大，不...

堆贪心

2021-04-17

0 492

题解 | #Running Median#

利用对顶堆求中位数我们可以构造两个堆，堆1放小的数，堆2放大的数。堆1为大顶堆，记录这些小的数中的最大者；堆2为小顶堆，记录这些大的数中的最小者。每次输入一个数，只需要把它和小顶堆的最大数比较，若这个数小于堆顶，表明这个数小，就放进小顶堆；若这个数大于堆顶，表明这个数大，放进大顶堆。当输入的元...

对顶堆

2021-04-17

0 473

题解 | #合并果子#

典型哈夫曼树问题方法一：使用小根堆解决 #include <bits/stdc++.h> using namespace std; typedef long long ll; int n; priority_queue<int,vector<int>,greater&l...

最小堆哈夫曼树

2021-04-17

0 694

题解 | #滑动窗口#

用数组du作为单调队列，把对应a中的下标记录下来。l和r分别是数组du的左右界。以求区间最大为例，如果后来的元素更大，则前面比它小的元素就没机会成为最大了，直接去掉。若后来的元素更小，由于位序偏后，可能会成为某个区间的最大。当区间里的数多于k个，就把最前面的元素去掉。最终du对应a中的元素单调下降，...

2021-04-16

0 426

题解 | #Sliding Window#

用数组du作为单调队列，把对应a中的下标记录下来。l和r分别是数组du的左右界。以求区间最大为例，如果后来的元素更大，则前面比它小的元素就没机会成为最大了，直接去掉。若后来的元素更小，由于位序偏后，可能会成为某个区间的最大。当区间里的数多于k个，就把最前面的元素去掉。最终du对应a中的元素单调下降，...

2021-04-16

0 547

题解 | #蚯蚓#

如果x1>x2，那么floor(px1)>floor(px2)，且x1-floor(px1)>x2-floor(px2)因此，可以把原来的蚯蚓、切开后长的蚯蚓、切开后短的蚯蚓分别放入三个队列，每次只需取三个队列中front的最大数，就是当前蚯蚓的最大长度另外为了统一，规定放进队列时...

2021-04-16

3 504

题解 | #好串#

可以把a看成左括号，b看成右括号，这样判断是否为好串就能转化成括号匹配问题方法一：开栈。碰到左括号就入栈，右括号就出栈，使左右括号对应匹配，若有一次栈空（即左括号不够）但还有右括号，则右括号多了，不是好串。最终只要栈空，就是好串，否则不是好串方法二：计数。本题中只有一种括号，因此无需开栈，只需要记录...

2021-04-15

5 1274