Z_L_G

分类

总结(8) 训练赛(3) 题解(48)

/ 注册

全部文章（共57篇）

算法入门-八数码

题意给定一个九宫格数字状态，询问能否恢复成 | 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

Dfs&&Bfs

Dfs 依赖于栈实现深度优先搜索，回溯，搜不到就回头放置试探性问题需要回溯迷宫类问题不需要回溯 Bfs 依赖于队列实现，预处理完后只要队列不空，就一直循环对每一个路径标注第几步走到

深度优先搜索广度优先搜索

2025-04-03

0 19

Prac-小白月赛113(ABCD)

A 给定一个串，sum初始为1，遇到-，sum-1，遇到*，sum*2，求给定串能否使得sum>=2025 思路直接模拟即可 AC代码 #include<bits/stdc++.h> using namespace std; int main(){ string ...

2025-04-02

0 19

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

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

并查集

2025-03-31

0 17

算法入门-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

并查集

介绍实现集合的合并和查找用树来存储一个集合如果两个点有共同根，就在一个集合里合并只需要把一个点的根放到另一个点的根的下面就行两种优化按秩合并把矮的集合的根放到高的集合的根的下面总能保证深度不超过logn 路径压缩（简单常用）操作复杂度O(logn) 忽视两个点的父子关系，...

并查集

2025-03-31

0 18

算法入门-Defeat_Enemy

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

贪心 multiset

2025-03-30

0 19