蜡笔小金QAQ的个人主页

浅谈BST前言 最近不顺心的事情有点多，再加上赶ptaL2 的题单，很久没做知识总结了 ，现在pta的题目告一段落，参考了某大佬 （某卷王） 总结的知识点，鸣谢大佬！总结一下BST问题的知识点，供以后参考。 封面： 站在巨人 （卷王） 的肩上，才能看 （卷） 的更远 二叉搜索树的性质 一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点 其左子树中所有结点的键值小于该结点的键值； 其右子树中所有结点的键值大于等于该结点的键值； 其左右子树都是二叉搜索树。 乍一看，其实感觉和二叉堆很像，不过二叉堆左右儿子之间没有可比性，因为二叉堆是根据与父亲节点大小关系建堆的，兄弟节点似乎无法比较，所以同一个序列，以不同顺序输入的生成的二叉堆序列也自然不同。二叉搜索树也有类似的性质，但是二叉搜索树输入的节点不会发生位置交替，这和二叉堆边插入边排序不同，所以，同一组数字不同顺序输入二叉搜索树也会导致二叉搜索树结构不同。假如输入的数字过于玄学，会导致树的左右子树不平衡，如果将两个子树平衡，就变成了平衡树(Treap) 二叉搜索树的操作必要的初始化1234567891011#define ...

浅谈二叉堆前言复习基础数据结构，供日后学习参考吧（放一个封面） 二叉堆二叉堆分为最大堆(大顶堆)和最小堆(小顶堆)，具体区别是： 大顶堆父亲节点永远大于子节点(堆顶元素是最大的) 小顶堆父亲节点永远小于子节点(堆顶元素是最小的) 那么二叉堆如何构建？ 二叉堆建立 大顶堆构建：12345678910111213void big_build(int x) //堆顶下标是1{ b_Heap[++b_Size] = x; int son = b_Size; while (son > 1) { int fa = son >> 1; if (b_Heap[son] <= b_Heap[fa]) break; swap(b_Heap[son], b_Heap[fa]); son = fa; }} 小顶堆构建12345678910111213void small_build(int x) //堆顶下标是1{ s_He ...

浅谈二叉树前言（初级数据结构鲨我）之前寒假集训的时候基础数据结构就学的不太好，很多还是眼高手低，这几天正好开始准备PTA天梯赛的题，L2的题都是这种基础数据结构模拟题，欠账出来都是要还的，今天正好趁着刚学的热乎劲写一下理解，供日后参考 二叉树的三种遍历四种主要的遍历思想为： 前序遍历：根结点 —> 左子树 —> 右子树 中序遍历：左子树—> 根结点 —> 右子树 后序遍历：左子树 —> 右子树 —> 根结点 层次遍历：只需按层次遍历即可对于这个树来说 前序遍历：124753689 123456789void pre_read(node *tree){ if (tree != NULL) { cout << tree->num << " "; pre_read(tree->lchild); pre_read(tree->rchild); }} 中序遍历：742513869 12345678 ...

01背包01背包题目采用一维优化 12345678910111213141516171819202122232425262728#include <bits/stdc++.h>using namespace std;// OJ传送门：https://www.dotcpp.com/oj/problem2131.html// 01背包一维优化// 特点：每个物品只有一个#define maxn 10000int N, M; // N个物品，背包容量Mint value[maxn];int space[maxn];int bag[maxn];int main(){ ios::sync_with_stdio(false); cin >> M >> N; for (int i = 1; i <= N; i++) { cin >> space[i] >> value[i]; } for (int i = 1; i <= N; i++) //枚举编号 ...

之前找了很多博客，想找一个万能的二分板子，始终没有找到合适的，后来找同学大佬要了一个（鸣谢大佬！QAQ），现在将其上传，供日后自己学习使用。 12345678910111213141516int erfen(){ int l = 1, r = n, ans; while (l <= r) { int mid = (l + r) >> 1; if (check(mid)) { ans = mid; l = mid + 1; } else r = mid - 1; } return ans;} 说明： check()函数是当满足查找条件以及向最佳答案压缩的方向返回true，不满足条件返回false l = mid + 1;和r = mid - 1;这两个表达式要根据查找目标在数组的左右情况要调换位置 二分实现查找lower_bound的原理：一定要理解这一段！！！比如我们要查找两个数之和等于目标值，返回一个第一个值最小的组合，当我们找到一个满足和等于目标值的时候，我们不仅要记录这个答案(将 ...

bfs最短路模板最短路+打印路径+记录方向 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108#include <bits/stdc++.h>using namespace std;// bfs路径打印// https://blog.csdn.net/ryo_218/article/details/88830082?spm=1001.2101.3001.6661.1&utm_medium=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1.pc_relevant_paycolumn_v3&de ...

最近正好在学线段树，搞懂后写一篇博客记录一下模板，供日后自己学习参考原题传送门：洛谷线段树模板题经典的RMQ问题，我们用线段树来解决线段树有一般两种写法，一种是结构体写法，还有一种是用堆结构来写本蒟蒻采用堆结构来写实现的操作：区间修改，区间询问。注意，堆写法数组要开原数组的四倍！！！(谨记！此代码已在洛谷AC，可以放心食用 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106#include <bits/stdc++.h>using namespace std;// 洛谷传送门：https://www.luogu.com.cn/problem/P3372// 线段树模板// 区间修改+区间询问#define ma ...

一般大部分人都喜欢用#define来定义代码中的常量，可以让代码更简洁，我原先认为const 和#define定义常量的效果相同，但事实上并非如此 这几天在写一道状压dp的题，无意间发现了关于const和#define定义常量的一些区别：看代码： 12345678910#include <bits/stdc++.h>using namespace std;#define test1 1 << 21const int test2 = 1 << 21;int main(){ cout << "test1: " << test1 << endl; cout << "test2: " << test2 << endl; return 0;} 对于上面的代码，乍一看应该结果是相同的，但是请看运行结果：如此看来，如果用#define来定义位运算得出的常量，得出的答案是错误的 (似乎直接忽略位运算符直接拼接？）但是c ...

第六届蓝桥杯题解前言新蝙蝠侠太好看了！！！姥爷牛逼！！！强推去看！！！！！ 方程整数解这道题可以直接暴力来写，答案有点坑，题目没有说不是负数！答案是 -30 123456789101112131415161718192021#include <bits/stdc++.h>using namespace std;// 传送门：https://www.lanqiao.cn/courses/2786/learning/?id=67081// 答案：-30int main(){ int ans = -1; for (int i = 0; i <= 40; i++) for (int j = 0; j <= 40; j++) for (int z = 0; z <= 40; z++) { if (i * i + j * j + z * z == 1000) { ans = ...

第七届蓝桥杯前言（不会吧不会吧不会吧，不会真有大学生到快到四月都没开学吧）乌丸千岁（💊千岁） 网友年龄直接循环嵌套穷举就好了，没啥好说的 12345678910111213141516#include <bits/stdc++.h>using namespace std;// 传送门：https://www.lanqiao.cn/courses/2786/learning/?id=67636// 循环嵌套int main(){ int ans = 0; for (int i = 0; i <= 9; i++) for (int j = 0; j <= 9; j++) { if (((i * 10 + j) - (j * 10 + i)) == 27) ans++; } cout << ans; return 0;} 生日蜡烛没什么好办法，从0开始枚举开始过生日的可能情况，依次判断就行 1234 ...