xia0ji233's blog

洛谷P6037题解 浅谈基环树(环套树)在题目开始之前，就唠一唠这个叫基环树的结构。准确来说，基环树它已经不是树了，我们知道，树一定是由 $n$ 点和 $n-1$ 条边组成的。而基环树是由 $n$ 点与 $n$ 边组成。但是因为它跟树还是很像，并且在保证连通的情况下有且仅有一个简单环，因此得名。如果不连通，那么它会成为基环树森林。 比如上图就是一个基环树。我们可以很清楚的看出来，点 $2,1,3,7$ 形成了环，断开任意一条属于环中的边都会使这个棵基环树成为树。一般情况下都是将环和环连接的子树进行分开讨论。如何求环呢？我们只需要 dfs 一遍就行了，如果遇到被访问过的点，那就依次返回路径上的所有点，直到我遇到的那个点为止。 举个例子，在上图中，我从 6 开始 dfs，假设它经历了 $6 \to 2 \to 1 \to 3 \to 7$ 的顺序。那么接下来在搜索 7 的时候就会发现与它相连的点 2 已经被访问过，那么我返回值给个 2，依次回溯，回溯过程中将点入栈或者入一个 $vector$ 都可以。直到回溯到 2 这个点为止。环就被我们求出来了。 能求出环我们就会很好做这类的题目 ...

洛谷P2656题解。 题目分析小胖和 ZYR 要去 ESQMS 森林采蘑菇。 ESQMS 森林间有 N个小树丛，M 条小径，每条小径都是单向的，连接两个小树丛，上面都有一定数量的蘑菇。小胖和 ZYR 经过某条小径一次，可以采走这条路上所有的蘑菇。由于 ESQMS 森林是一片神奇的沃土，所以一条路上的蘑菇被采过后，又会长出一些新的蘑菇，数量为原来蘑菇的数量乘上这条路的“恢复系数”，再下取整。 比如，一条路上有 4个蘑菇，这条路的“恢复系数”为 0.70，则第一~四次经过这条路径所能采到的蘑菇数量分别为 4,2,1,0。 现在，小胖和 ZYR 从 S号小树丛出发，求他们最多能采到多少蘑菇。 就是沿线采蘑菇，然后给定起点，没有给终点，蘑菇采完后会复活，复活的个数为上一次的个数×恢复系数。路是单向的，那么可以据此建一个有向图。如果一条边的两个顶点在同一个强连通分量内的话，那么这条边我可以经过无数次，这很容易证明。但是如果一条边的两个点不在同一个强连通分量，那么我只能采一次上面的蘑菇。因为题目没有规定不能反复横跳，所以我们可以先tarjan缩点然后把内部的边权集中到点上，再集中的时候只需要 ...

然后今天来学二分图，首先我们来看看二分图的定义。 二分图的定义首先二分图它是一个图(G)，由点集(V)和边集(E)构成的集合，即G=(V,E)。 除此之外它还满足一个特点，若这个图的点集存在一个划分{V1,V2}使得，任意的e(i,j,w)∈E满足关系，i∈V1,j∈V2或者是i∈V2,j∈V1。那么这个图就被称为一个二分图。 以上是比较数学的说法，而且是自己DIY的(狗头。那说人话就是说，如果你能找到一个合理的方式把点划成两个部分，使得每条边的两个顶点均不同时属于一个部分。那么它就是一个二分图。反之，如果不存在这样的划分满足以上结果，那么它就不是一个二分图。 二分图的一个等价定义是：不含有含奇数条边的环的图。 如果说了这么多让你感觉到还是有一点点难以理解的话，那么我们换一个思路：假设把人比作点，把相爱关系比作边。假设这个人群内没有舔狗(恋情非单向)和男酮，那么它们的关系组成的图就会是一个二分图。时间管理大师(一人同时与多人)不影响它还是一个二分图的，只要没有同就行。不知道这个例子是否够抽象，更易于理解。 举个例子，如下图，它是不是一个二分图？ 判断二分图可 ...

buu刷题记录，actf_2019_onerepeater 分析拿到elf文件checksec一波，无任何保护，栈可执行，那么多半是要把程序流劫持到栈上执行shellcode了，拖进ida里面。 逻辑比较简单，菜单题，然后选项2是明显的格式化字符串漏洞，1选项就是读入0x400字节的数据。首先找到jmp esp的gadget。 有就很好办了，利用格式化字符串改掉返回地址为这个gadget，然后再在后面写一个跳板指令跳到缓冲区内，只要在退出之前把缓冲区写上shellcode就可以很快get shell了。 先通过测试偏移，发现buf在格式化字符串函数的第16个参数。 那么我们先把返回地址劫持了再说，经过调试发现返回地址在buf+0x41c的位置上。 写出部分exp 123456789101112131415jmp_esp=0x08048907# : jmp espfor i in range(4): byte=jmp_esp&0xff jmp_esp>>=8 p.sendlineafter(b'Exit',b' ...

学了这么久堆漏洞了，我想应该把glibc的malloc和free源码解析写一下了，希望能帮助一下刚上路的师傅，同时也巩固一下自身知识。 内存分配我们平时写程序的时候，某些变量可能需要在开始就分配内存，这些内存是不可避免的。那么这些内存就是静态分配的，当程序编译完成之后，它就确定了占用这么多的内存。但是有时候，实际问题的规模没有预期那么大，我们不一定需要很大的内存，如果每次都按最大考虑那么就有很大一部分内存是被浪费的，这就是静态分配内存的弊端，虽然咱打acm的时候都是静态分配的，但是这没啥，因为每个问题不要超过它的总内存上限问题就不大(狗头。但是在内存不足的年代，如果都这样使用静态分配内存的方式，那么计算机的效率会被拖垮很多，所以就有动态分配内存的概念了。 glibc采用ptmalloc的管理方式去分配内存。 ptmalloc2的分配策略那么动态分配内存要怎么去分配呢？如果我们需要占用除了我程序本身占用的内存以外的一块内存，那程序指定是没权限用的，得先向操作系统申请这一块内存的使用权。而操作系统没那么闲，分配几个字节的内存都要它去管，操作系统管理都是按页式的管理。而一页的内存是0x1 ...

谨以此文，纪念我逝去的这6个小时。原本昨天开开心心学学分块，但是入门2就卡住了，卡到生活都不能自理了。 题目分析 题目意思还是很清晰的。要求区间加法，区间查询符合条件的值。至于加法完全可以照搬前一道题目的方式，但是查询的操作着实有点耐人寻味了，因为区间查询意味着我们得采用分块的思想，不能暴力求解。首先我想到让每一个块变得有序，然后lower_bound查到第一个大于等于某个值的第一个元素的位置。首先对所有块排序的复杂度为√n * √n log_2(√n)也就是nlog_2(n)的复杂度，然后每一次查询最多是√n的复杂度，每一次区间加法是√n的复杂度，区间加法还要对固定两个残缺块进行重新排序(因为两边的残缺块可能会破坏有序结构，而中间的则会保持原来的顺序)，这又需要2√nlog_2(√n)的复杂度。查询和加法一起是n√n的复杂度，所以整个算法就是n√n的复杂度，理论可行但是实践可惨死了。 首先，序列排序直接破坏了它的序列结构，这导致我在前一天20点-24点的提交一直不通过。后来我意识到了不能破坏它原有的序列，于是想到每个块用一个vector去保存。更新的时候clear再一个个pus ...

最近cf刷的有点难，请教一位大神，大神曰，“汝之惑，分块也”，所以小菜鸡来学分块了。 数列分块分块是我感觉是最优雅的暴力了，适用于同时区间修改和区间查询，而且书写十分方便。对于动态维护序列的题目我们一般会想到树状数组和线段树结构。 树状数组的限制十分明显，不能同时进行区间修改和区间查询地操作，只能支持单点修改+区间查询或者是区间修改和单点查询。虽然此题可以用树状数组做，但是主要还是练习一下分块。 线段树可以说是非常棒的动态维护序列的数据结构了，时间复杂度非常优秀，但是书写起来十分复杂。 分块也并不是万能的，如果同时区间修改和区间查询且数据范围在1e6的范围，那么分块就很可能超时了，此时只能使用线段树结构去维护这个序列。 各有优缺点吧，主要是分块的这个思想得学会，在很多地方都用得到。 下面给出分块算法中的一些特有名词 区间：数列中连续一段的元素 区间操作：将某个区间[a,b]的所有元素进行某种改动的操作 块：我们将数列划分成若干个不相交的区间，每个区间称为一个块 整块：在一个区间操作时，完整包含于区间的块 不完整的块：在一个区间操作时，只有部分包含于区间的块，即区间左右端点所在的两个 ...

今天来学学AES。 AES简介高级加密标准(AES,Advanced Encryption Standard)为最常见的对称加密算法(微信小程序加密传输就是用这个加密算法的)。对称加密算法也就是加密和解密用相同的密钥，具体的加密流程如下图： 分组问题AES属于分组加密，什么是分组加密呢，顾名思义，分组加密=分组+加密(狗头。分组就是说把它分成一个个组进行加密，可以把它和base64作为一个对比，base64是三个字符一组进行编码，那么既然是要分组那必然也会遇到分组不满的情况，这个时候需要加上填充。这个填充呢，有很多种方案。 零字节填充这个可以说是比较常见的手段了，一般人一般也都能想得到，但是这样的话难以区分末尾的0到底是它的信息本来就存在的还是填充的，信息表达不明确。 填充n位n这个略有点意思。但是假如它本来信息就有n位n呢？那么最后的那n位n还是没办法区分是不是它本来就有的。 那么最终AES采取了哪种填充方式呢？它选择在第二种方案中改进，如果长度刚好不需要填充，那么就填充16位16。这么一来，如果它末尾存在了n位n，但是由于长度满足16的倍数，那么还会填充16位16 ...

继续来学启发式搜索 多的其实没啥好讲了的，因为概念问题在前一篇博文已经讲的很清楚了。主要就是训练寻找估值函数，多点题目练习能应对不通场景下的启发式搜索。 例题洛谷上的p2324骑士精神 题目描述 主要就是说有个空格，然后所有马都走日，没有马脚，只能跳到空格里面去，然后问你是否能在15步以内达到。如果可以则输出最短步数，否则输出-1，因为空格只有一个我们不考虑跳马，考虑跳空格。 递归最大深度15层能确定了，但是任意一个状态可以延伸出最少2中最多八种情况。15作为指数时间上还是遭不住，考虑启发式搜索。那么估值函数需要怎么写呢？ 估值函数这里再补充点估值函数的知识。 f(n)=g(n)+h(n) 估值函数一般表达式如上，g(n)为当前状态，h(n)为未来最优状态产生的花费，或者是其它。估值函数为两者和，由于当前状态我们很容易获取，所以算出未来最优状态即可等于获得了估值函数。可能前面讲的有点小问题，但是还是不妨碍的，因为我们平时写也基本是 123if(f(n)+value>ans){ dfs(n+1);} 所以问题不大。 题目分析在本题中，我们的 ...

来快乐学算法了。 启发式搜索启发式搜索（英文：heuristic search）是一种改进的搜索算法。它在普通搜索算法的基础上引入了启发式函数，该函数的作用是基于已有的信息对搜索的每一个分支选择都做估价，进而选择分支。简单来说，启发式搜索就是对取和不取都做分析，从中选取更优解或删去无效解。 在此之前，本蒟蒻一直就只会dfs和bfs，今天来学学新的搜索算法。经过多重资料的 查阅也是大概得知启发式搜索的大概思路，每次搜索会对之后可能的最优状态估值，如果估出来的值不如当前某些状态，那么我就直接舍弃这个状态。就比如经典01背包问题，我对每一个物品的抉择都有选或者不选两种选择，我发现我不选这个物品，选其它物品所产生的最优解不如我当前选这个解的状态好，那么我直接考虑选择这个而不去搜索不选择这个物品的状态。 估值函数这里需要解释一下我如何判断当前状态是否优于之后的最优状态，那么这里需要这么一个估值函数，估值函数不是真的对那个情况做具体分析，那样的话跟暴力没区别了。我这样考虑，如果剩下所有物品全能放进去都不如我一个放进去价值大，那么我肯定得放这个物品(前提是放得进去，放不进去就别讨论了)。那么这个 ...