Z_L_G

题解

总结(8) 训练赛(3)

/ 注册

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

Prac_前缀和和差分_储物点距离

题意给定若干点和每个点的权值，查询若干次，每次查询输出将给定区间所有点移动到给定点的代价，代价为权值*距离思路肉眼可见的题目数据范围很大，暴力必T就别抱有幻想了差分的给出了坐标，可以求前缀和得到每个点的真实坐标让我们算代价，对代价的公式进行推导：此时，此时我们试图消去...

2025-03-05

1 29

算法入门——最大的半径（bitset）

题意给定若干个点，选哪三个能使得构成三角形的同时，短边长最大思路读入点，把边存入结构体，记录长度和构成边的两个点，按长度排序，遍历边，每次记录每个点连接了哪几个其它点（使用bitset，用01串来记录联的点的个数），直到有一条边两个顶点已经连的点有交集，该边就是最短边 AC代码(注意b...

2025-03-04

0 32

算法入门——起床困难综合征（位运算）

前言位运算往往涉及到拆位思考，有时候每一位达到最优解汇合到一起就是全区最优解，同时位运算可以缩小量级，把一个很大的数处理成一个不超过64位的01串题意选择一个不超过m的数，做k次给定的操作（opt包含OR，XOR，AND），结果最大可能是多少思路对每一位来说无非0，1两种情况...

2025-03-04

0 45

贪心——经典活动安排（套路贪心

题集活动安排国王的游戏保护那些花题意基本都隐含着让最大贡献尽可能小思路贪心来思考，在局部让他对总贡献小，那么在全局就贡献小，这类问题，往往一个单位的贡献情况只取决于自身和前面一位，也就是说，交换自身和前一位对除了这俩以外的部分没有影响，那么便可以进行讨论以保护那些花为例：我...

2025-03-03

0 32

算法入门——给定长度和数列和

题意生成m位所有位和为s的最大数和最小数思路贪心：最大数为前面尽可能放9，最后剩下的不够9的放最后一位。最小数为后面尽可能放9，剩下的放前面，但如果有前导0，就给第一位加1，第一个非零位-1。这时发现，最小数其实就是最大数逆序然后改变前导0的结果注意：三种特殊情况，第一种全放9也凑不够...

2025-03-03

0 41

算法入门——合法字串（双指针）

题意在字符串S中找一个最短字串，使其包含26个字母思路暴力枚举会T 双指针：从头开始扫，更新右界直到扫全，然后更新左界直到缺字母，重复上述过程遍历整个串 AC代码 #include<bits/stdc++.h> using namespace std; int vis[26...

2025-03-01

0 34

算法入门——中位数图&带权中位数

题意给定1~n的排列和中位数b，构造子列使得中位数是b 思路比b大的记为1，小的记为-1，对b左右做后缀和和前缀和，统计每种答案个数，将前后和中互为相反数的相乘 AC代码 #include<bits/stdc++.h> using namespace std; #define...

前缀和

2025-03-01

0 59

算法入门——校门外的树（前缀和和差分）

前言前缀和和差分是一对对称的操作，对前缀和数组差分可以得到原数组，对差分数组前缀和也可以得到原数组题意一条长为L线段等距离分布L+1个点，每次去掉一段中的所有点，去除m次后还剩多少点思路第一种思路：差分查询次数，统计当前点被查询的次数和上一个点被查询的次数的差，再前缀和，可求出...

前缀和差分

2025-03-01

1 38

算法入门——回文日期

题意计数两日期之间的回文日期思路枚举所有年份，构造月份判断是否合法枚举所有月份和日期，构造年月日看是否在区间内但是，构造年份检查月份还要分大小月以及平年闰年，相对麻烦，故构造年月日是更为便捷的解法 AC代码 #include<bits/stdc++.h> using n...

枚举

2025-02-26

0 29

算法入门——最大正方形

题意给定一个由*和#构成的正方形矩阵，求其中以#为顶点的最大正方形，输出四个顶点坐标思路两个点确定一个正方形，三个点确定一个长方形，枚举所有的两个#，check当前两个#构造出的另外两个顶点是否为#，通过边长比较正方形大小注意：计算几何中尽可能避免硬解方程组，多考虑向量和三角函数，本题...

2025-02-26

0 48