Z_L_G

题解

总结(8) 训练赛(3)

/ 注册

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

算法入门-缓存交换

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

贪心堆(优先队列)

2025-03-27

0 16

算法入门-蚯蚓-队列

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

队列

2025-03-24

1 20

算法入门-KMP匹配(模板)

功能在主串中查找子串，返回头位置(0开头索引) 复杂度 n,m为主串和子串长度思路把主串和子串拼接到一起，中间隔开，记为合并串s 对s中的每一个子串计算其最长匹配真前后缀长度，如果有某一个字串的最长匹配真前后缀长度等于子串长度，则说明查找到子串对于每一个子串希望求他的最长匹配真前...

kmp

2025-03-20

0 22

算法入门-01分数规划

定义有n个物品，每个物品有价值和消耗，从其中拿k个，希望使得 ∑价值/∑消耗最大方法设最优解X=∑v/∑c，对式子做变形有∑v-X∑c=0，再变形有∑(v-Xc)=0 易发现这是一个单调式子，故考虑使用二分二分X，每次计算当前X下的(v-Xc)，取前k个求∑(v-Xc)，如果小于0则...

二分答案 01分数规划

2025-03-19

0 21

算法入门-传送带（三分典例）

题意两条传送带AB，CD，给出四个点坐标，在两条传送带和地面上的速度分别为P,Q,R,从A到D的最短时间是多少？思路从AB到CD某点花费满足凹函数，从AB某点到CD花费也满足凹函数，三分套三分 AC代码 #include<bits/stdc++.h> using names...

三分

2025-03-19

0 25

Prac-贪心-土:巨石滚滚

题意 n块小石头，1块大石头，大石头生命值m，撞碎每块小石头先扣除a滴血，然后再回复b滴血，能否使n块小石头在一定的顺序下被吃掉而不死（m<0）思路一个很贪的贪心由于我们希望尽可能撞碎尽可能多的石头，所以第一步贪心是把所有小石头分为三类，先撞使稳定性提升的，再撞使稳定性不变的...

贪心

2025-03-18

0 16

算法入门-第K大和第M大

题意给定一个长为n的数组a，对于他的每个区间拿出他的第K大元素，将所有的第K大元素进行排序，请问其中的第M 大是多少思路转化1：第K大数比X小的区间个数不能超过M-1个转化2：区间中大于等于X的元素超过K个的区间小于M个转化3：二分M，按上述要求检查所有可能的区间转化4：对于找区间...

二分答案

2025-03-17

0 20

算法入门-借教室

题意第i天有Ri个教室可以借出，一共有m次操作，每次操作以（x,y,z）形式给出，代表从y天到z天要借出x个教室，判断教室够不够用，如果不够，输出第一次不够的操作的序号思路正常读入该读入的东西二分第次天会出问题，将这一次前（包含这一次）的操作做完检测有无教室不够 AC代码 #inc...

2025-03-17

0 17

算法入门-Music Notes

题意给定每个点的消耗时间，查询在第t秒的时候位于哪个点思路对耗时做前缀和，查询第一个大于的位置(upper_bound) AC代码 #include<bits/stdc++.h> using namespace std; long long sum[50505]; int ...

2025-03-10

0 21

算法入门-倍增-快速幂原理

对于a^b，可以将b转化为二进制表示（10：1010），故a^b可拆分成a^b1*a^b2*…… 因此记录一个base=a，如果b的对应位为1，ans*=base 最后再给base倍增：base*=a，b位移：b>>=1 #include<bits/stdc++.h> us...

2025-03-10

0 22