Z_L_G

题解

总结(9) 训练赛(6)

/ 注册

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

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

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

二分答案

2025-03-17

0 39

算法入门-借教室

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

2025-03-17

0 27

算法入门-Music Notes

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

2025-03-10

0 35

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

对于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 31

算法入门-平面最近点对（模板）

题意给定若干个点，求最近的两个点的距离思路分治对于所有点，总可以按照以下三种情况处理： 1.只剩下两个点：直接返回两点距离 2.只剩下三个点：返回三个距离的最小值 3.剩下的点超过三个，从中点分开，不断递归至情况一/情况二由此，总能不断地把大区间二分成小区间，并算出区间内最...

2025-03-10

0 65

Prac_前缀和和差分_货物种类

题意 n个点，m次输入，每次输入左界，右界，存储的货物编号求存储的货物种类最多的点思路因为一个点可能重复读入同一个货物，所以使用map并做前缀和开一个map统计每个点存入的货物和次数，全部读入完后，开第二个前缀和map 遍历第一个map中的每一个点，对每一个点，将其中的货物存入前缀和m...

前缀和差分

2025-03-10

0 29

算法入门-中序遍历

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

2025-03-10

0 35

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

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

模拟栈

2025-03-10

0 30

算法入门-更相减损术（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 35

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

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

2025-03-10

0 45