小嗷犬

分类

题解(39)

/ 注册

全部文章（共40篇）

西南财经大学·奇点工作室·程序设计部暑期训练营第五次课后习题题解

A. tokitsukaze 与士兵题目链接：A. tokitsukaze 与士兵考察知识点：贪心、优先队列读入每个士兵的信息，按照士兵的 s[i] 值降序排序，然后依次将士兵战力加入优先队列（小根堆），同时维护当前士兵战力之和 cnt，当优先队列大小超过当前士兵的 s[i] 值时，将优先队列...

C++ 深度优先搜索树 LCA 倍增

2023-08-21

2 538

题解 | #漂亮的公园#

考察知识点：树上 DFS、倍增、LCA 设为颜色的两个直径端点（即距离最远的两个点），为颜色中的一个点，则点到颜色中点的最大距离为。可以想象一个点到一条线段的最远距离必然出现在这个点到两个端点的距离中，在此不做严格证明。进而我们有如下结论：设为颜色的两个直径端点...

C++ 深度优先搜索倍增 LCA

2023-08-19

3 521

题解 | #城市网络#

考察知识点：树上 DFS、倍增本题很容易想到模拟的方式，但时间复杂度为，会超时。 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; ...

C++ 深度优先搜索倍增

2023-08-19

3 546

题解 | #Treepath#

考察知识点：树上 DFS 设节点 i 到根节点 1 的距离为节点 i 的长度，记为 dist[i]，则有以下结论：长度为偶数的两个节点之间的路径长度一定为偶数长度为奇数的两个节点之间的路径长度也一定为偶数因此本题我们只需要遍历整棵树，记录每个节点的长度，然后统计长度为偶数的节点数量和长...

C++ 深度优先搜索

2023-08-18

4 540

题解 | #生成树#

考察知识点：生成树本题其实不用建树，对比两棵树的差异即可，当生成树 a 有而生成树 b 没有的边的数量不等于生成树 a 没有而生成树 b 有的边的数量时输出 -1（事实上，可以证明对于两棵节点相同的生成树，这两个值一定相等），否则输出相差边数之和的一半。时间复杂度： #include <b...

C++ 图

2023-08-18

3 473

题解 | #[NOIP2004]合并果子#

考察知识点：贪心、优先队列、哈夫曼树题目翻译一下就是个节点构成一棵二叉树，求这棵树的最小带权路径长度。哈夫曼树是带权路径长度最小的树，所以本题只需要构造一棵哈夫曼树即可。时间复杂度： #include <bits/stdc++.h> using namespace std; ...

C++ 贪心堆(优先队列) 哈夫曼树

2023-08-18

3 594

题解 | #网络优化#

考察知识点：贪心、优先队列读入服务器的信息，按照 (l, r, v) 升序排序，遍历每一位用户，为每一位用户分配符合条件的服务器中 r 最小的服务器，对应的服务器的 v 值减一，若成功为用户分配服务器，则答案 ans 加一。时间复杂度： #include <bits/stdc++.h>...

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

2023-08-18

3 437

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

考察知识点：贪心、优先队列模拟操作系统 MIN/OPT 换页机制，每次换页优先选择未来不会再访问的页或者在最长一段时间不会再访问的页（即当前缓存页中下次最晚访问的页），具体实现请见代码。理论上，MIN/OPT 换页机制是最优的内存换页机制，但是由于需要预知未来的访问情况，所以在实际应用中无法使...

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

2023-08-18

3 463

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

考察知识点：贪心、优先队列读入每个建筑的信息，按照每个建筑修理的截止时间 t2 升序排序，然后依次将建筑修理的时间 t1 加入优先队列（大根堆），同时维护当前建筑修理的时间之和 time，当当前建筑修理完成后的时间大于截止时间时，如果当前建筑所需的修理时间 t1 小于优先队列顶端的建筑所需的修理时...

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

2023-08-18

2 437

题解 | #tokitsukaze and Soldier#

考察知识点：贪心、优先队列读入每个士兵的信息，按照士兵的 s[i] 值降序排序，然后依次将士兵战力加入优先队列（小根堆），同时维护当前士兵战力之和 cnt，当优先队列大小超过当前士兵的 s[i] 值时，将优先队列顶端的士兵战力（即最低战力）从 cnt 中减去，直到优先队列大小不超过当前士兵的 s[...

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

2023-08-18

2 454