Z_L_G

题解

总结(19) 训练赛(6)

/ 注册

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

算法入门-中序遍历

题意给定一个树的先序遍历和后序遍历，求他的中序遍历，无法确定的时候，认为是左子树思路若没有规定左子树，则给定先序和后序是无法确定的，但规定后即可对于先序遍历，第一个点总是当前的根，第二个点总是当前左子树的根对于后序遍历，找到由先序确定的左子树的根的位置，由后续的头到该位置为左子树，由...

2025-03-10

0 40

算法入门-表达式计算（bye逆波兰表达式）

题意对给定的数学表达式，求解其值（包含括号，加减乘除，幂）思路通过递归的方式，每次找到最后一个运算的运算符，然后递归处理该运算符的左边和右边，直到当前区间只有数字，然后将两个递归的结果按照符号处理即可 AC代码 #include<bits/stdc++.h> #define...

模拟栈

2025-03-10

0 37

算法入门-更相减损术（gcd）

题意求gcd 证明对于a和b的最大公因子d a=pd，b=qd 则有c=(p-q)d，使得d为b和c的公因子代码 int gcd(int a,int b){ if(b==0) return a; return gcd(b,a%b); }

2025-03-10

0 39

算法入门-二叉树遍历(模板)

前言通常对于一颗树有四种遍历方式，先序遍历，中序遍历，后序遍历，层序遍历，分别对应着：根左右，左根右，左右根，层（类bfs队列实现）题意存一颗树，输出他的前中后层遍历思路由题意，给定一个节点的父亲和该节点的左右位置，可以使用一个结构体数组来存储对于前三种遍历方式，使用递归即可实...

2025-03-10

0 49

算法入门——归并排序

思路类似于二分的操作，把每一段空间分成两半，直到空间长度等于一（递归实现）合并过程，则对两个区间分别分配一个pointer，比较两个pointer指向的元素，然后存入数组对于每一个片段需要的合并，一共有的层次，所以复杂度为实现代码 #include<bits/stdc++.h>...

2025-03-06

0 43

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

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

2025-03-05

1 45

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

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

2025-03-04

0 44

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

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

2025-03-04

0 57

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

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

2025-03-03

0 52

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

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

2025-03-03

0 58