xia0ji233's blog

今天来复盘一下上次省赛考到的题目，异常地折磨人。 先说一下这题比赛的情况吧，基本上呢，银奖中等偏上的队伍都是做出来了的。 那我们就看看这题吧。 题目简介 什么思路在题目名字这里就一目了然了，那自然是最短路径。 而当我一眼扫过去看到这个数据量的时候瞬间惊呆。$1≤n≤100000，1≤m≤200000$，不仅如此，还有 $q$ 次询问最短路径，$q≤200000$ 当时一看，这玩你妈。给一个点都勉强能过了，这有这么多点，如果按照常规思路，一次单源最短路径复杂度 $nlog_2n$ 然后 $q$ 次询问，总复杂度就是 $qnlog_2n$ 全部以最大值带进去妥妥的超时。所以当时比赛的时候看到这个题目是直接放弃了的，而且英文不好的我留下了悔恨的眼泪。 题目分析但是它还有一个条件，那就是，直接相连的两个点当中，其中一个点的编号一定是另一个点的二进制前缀，这就说明了一点，$2$ 它一定不会跟 $3,6,12……$ 等点连接起来的，因为它们的前缀是 $11_{2}$，而 $2_{10}$ 是 $10_{2}$ 开头的，那么这样的话我们就可以构造一棵 $tire$ 树。像这样子。 可以很明 ...

最近来复习一遍图论的板子——LCA。 概念最近公共祖先（英语：lowest common ancestor）是指在一个树或者有向无环图中同时拥有v和w作为后代的最深的节点。在这里，我们定义一个节点也是其自己的后代，因此如果v是w的后代，那么w就是v和w的最近公共祖先。(fron wiki) 算法设计我们先来看看应该怎么解决此类问题。 一般思路在一个树上，我们定义离根节点最远的与a,b相同的祖先为最近公共祖先(LCA)。我们需要怎么做呢，首先肯定是 dfs 跑一遍，把所有的点的层次遍历出来，时间复杂度为 $O(N)$。一般情况下 $LCA$ 问题会有多次询问，询问次数一般为 $q<10^5$ ，那么就意味着我们不能在线性时间内去计算 $LCA$，如果采取最朴素的方法：选定2个点，若深度不一样则先转为深度一样，深度较深的点不停求它的父亲节点直到深度一样，然后用如下代码去求解。 1234567int LCA(int a,int b){ while(a!=b){ a=pre[a]; b=pre[b]; } r ...

洛谷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 ...