WG_17的博客

原创 Linux:44线程互斥lesson32

原则：尽量加锁的范围粒度要细，尽量不要加太多非临界区代码我们用swap,exchange将内存中的变量，交换到CPU的寄存器中“本质是当前线程/进程，在获取锁，因为是交换，不是拷贝，所以1只有1份，所以谁申请到，谁的al > 1,mutex就jiaohuan谁持有锁”锁就是mutex的内容1，谁的%al持有1，谁就持有锁。释放锁，就是向mutex里面写1就可以了。代码3：自动释放锁。

原创 Linux:43线程封装与互斥lesson31

mmap文件映射视屏：待看...

原创 Linux:41线程控制lesson29

1. 如果thread线程通过return返回,value_ptr所指向的单元⾥存放的是thread线程函数的返回值。2. 如果thread线程被别的线程调⽤pthread_cancel异常终掉,value_ptr所指向的单元⾥存放的是常 数PTHREAD_CANCELED。3. 如果thread线程是⾃⼰调⽤pthread_exit终⽌的,value_ptr所指向的单元存放的是传给 pthread_exit的参数。

原创 Linux:42线程控制lesson30

ID:线程控制块的起始地址返回值：线程执行完，的返回值，被join回收分离：joinable = 0线程分离joinable!=0,线程不分离joinable线程标记位。

原创 Linux:40线程理解_页表转换

让我们现在总结⼀下：单级⻚表对连续内存要求⾼，于是引⼊了多级⻚表，但是多级⻚表也是⼀把双 刃剑，在减少连续存储要求且减少存储空间的同时降低了查询效率。有没有提升效率的办法呢？计算机科学中的所有问题，都可以通过添加⼀个中间层来解决。MMU 引⼊ 了新武器，江湖⼈称快表的 TLB （其实，就是缓存） 当 CPU 给 MMU 传新虚拟地址之后， MMU 先去问 TLB 那边有没有，如果有就直接拿到物理地址发到 总线给内存，⻬活。

原创 Linux:39内核与用户--信号-lesson28（待）-未完多个子进程处

DFL:默认。子进程给父进程发送，SIG_CHLD,父进程处理用的是缺省 的ign如果不理解可以认为：两种是不一样的系统默认->僵尸手动默认->可以做到后面的20分钟方案一和方案二。

原创 Linux:38信号捕捉_穿插中断

a.处理信号的合适时机：进程由内核态返回到用户态的时候b.如果是默认/忽略：照常c.捕捉过程，实际上就如右上所示当执行自定义方法的时候，要进行身份切换（由内核态转化为用户态，以免在用户态写一些非法操作需要（内核权限才可以进行的操作））

原创 Linux:35.其他IPC和IPC原理+信号量入门

---------------------------------------------------------------------------------------------------------------------------------这种相似性，叫做system V标准。 ----------------------------------------------------------------------------------------------------------

原创 Linux:37信号lesson26（未完）

信号量集第一个成员*sem.base:起始信号量可以malloc多个信号量sem_nsems:有多少个信号量。

原创 算法基础

原创 图论：多源最短路

1. 状态表⽰： f[k][i][j] 表⽰：仅仅经过[1, k] 这些点，结点i ⾛到结点j 的最短路径 的⻓度。2. 状态转移⽅程：• 第⼀种情况，不选新来的点： f[k][i][j] = f[k - 1][i][j]；• 第⼆种情况，选择新来的点： f[k][i][j] = f[k - 1][i][k] + f[k - 1][k][j]，i->k的路径+k到j的路径之和，把k作为中转点。找以k为中转点，i到j是否存在更小的路径，存在的话，那就更新，不在的话，那就维持原判。

原创 图论：单源最短路（BF算法+迪杰斯特拉算法+spfa算法）

P1629 邮递员送信 - 洛谷。

原创 图论：拓扑排序

拿最大的进行更新，因为大的做完了，小的也就做完了。记录ret:是餐厅里的摄像头，in不为0。加了一个标记要砸坏的bool st[]进队列：是餐厅里的摄像头，并且没有前辈。最短时间，所有情况下，取最大值。

原创 图论：最小生成树

由于克鲁斯卡尔算法要把所有的边进行排序没所以我们要创建一个起点,终点，边的结构体。dfs:把所有的路径都找到。（遍历到一条边就加入路径）瓶颈树：生成所有生成树中，最大边权值最小的那棵树。用胶囊把所有可以到的点统计到。->生成最小生成树。最小生成树：利用dfs找到的路径据生成最小生成树。距离最短->所有距离的总和。--->最小生成树。选边的时候，优先去往高的位置的边，其次才是距离。最小生成树的最大边值也就是最终结果。题目没有明确给出那就自己创建。

原创 图的储存+图的遍历

和树的存储⼀模⼀样，只不过如果存在边权的话，我们的vector数组⾥⾯放⼀个结构体或者是pair即 可。和树的存储⼀模⼀样，只不过如果存在边权的话，我们多创建⼀维数组，⽤来存储边的权值即可。

原创 动态规划：区间dp

k把点分成左右两端，左端的代价，加右端的代价，加把两个合在一起的代价和f[i][j]一起取最小值，即可。把f[i][i] 初始化成0，是根据实际，单独一个不需要合并，代价为0。先全部初始化成无穷大，因为避免取最小值时产生影响。处理环行问题的常见技巧：倍增/复写。

原创 动态规划：背包问题

背包问题是动态规划中最经典的问题，很多题⽬或多或少都有背包问题的影⼦。它的基本形式是：给 定⼀组物品，每个物品有体积和价值，在不超过背包容量的情况下，选择物品使得总价值最⼤。背包问题有多种变体，主要包括：1. 01背包问题：每种物品只能选或不选（选0次或1次）。2. 完全背包问题：每种物品可以选择⽆限次。3. 多重背包问题：每种物品有数量限制。4. 分组背包问题：物品被分为若⼲组，每组只能选⼀个物品。5. 混合背包：以上四种背包问题混在⼀起。

原创 动态规划：经典线性dp

f[i][j]表示：s的【1，i】区间内，以及t的【1，j】区间内，所有子序列中，最长公共子序列。增加：也就是[ i ] 变成 [ j - 1],把b[j] 插入到 [i]后面 ，i++,j不变。跟上面的类似，f[i][j]是指把1-i变成到1-j的最小操作数。a[i] == a[j]相等->那就前面的操作数一样。删除：也就是[ i - 1] 编程[ j ]修改 ：[i- 1] 变成 [ j - 1]到 1~i-1和1~j-1找最长公共子序列。（1）1~i+1~j-1里面拿。根据实际意义进行初始化。

原创 3. 枚 举

include<cstring> ---->memset 和memcpy。0x3f3f3f3f最大。为了更好理解，反着想。

原创 2.高精度

【代码】2.高精度。

原创 1.模 拟

从输出方面考虑：分别从符号，数字，次数考虑按照特殊情况一次分类。

原创 第一章：基础算法

从输出方面考虑：分别从符号，数字，次数考虑按照特殊情况一次分类。

原创 第四章：动态规划

比方说，我们要凑 j = 1,a[i] = 9, a[i]%5 == 4, j - a[i] = -3,我们本来是要找-3的位置的，使得取模 == 1但是我们是找不到的，但是我们可以反向的向前找2,4+2 == 6 ，取模 == 1。4. 输出具体⽅案。f[i][j]表示：s的【1，i】区间内，以及t的【1，j】区间内，所有子序列中，最长公共子序列。选，就找[j - a[i]]的，注意，这里会出现负数的情况，但在这道题中，负数也是有意义的。然后用f[i][j-b[i]]+w[i]替代max的第二部分！

原创 第五章.图论

P1629 邮递员送信 - 洛谷。

原创 动态规划：路径类dp

【代码】动态规划：路径类dp。

原创 动态规划：线性dp

【代码】动态规划：线性dp。

原创 Trie树（字典树）/（前缀树）

注意:（1）在一条边上存字符（2）如果前缀相同的话，就可以实现复用。（3）从根节点出发到某个节点的路径就代表一个字符串（4）有->复用没有->创建（5）维护信息：pass:标记当前节点一共经过多少次end:b=标记当前节点是以多少个字符串作为结尾。

原创 字符串哈希

【代码】字符串哈希。

原创 带权并查集的概念

可以解决路径问题也可以解决扩展域并查集的敌人朋友问题。

原创 扩展域并查集

1 和 2是敌人，那么就把1好12链接起来：表示1和2是敌人2和11链接起来也是这个道理然后2 和3使敌人同理。最后12连接了1 和 3，表名1 和 3 是 2 的敌人，1和3 就是朋友。

原创 并 查 集

初始状态下，所有的元素单独成为⼀个集合：• 让元素⾃⼰指向⾃⼰即可。3.2 查询操作查询操作是并查集的核⼼操作，其余所有的操作都是基于查询操作实现的！ 找到元素x 所属的集合：• ⼀直向上找爸爸~3.3 合并操作将元素x 所在的集合与元素y 所在的集合合并成⼀个集合：• 让元素x 所在树的根节点指向元素y 所在树的根节点。反过来也是可以的）3.4 判断操作3.5 并查集的优化极端情况：在合并的过程中，整棵树变成⼀个链表。 路径压缩：在查询时，把被查询的节点到根节点的路

原创 第三章：单调队列

如果当前a[i] >= a[q.back()],那么把比a[i]小的全部都出队列，然后推进去。根据队头和队尾的下标判断是否超出m;如果 < 那就推进队尾。

原创 第三章：单调栈

记录详情 - 洛谷 | 计算机科学教育新生态int n;int a[N];int ret[N];i <= n;i >= 1;i <= n;

原创 Floodfile

思路：用dfs或者bfs给相同性质的地方打上标记。

原创 广度优先遍历（BFS）

可以用于解决最短路的问题。

原创 1.深度优先遍历

/先判断前面的基本条件，再判断是否存在，就比如说abc都特比特别大，那么就根本找不到对应的f[a][b][c]，就是转化成f(20, 20, 20)如果我们按照 从大到小进行排序的话，那么，一只小猫就会把一个索道尽可能的占满，这样的话，后面的小猫就占不到了，可以对。3.这里进行存取，那么到下一次的，已经遍历过的就已经保存了目标结果，后面几组数据可能以来就可以得到结果。处理已经出现过的情况用到f[N][N],出现过一次就直接返回f[x][y]，这时候必是三。2.主要的处理点，如果两方其中之一为0，返回。

原创 12. 递归

学会从宏观的⻆度看待递归。1. 什么是递归？函数⾃⼰调⽤⾃⼰。2. 为什么会⽤到递归？本质：在处理主问题时，需要解决⼦问题，两者的处理⽅式完全⼀致。问题->相同的⼦问题->相同的⼦⼦问题......直到⼦问题不能继续拆分3. 从宏观⻆度看待递归！1. 不要在意递归的细节展开图---写完代码不要再去纠结递归展开图；2. 把递归函数当成⼀个⿊盒----赋予这个⿊盒⼀个任务；3. 相信这个⿊盒⼀定能帮助我们完成这个任务。

原创 11.离散化

当题⽬中数据的范围很⼤，但是数据的总量不是很⼤。此时如果需要⽤数据的值来映射数组的下标 时，就可以⽤离散化的思想先预处理⼀下所有的数据，使得每⼀个数据都映射成⼀个较⼩的值。之后 再⽤离散化之后的数去处理问题。⽐如：[99, 9, 9999, 999999] 离散之后就变成[2, 1, 3, 4]。

原创 10.倍增

【代码】10.倍增。

原创 8.贪心算法

这种题⽬的解决⽅式⼀般就是按照区间的左端点或者是右端点排序，然后在排序之后的区间上，根据 题⽬要求，制定出相应的贪⼼策略，进⽽得到最优解。⼀般是假设⼀种排序⽅式，并且制定贪⼼策略， 当没有明显的反例时，就可以尝试去写代码。2.交换这两个元素，对前面和后面确定好顺序的序列的结果不造成影响。2.交换这两个元素，对前面和后面确定好顺序的序列的结果不造成影响。舍弃的想法很大胆，也很有风险，但通过证明，就可以表示通过。证明： 按照左端点排序，互相重叠的区间是连续的。按照左端点排序，互相重叠的区间是连续的。