Z_L_G

题解

总结(8) 训练赛(3)

/ 注册

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

算法入门-八数码

题意给定一个九宫格数字状态，询问能否恢复成 | 1 | 2 | 3 | | 4 | 5 | 6 | | 7 | 8 | x | 如果可以输出还原步骤，否则输出unsolvable 思路对状态进行广搜，每次记录当前状态是由什么情况经过什么步骤改变而得到的，最终如果能搜到目标状态，说明可行，反之则...

广度优先搜索队列

2025-04-04

0 16

算法入门-奶酪

题意有一块奶酪，高度为h，内部有n个球洞，半径均为r,问这些球洞能否贯穿奶酪思路使用并查集，合并到顶和底两个大集合中，最后检查顶和底是否在同一个集合注意，和顶部连通的球洞可能同时和底部连通，注意处理方式另一种思路为使用深度优先搜索，看全部搜完后最大深度能否超过h AC代码(并查集)...

并查集深度优先搜索

2025-04-03

0 23

算法入门-幸运数字Ⅱ

题意给定一个区间，将区间中每一个数放大为大于等于它的第一个全部由4，7，组成的数字，然后再求和思路 dfs打表把所有4和7组成的数组打印出来，然后检查区间，输出即可特别的，注意加入0和4444444444，否则lower_bound和upper_bound会出错 AC代码 #inclu...

深度优先搜索打表

2025-04-03

0 25

算法入门-食物链-并查集特殊用法

PS 此题是并查集的一种抽象运用，通过开大空间，将一条逻辑链存到一个合并集合里开眼看世界题意三种动物：a吃b，b吃a，c吃a n只动物，m条信息，信息就两类——ab是同类\a吃b 若一条信息和之前矛盾，则认为新出现的是假信息，求一共有多少条假信息思路最终维护三个集合，每个集合代表...

并查集

2025-03-31

0 18

算法入门-DongDong认亲戚

题意 n个人，m次操作每次操作要么在a,b之间建立亲戚关系，要么查询a，b之间是否为亲戚思路并查集典例，最开始每个结点的父亲是自己，建立，就合并两个，查询就查询 AC代码 #include<bits/stdc++.h> using namespace std; int f...

并查集

2025-03-31

0 18

算法入门-Parity_game-并查集

题意给定长为n的01串，给出m次描述，找出第一次矛盾的描述序号思路将区间值转化为端点值 eg:[5,10]中有奇数个1，说明前4个数中1的个数和前10个数中1的奇偶性不同，也就是前4个数中有奇数个一的时候前10个数有偶数个1 维护一个大小为2n的father数组，当属于1-n表明为奇数，...

并查集 map

2025-03-31

0 18

算法入门-Defeat_Enemy

题意有n支军队，m支敌人，每支军队攻击力比对方高就可以消灭对方，同时减少对方攻击力的防御力，每只军队只能进攻一个敌人，能否消灭所有敌人，消灭敌人后最多剩多少军队思路贪心的思考，在已知敌人防御力的情况下，我们希望存活，所以使用刚刚好大一点的军队，去消灭他，如果最大都不够消灭，就选择防御力最...

贪心 multiset

2025-03-30

0 19

算法入门-滑动窗口

题意给定长为n序列，给定窗口长度k，问所有长为k的区间的最大值和最小值思路单调队列并维护一个队列（以最大值为例），此队列中，队头表示的是当前窗口内的最大值，其他的是可能成为最大值的候选同时，当新入队的元素比之前的元素大的时候，就意味着小的元素再也不可能成为最大值(生命周期没有新入队的...

单调队列双指针

2025-03-28

0 24

算法入门-建筑抢修

题意有n个建筑，每个建筑有修理花费时间t1和deadline t2，最多能修理几个？思路贪心，先修deadline早的或先修时间短的都会有问题早的{(10,10),(3,11),(2,11)} 短的{(1,10),(2,10),(3,3)} 故考虑新的贪心策略，在deadline一定的...

贪心堆(优先队列)

2025-03-27

0 14

算法入门-tokitsukaze and Soldier

题意 n名士兵，每个士兵有v,s，两个值，代表战斗力和包含改名士兵后队伍最大容量，求战斗力最高为多少思路贪心在人数固定的时候贪心选战斗力最高的人从最大人数开始向下枚举，所有能放的都放进小顶堆，然后超出的就弹出，过程中记录最大答案代码 #include<bits/stdc++....

贪心堆(优先队列)

2025-03-27

0 18