PocketCat blog

# 可持久化 01 字典树 作用：实现区间查询异或最大 时复：插入和查询都是 O (logn) # 算法流程 先开一个内存池，动态开点，每次插入一个数都建一个根节点，从根节点拉出一条链，链上的节点一边连向上一个版本的节点，一边连向新插入的点，再开一个 num 数组表示每一个节点经过了几次，查询时当高版本的 num 值大于低版本的 num 值时表示在这个区间内有对应的值，走到最后直接返回即可 # P4735 最大异或和 # 题意 给定有初始值的 n 个数，m 此操作，每次可以选择插入一个数或者查询一个区间内和给定的数异或最大是多少？ # 题解 # 代码 #include...

# 01 字典树 01 字典树：解决最大异或问题 和字典树一样，只不过每一个节点的值不再是字符而是 01，一个数从高位到低位对应于字典树从根到叶子，一个数二进制有多少位，就应该建几层树，包含根节点的那个编号 0 树上的每一个点都有各自的编号，节点有两条边，分别是 0 和 1，开空间时应该多开 40 倍左右 # HDU4825 Xor Sum 题目链接 这道题数据有点水，说是不超过 232，其实连 int 都没有爆，应该开 33 层 (包含根节点)，但是实际上 32 层就可以，代码是开了 33 层 #include <bits/stdc++.h>//#pragma G++...

# 题目 # 题意 让你构造一个序列，满足 m 个位置的前缀异或等于 m 个值 # 题解 先把 p 位置的值定成 x，把每一个定好的位置标记一下，从前往后跑，没有标记过的点就给他定一个比 1e9 要大的数，之所以要比 1e9 要大，是因为要保证定好的位置和它的前一个位置异或不为 0，而定好的位置的值 x<=1e9，输出时，就输出每一个数和前一个数的异或结果 # CODE #include <stdio.h>#include <algorithm>using namespace std;int n , m;int ned[1200000]...

# 字典树 作用：快速实现查询某一个字符串是否出现过，类似字符串哈希 时复：O (L) [L: 要查询的字符串长度] 空间复杂度：正比于需要插入的字符串总量，比普通数组存储要省空间 # 大致过程 每一个节点代表一个字符，根节点为 0，从根节点到叶子节点是一个完整的字符串，实际上就是一个前缀树，两个相同前缀的字符串在字典树上就有一个相同的前缀路径，给每一个节点编一个号，从 1 开始，用一个二维数组，第一维表示编号，第二维表示字符下标 (s [i]-'a')，来表示这个编号的节点下有没有这个字符，这样一来省去了相同前缀的空间，而且查询可以每次以 O (1)...

# 可持久并查集 前置知识：主席树、可持久化数组 作用：保存历史的集合版本，查询过去版本 空间复杂度 >=(klog (n)+2log(n)-1) [一般开 40 倍原空间] 详细讲解 # 大致过程 将 fa 数组和 dep 数组可持久化，fa 数组就有了各个版本不同的值，如果开结构体的话只需要将 fa 定义成结构体类型，因为两个数组可持久化后下标是相同的，需要注意的是不能路径压缩，一定要按秩合并！ # 题目 洛谷模板 # 题意 给定 n 个集合，每一个集合初始只有自己一个数，接下来 m 次操作，每次操作有三种选择，合并 a 和 b，回到 k 版本，询问 a 和 b...

# 可持久化数组 (可持久化线段树) 前置知识：主席树 作用：记录下历史版本，可以进入历史版本进行修改或者查询 # 洛谷 P3919 # 题意 给定初始版本数组的 n 个数，之后 m 次操作，可以查询或者单点修改，每次查询或者修改都会产生一个新版本，查询产生一摸一样的版本，修改会产生一个只有一个位置不同的版本，版本数连续递增，输出每次查询某一个版本的某一个位置的数是几？ # 解法 原本想用 vector 开 n 个表示数组的每一个位置的不同版本，想的是每次只把一个数塞进要修改的 ve...

# 计算几何 皮克定理 ： 2S=2a+b-2 (S: 三角形面积，a 三角形内部点的个数，b 三角形边上点的个数)，求三角形内点的个数 求线段上整数点的个数 ：gcd (abs (x2-x1),abs (y2-y1))+1 判断一个点是否在多变形内部 ：以这个点向多边形顶点做向量，相邻两两做叉积 (左乘右)，若得出的所有结果符号都一样，则在内部 计算多边形面积 ：从原点向多边形顶点做向量，相邻向量做叉积（右乘左）累加求和除以 2 判断一个点是否在两条直线中间...

# ICPC 训练赛 - Philosopher‘s Walk # 题意 如图所示，给定这样的一个 n 阶图形，每次从左下角开始走，问走了 m 步后的位置坐标？ 这个图是有规律可循的，定义 f (i) 是 i 阶图的样子，那么 f (i+1) 就是四个 f (i) 拼成的，上面两个和 f (i) 一样，左下角是 f (i) 顺时针旋转 90 度得到，右下角是 f (i) 逆时针旋转 90 度得到，因此可以定一个 dfs 函数返回的是坐标，不管这个图形是否旋转，我们只求这个图形没有旋转，也就是正着放时走 m...

# 主席树 (可持续化权值线段树) 可持续化系列的一种数据结构，可以保存修改的版本，本质上是一种可持续化权值线段树 # 区间第 k 小 倘若不是区间，而是每次求所有值的第 k 小，一个权值线段树就搞定了，将所有数离散化一下，将数值作为插入位置建树，之后查询第 k 小时，如果左子树插入点数量大于 k 就在右子树上，否则就在左子树上，这样就能第 k 小的数在排好序的数组中排第几个了，每次修改花费 logn 时间，查询也花费 logn 时间 而如果现在变成了区间第 k...

# 马拉车算法 (Manacher) 解决的问题： 以 O (n) 时间求出一个字符串的最长回文子串长度 # 算法流程 如果求最大回文子串，暴力做法是从一个点开始，每次向左和右同时延伸一个单位，比较是否相同，但是这种方式比较难受的是如果字符串长度是偶数，那么可能对称中心不在字符上，而在两个字符之间，如果还想使用上面的方法就必须让指针在字符之间停留一下，所以考虑在每一个字符之间以及开头结尾（开头结尾添加是要让添加字符后的答案和未添加时的答案有一个对应关系）都添加相同的未出现的字符，这里用 "#" 表示，这样一来 aba 就变成了...

# 扩展 KMP 解决的问题： 求解母串以 i 位置开始的后缀子串与模式串的最大公共前缀 时复： O (母串长度 + 模式串长度) 引入两个概念，extend [] 数组表示以母串 i 位置开始的后缀子串与模式串的最大公共前缀，next [] 数组表示模式串以 i 位置开始的后缀子串与模式串的最大公共前缀，一个是模式串与母串，一个是模式串与模式串 与 KMP 类似，都采用了利用之前已经得到的信息来优化当前的时间 # 大致过程 记一个 po 表示起始位置，求解 extend 数组需要先求出 next 数组，而求解 next 数组的过程和求 extend...

# 树链剖分 求解问题：在树上进行区间修改区间查询问题，求 lca 问题，维护路径信息 主要思想：将树上的点分割成一条一条的链，每一条链的第一个点是链头 (父亲)，利用 dfs 序按照链优先的思想加上序号，这样每一条链上面的序号都是连续的，就把树上的点映射到了一条数轴上 时复：找到父亲，重子节点，子树大小（dfs1）O (N)，进行一次 dfs 序 (dfs2 O (N))，每一条路径都能被分割成最多 log2n 条链，因此链头数量不超过 log2n，每次求 lca 时复 logn #...

# 题目 # 题意 从 (1,1) 出发走到 (n,m)，途中有墙有门有钥匙，问最短几步走到右下角。 # 思路 利用状态压缩，用二进制位表示第几种钥匙是否持有，利用 BFS 爆搜，再开一个数组储存状态来记忆化剪枝 实现方法有很多种，可以利用邻接表建边，可以直接利用 Next 数组表示下一个位置，邻接表利用空间换取了时间，表示墙和门时如果不用邻接表，则需要用 map<pair<int,int>,pair<int,int>> 这种结构来表示，而邻接表可以用边权来表示，但都是可以过的 # CODE1...

# 题目 # 题意 如图所示，旋转最少的电线使得左面的电源和发光器相连、 # 思路 考虑把所有电线已经相连的点设为边权为 0，没有连接的，比如电线是主对角线，副对角线上的两个点就应该设为边权为 1，最后跑一个从左上角到右下角的最短路径，将每一个点映射到一维数组中。 dijstla 当然可以做，但是双端队列更高，因为这个图中只有边权为 0 和 1 的点，可以把优先队列的 log (n) 省掉，当遇到边权为 0 的点时就把点直接添加到队头，遇到边权为 1 的点放到队尾，并且判断能否更新当前点离起点的距离。 # CODE #include...

# 题目 # 题意 n 个城市，从 1 到 n 点，有有向边，也有无向边，每个城市都有宝石价格，从一个点买一个宝石，再在后面走的点卖出，问最多赚多少钱？ # 思路 对每一个路径求一个前缀最小值和后缀最大值，对每一个点后缀减去前缀取最大值即是答案，细节就是，求后缀可以反建图，开一个 rhead 数组 # CODE #include <bits/stdc++.h>#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;const int MAXN=500000;const...