题目翻译:有n个箱子，初始时每个箱子单独为一堆；接下来有p行输入，M x y 或者 C x y 对于M x y：表示将x箱子所在的一堆箱子搬到y所在的那一堆箱子上； 对于C x y表示求箱子x下面有多少个箱子； 输出：在箱子x所在的那堆中，求出在x之下的cube的个数。 大致思路:与题解59一样,又是涉及到合并(M x y)与查询(C x y)的问题,故使用并查集解决.但我们在这里还能使用路径压缩吗?在路径压缩的过程中,会不会影响中间堆放的箱子的个数?当然会,但我们只有开数组,在合并之后,马上记录(更新)某个原来的根节点没被压缩前一路上堆放的箱子数即可,还要时刻记录某一堆堆放了多少个箱子,在合...

思路:并查集模版题 不妨把每个亲友团认为是一个集合,那么并查集中的并即合并两个集合(有共同亲戚的要在同一个亲友团),查即找两个人有没有在一个集合(亲友团) AC代码: #include<iostream> #include<unordered_map>//也可以将所有的unordered_map替换为map,但运行时间有所延长 using namespace std; int fa[20010]; unordered_map<string,int> mp;//将人名映射成数字,因为此处不需要按照顺序遍历元素,所以可以用无序map inline int fin...

题目(翻译来自洛谷) 红队和蓝队在冰面上向目标区域滑动冰壶，距离目标区域中心最近的队伍获胜。 两支队伍在一条直线上竞争。比赛结束后，有 (n+m) 个冰壶在直线上, n 个是红队的，剩下 m 个是蓝队的。 红队的第 i 个冰壶被放在 a_i ，蓝队的第 i 个冰壶被放在 b_i 。 设 c 是中心。如果存在一些 i 使得 1 <= i <= n 并且对于所有 1 <= j <= m 都有 |c - a_i| < |c - b_j| 红队就赢得比赛。另外，如果满足条件的 i 的数目是 p ，则认为红队赢得 p 分。 给你红蓝两队的冰壶的位置，请你确定中心 c 的值，...

题目翻译: 很久很久以前，地球上生活着一个强大的部落。他们经常发动战争，征服其他部落。 有一天，另一个部落成为了他们的目标。这个强大的部落决定要消灭他们！！！ 这个被盯上的部落拥有 m 个村庄，每个村庄都有一支军队，这支军队具备攻击力 EAttacki 和防御力 EDefensei。我们的部落有 n 支军队可以用来进攻敌人，每支军队同样拥有攻击力 Attacki 和防御力 Defensei。我们最多只能用一支军队进攻一个敌人村庄，且一支军队只能用于进攻一个敌人村庄。即便某支军队在一次进攻中存活下来，也不能再用于另一次进攻。 两支军队之间的战斗规则非常简单：双方会同时用各自的攻击力攻击对方。如果...

题目: “我们的婚礼仪式是庄严、清醒的反思时刻;还有遗憾、分歧、争论和相互指责。一旦你知道事情不会变得更糟，你就可以放松并享受婚姻。J.Michael Straczynski，“流星的解构”。半人马座的公主银河系最可辨认的年度单身女郎。她有充满希望的新郎在皇宫的前面，花 5 分钟尝试并给她留下深刻印象。5分钟后，绅士被宫殿卫兵抬出皇家房间，公主做出决定。她通过将他作为两个属性中每个属性的核心来评价拉登的血统年龄和魅力。在 Centauri Prime 上，低分比高分好。假设她观察了两个绅士-A和B。她给A分配了LA和CA的分数（分别是血统和魅力）。B接受分数LB和CB.然后A is 主要由B ...

问题描述 今天，公司有 m 个任务要完成。第 i 个任务需要 xi 分钟才能完成。同时，该任务的难度级别为 yi。级别低于此任务级别 yi 的机器无法完成此任务。如果公司完成此任务，他们将获得 （500xi+2yi） 美元。 该公司有 n 台机器。每台机器都有一个最长工作时间和一个级别。如果任务的时间超过机器的最大工作时间，则机器无法完成此任务。每台机器只能完成一天的任务。每项任务只能由一台机器完成。 该公司希望最大限度地增加他们今天可以完成的任务数量。如果有多种解决方案，他们希望赚到最大的钱。 输入 输入包含多个测试用例。 第一行包含两个整数 N 和 M。N 是机器的数量。M 是任务数（1 ...

问题翻译: 这是一场残酷的战争，杀死了数百万人，摧毁了一系列城市。为了阻止它，让我们轰炸对手的基地。在巷战的情况下， 这似乎不是一项艰苦的工作，但是，你会遇到一个更困难的例子：讲述军队的功绩。在轰炸行动中，指挥官将派出一群轰炸机，其武器具有巨大的破坏力，可以摧毁一排内的所有目标。由于我们间谍的出色工作，所有对手基地的位置都被检测到并在地图上标记，因此，轰炸计划将发送给您。 具体来说，地图表示为一个 2D 平面，上面标有敌方基地的一些位置。轰炸机有条不紊地出动，每架轰炸机都会轰炸地图上的一条垂直线或水平线。然后你的指挥部希望你报告每架轰炸机将摧毁多少个基地。请注意，在计算后来轰炸机的功绩时，不会...

题目翻译: Berland SU 今天为其学生举办了另一场培训比赛。n个 学生来了，每个人都带来了他的笔记本电脑。然而，事实证明，每个人都忘记带充电器了！ 让学生编号从1 自n .笔记本电脑的我 -第个学生负责一个我 在比赛开始时，它使用b我 每分钟的电费（即，如果笔记本电脑有c 在某分钟开始时充电，它变成丙−b我 在下一分钟开始时充电）。整场比赛持续k 纪要。 Polycarp（Berland SU 的教练）决定购买一个充电器，以便所有学生都能顺利完成比赛。他在比赛开始的同时购买了充电器。 Polycarp 可以选择购买具有任何非负（零或正）整数功率输出的充电器。功率输出是在购买前选择的，购...

写了几道题,发现优先队列的题和贪心关系还挺密切 下面两道题都是在贪心,用优先队列来辅助判断是不是有更好的选择,然后后悔原来的元素,选择更好的元素 题解51:https://ac.nowcoder.com/acm/problem/50439 tokitsukaze and Soldier 因为待会能后悔,所以按照要求的高低排序.先选要求高的,待会交换的时候,要求低的总是能交换(相当于减少了一个变量),然后优先去除当前战力最低的,加入新的战士,随后仅用考虑交换后是不是战力更高 AC代码&思路: #include<iostream> #include<queue> #...

前言:这道题目的前面的几个题解写的真的不错,我感觉这道题挺难理解的,需要沉下心思来思考 大的前提:缓存中每个数字的大小范围是1e9级别,不可能用容器直接存下.所以用于标记和比较的容器里存的是第i个数的下标 调度策略:只出现一次的数据,优先级最低,应该最先把这种数据从缓存中移除.其他的数据,出现的越晚优先程度越低.对于时刻更新的缓存,优先程度也是时刻更新的,所以用优先队列来实现 PS:这道题题目对于缓存调度策略的描述不够严谨,要是知道能存下来(知道)接下来要存的数,那就不需要缓存 所以这种调度策略是不可能实现的 AC代码&思路: #pragma GCC optimize("Ofast,n...

题目 对于此问题，您将编写一个读取 32 位有符号整数序列的程序。读取每个奇数索引值后，输出到目前为止收到的元素的中位数（中间值）。 输入 输入的第一行包含单个整数 P（1 ≤ P ≤ 1000），这是后面的数据集数。每个数据集的第一行包含数据集编号，后跟一个空格，后跟奇数十进制整数 M（1 ≤ M ≤ 9999），给出要处理的有符号整数总数。数据集中的其余行由值组成，每行 10 个，用单个空格分隔。数据集中的最后一行可能包含少于 10 个值。 输出 对于每个数据集，输出的第一行包含数据集编号、单个空格和输出的中位数（应为输入值数的二分之一加一）。输出中位数将位于以下行上，每行 10 个，用一...

思路:因为每次只能将两堆合并成一堆(堆数-1),所以合并次数一定是n-1次.那么只要让每次合并消耗的体力值最小即可(永远选择最小的两堆).刚好符合最小堆优先队列 PS:注意stl中的优先队列默认是最大堆,不像sort()默认从小到大排序.想要最小堆,就要使用greater<>,并且在中间还要加上vector,符合STl库中priority_queue<>的传参顺序 AC代码(使用STL): #include<queue> #include<functional> #include<iostream> #include<algor...

题目  直方图是由一系列在公共基线对齐的矩形组成的多边形。矩形的宽度相等，但高度可能不同。例如，左图显示了由高度为 2、1、4、5、1、3、3 的矩形组成的直方图，单位为 1 是矩形的宽度：  通常，直方图用于表示离散分布，例如文本中字符的频率。请注意，矩形的顺序（即它们的高度）很重要。计算直方图中与公共基线对齐的最大矩形的面积。右图显示了所描绘直方图的最大对齐矩形。 输入包含多个测试用例。每个测试用例都描述一个直方图，并以整数 n 开头，表示它由的矩形数。您可以假设 1 ≤ n ≤ 100000 。然后跟上 n 个整数h1...hn，其中 0 ≤ hi ≤ 1000000000。这些数字按从...

题解45:https://ac.nowcoder.com/acm/problem/50528 滑动窗口 这道题是求区间最大值,不是区间和最大值 属于单调队列的应用(模版题?)(与题解47单调队列区分) AC代码&思路: #include<iostream> #include<deque> using namespace std; int a[1000010]; int main() { ios::sync_with_stdio(0);cin.tie(0); int n,k;cin>>n>>k; for(int i=1;i<=n;++...