Z_L_G

分类

总结(9) 训练赛(6) 题解(68)

/ 注册

全部文章（共81篇）

算法入门-DongDong认亲戚

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

并查集

2025-03-31

0 25

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

并查集

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

并查集

2025-03-31

0 25

算法入门-Defeat_Enemy

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

贪心 multiset

2025-03-30

0 24

算法入门-Efficient_Solutions-multiset/map/set比较

题意给定n个点对(x,y)，如果不存在一个点对(a,b),使得(a<=x&&b<y)||(a<x&&b<=y),则称(x,y)是有优势的点对每次加入点对后，输出当前有优势的点对个数思路点对问题转换成二维坐标系中问题画图发现，有优...

multiset set map

2025-03-30

0 31

算法入门-滑动窗口

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

单调队列双指针

2025-03-28

0 41

算法入门-建筑抢修

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

贪心堆(优先队列)

2025-03-27

0 27

算法入门-tokitsukaze and Soldier

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

贪心堆(优先队列)

2025-03-27

0 31

算法入门-缓存交换

题意有一段长为n的整数序列，一个长为m的空间，遍历整数序列，如果空间中没有该元素就需要将该元素加入，如果空间满了就需要移除一些元素，问遍历完整个序列最少需要多少次加入操作思路贪心思考，满了以后移除出现最晚的，因为出现的最晚，所以占位时间长，造成的损失更大如果按照出现次数最多贪心，会发现...

贪心堆(优先队列)

2025-03-27

0 27

算法入门-蚯蚓-队列

题意共有n条蚯蚓，切割m次，每次切当前所有蚯蚓中最长的一条，切割比例为p=u/v，即对于长x的蚯蚓，切成px(向下取整)和x-px两段特别的，长度为0也会被保留同时每次切割后，除了被切割的那一条，其它蚯蚓增长q的长度每切t次输出当前要切的这条蚯蚓的长度，最后输出长度从大到小排名t的整数倍的...

队列

2025-03-24

1 29