JamhusTao の Blog

前往 算竞题解 分类 || 前往 算竞模板 分类 简介 AVL 是最早发明的平衡树，通过旋转维护任意点的左右子树高度差小于 111，从而实现 O(log⁡n)O(\log{n})O(logn) 的时间复杂度。 模板题链接 洛谷 P3369 【模板】普通平衡树 左旋与右旋 维护二叉搜索树平衡，左旋 (zag) 和右旋 (zig) 是其基本操作。 123456 | | | A B A / \ Zig(A) / \ Zag(B) / \ B [3] ========> [1] A ========> B [3] / \ / \ / \[1] [2] [2] [3] [1] [2] 核心思想 二叉搜索树只有在插入和删除节点时才会改变节点 ...

前往 算竞题解 分类 || 前往 算竞模板 分类 简介 二叉搜索树（BST）用于快速增删改查数据，对外部可以看作一个集合。BST 的平均时间复杂度是 O(log⁡n)O(\log{n})O(logn)，但是遗憾的是其最坏时间复杂度是 O(n)O(n)O(n) 的。为了解决 BST 的这个问题，之后会介绍多种平衡树。平衡树通过不同的维护方式，保证了其始终有 O(log⁡n)O(\log{n})O(logn) 的时间复杂度，BST 是所有平衡树的基础，同时其多数操作在多数平衡树中是通用的。 模板题链接 只有最后一组数据会 TLE。 洛谷 P3369 【模板】普通平衡树 核心思想 ​定义： 对于一棵有根树的任意节点，如果满足左子树所有节点的权值均小于该节点的权值，且右子树均大于该值，则称之为 BST。即对于任意节点 xxx 有权 max⁡{kl}<k<min⁡{kr}\max\{k_l\} < k < \min\{k_r\}max{kl​}<k<min{kr​}，其中 kkk 表示节点 xxx 的权值，{kl}\{k_l\}{kl​} 表示 xxx 左 ...

前往 算竞题解 分类 || 前往 算竞模板 分类 简介 下面介绍一种不常用但是经常被提起的数据结构 —— 笛卡尔树，可以说是平衡树的入门基础。 笛卡尔树既满足二叉搜索树又满足堆，即对于任意键值对 {k,v}\{k,v\}{k,v}，max⁡{kl}<k<min⁡{kr}\max\{k_l\} < k < \min\{k_r\}max{kl​}<k<min{kr​} 且 max⁡{vl}≥v≤max⁡{vr}\max\{v_l\} \ge v \le \max\{v_r\}max{vl​}≥v≤max{vr​}，其中 {kl}\{k_l\}{kl​} 表示左子树中的所有 kkk。 由于笛卡尔树能解决的问题很多都能通过单调栈解决，因此笛卡尔树很少用。 模板题链接 洛谷 P3369 【模板】普通平衡树 HDU 1506 Largest Rectangle in a Histogram （不止一种解法哦） 核心思想 首先我们需要按 kkk 将键值对排序，假设我们将索引当作 kkk 则序列就是已排序的。从左往右遍历即可 O(n)O(n)O(n) 完成笛卡尔 ...

前往 算竞题解 分类 || 前往 算竞模板 分类 简介 平衡树种类众多，各有优劣，其公共功能是完成 O(log⁡n)O(\log{n})O(logn) 的增删改查。本文将介绍 Splay，其优点是代码短，缺点是常数较大。此外，Splay 还可以处理区间翻转问题。Splay 不属于严格的平衡树，但与平衡树有相同的均摊复杂度。 模板题链接 洛谷 P3369 【模板】普通平衡树 核心思想 Splay 的核心为 splay 也是重要的基本操作，只要在完成任何搜索时通过 splay 操作将搜索到的节点旋转到根 ，即可非常神奇地得到 O(log⁡n)O(\log{n})O(logn) 的时间复杂度。 splay 讨论 666 种情况：zig（右旋）、zag（左旋）、zig-zig、zag-zag、zig-zag、zag-zig。 由于左右对称只需讨论其中 333 种情况： zig：完成一次右旋，当且仅当父节点为根，否则考虑后面两种情况。 zig-zig：对祖父节点完成一次右旋，再对父节点完成一次右旋。 zig-zag：对父节点完成一次左旋，再对祖父节点完成一次右旋。 代码虽短，涵盖了上述三种 ...

个人实用小工具项目 | ACMer 一键板子导出工具 cpps2md

前往 小工具指北 分类 这是我的个人开源项目，Github 自取 jamhus-tao/cpps2md，本来是给自己用的，当然也希望帮助更多人。 cpps2md @Jamhus Tao 简介 这是一个 cpp 转 markdown 脚本，主要用于 ACMer 整理板子。如果你不是 ACMer（参与大学生程序设计竞赛的人），这个项目或许对你没有什么帮助。众所周知，ACM 系列赛事允许赛时使用纸质资料，于是每到赛前都需要将之前的练习整理成册打印出来，这是一个繁琐的工作。 通过该工具，你只需要将所有待打印的练习，分门别类地整理到一个文件夹内，运行脚本就可以整理成单一的 Markdown 文件。然后使用你喜欢的方式打印该 Markdown 文件。 本工具为命令行工具，运行窗口简陋，但功能实用。同时支持 .cpp 和 .md 文件格式、支持板子增量式打印。也就是说工具会检测你相较于上一次更改了哪些文件并且只导出它们。 演示 原来的文件夹长这样，其中 .bin 放了我的工具，.out 放了工具导出的文件，其他几个可以无视。 运行脚本导出到 .out 文件夹。 然后我使用 Typora 将它 ...

回到文章目录 修改配置文件 众所周知，网站即 html + css + js，通过修改 css 和 js 我们可以自定义配置我们的主题。 首先修改配置文件，这里建议将需要的所有内容添加到 /css/my.css 和 /js/my.js 。 12345678910# Inject# Insert the code to head (before '</head>' tag) and the bottom (before '</body>' tag)# 插入代码到头部 </head> 之前 和 底部 </body> 之前inject: head: # - <link rel="stylesheet" href="/xxx.css"> - <link rel="stylesheet" href="/css/my.css"> bottom: # - <script src=& ...

建站提交历史文章，原文写作时间 2023 年 2 月前后。 回到文章目录 锁与线程同步 互斥锁 互斥锁概述 互斥锁（mutex）即任一时刻最多允许一个线程独占资源。一把互斥锁最多被一个线程持有，持有互斥锁的线程具有访问和修改资源的权限，否则线程不应继续访问和修改相应资源，阻塞等待互斥锁释放或运行其他代码。 互斥锁实际是对线程是否进入或阻塞在某段代码的控制，而此段代码所涉及的资源不是互斥锁关注的问题，是程序员应当考虑的问题。 互斥锁函数 man文档中找不到以下mutex相关函数。 pthread_mutex_init、pthread_mutex_destroy 1234567891011121314151617#include <pthread.h>// initialize a mutex// mutex:// structure of mutex// mutexattr:// NULL is enough// return value:// ...

建站提交历史文章，原文写作时间 2023 年 2 月前后。 回到文章目录 线程基本操作 编译包含线程函数的程序，需要导入动态库-l pthread。（部分版本会自动导入） 查看线程 查看进程线程 1$ ps -Lf <pid> // 查看 pid 进程线程 获取当前线程号 12345#include <pthread.h>// get the thread identifier// return value:// pthread identifier, always succeedpthread_t pthread_self(void); 比较线程号 123456789#include <pthread.h>// compare thread identifier// t1:// thread identifier 1// t2:// thread identifier 2// return ...

建站提交历史文章，原文写作时间 2023 年 2 月前后。 回到文章目录 线程概述 线程（Thread）本质上是轻量级进程（LWP，Light Weight Process），但与进程拥有不同的行为。在Linux中线程被当作进程进行处理，在原生Linux中并不支持线程。现在Linux操作系统上的线程，大多是Red Hat基于POSIX开发的NPTL（Native POSIX Tread Library）。 线程是轻量级进程。在进程创建时虽然运用写时拷贝技术大幅度减少了拷贝量，但仍然需要拷贝PCB中诸如虚拟内存映射表以及文件描述符表中的数据；线程共享PCB，这意味着线程创建时拷贝的数据量很小，创建线程的开销通常是进程创建的1/10或者更少。 线程依然具有不共享资源： 线程号与线程的实时调度策略与优先级 信号掩码 线程特有数据 errorno变量（线程操作中，errorno通过函数返回，而非设置全局变量） 栈空间与.text空间（线程运行在函数体中，因此外部无法访问函数体数据与代码） 与进程不同地，进程拥有父子关系构成的复杂进程树结构，而线程仅拥有主线程与子线程的二 ...