Doraemon's Blog

572. 另一棵树的子树 解法一、暴力遍历每一个子树，比较子树是否相同 时复：O(s * t) 1234567891011121314151617181920212223242526272829303132333435363738/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; ...

56. 合并区间双指针，先按照左端点升序排序，对于一个区间，如果可以和后面的合并，则其右端点一定大于后面区间的左端点，且合并后的区间右端点要取两个区间大的右端点，取max，注意边界即可 vector<vector<int>>默认按照第一列的元素从小到大排序，注意如果这里加cmp函数，必须是静态函数，因为sort是全局函数，全局函数不能调用类的成员函数 123456789101112131415161718192021222324252627282930class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { int n = intervals.size(); sort(intervals.begin(), intervals.end()); vector<vector<int>> res; ...

取消拼写检查默认会检查拼写错误，并在下方给予红线提示。 偏好设置->拼写检查->不使用拼写检查 取消自动保存偏好设置->自动保存 取消自动检查更新图像上传路径偏好设置->图像->插入图像时->复制到指定路径->设置图片保存路径 开启markdown扩展语法偏好设置->markdown->markdown扩展语法 代码块显示行号偏好设置->markdown->代码块

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

字典树 作用：快速实现查询某一个字符串是否出现过，类似字符串哈希 时复：O(L) [L:要查询的字符串长度] 空间复杂度：正比于需要插入的字符串总量，比普通数组存储要省空间 大致过程每一个节点代表一个字符，根节点为0，从根节点到叶子节点是一个完整的字符串，实际上就是一个前缀树，两个相同前缀的字符串在字典树上就有一个相同的前缀路径，给每一个节点编一个号，从1开始，用一个二维数组，第一维表示编号，第二维表示字符下标(s[i]-‘a’)，来表示这个编号的节点下有没有这个字符，这样一来省去了相同前缀的空间，而且查询可以每次以O(1)时间查询当前编号下是否有查询字符，需要查询L次，所以是O(L) 例题洛谷模板P2580 题意给定n个字符串，m次询问，每次询问一个给定字符串是否出现过？ 题解两种做法： map trie字典树 CODE12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include <bits/ ...

可持久并查集 前置知识：主席树、可持久化数组 作用：保存历史的集合版本，查询过去版本 空间复杂度>=(klog(n)+2^log(n)^-1) [一般开40倍原空间] 详细讲解 大致过程将fa数组和dep数组可持久化，fa数组就有了各个版本不同的值，如果开结构体的话只需要将fa定义成结构体类型，因为两个数组可持久化后下标是相同的，需要注意的是不能路径压缩，一定要按秩合并！ 题目洛谷模板 题意给定n个集合，每一个集合初始只有自己一个数，接下来m次操作，每次操作有三种选择，合并a和b，回到k版本，询问a和b是否属于一个集合 解法将fa数组和dep数组可持久化，需要注意的是一定不能路径压缩，因为每次要保存版本，只是拉出来一条链，压缩路径的话就会影响其他版本的fa数组值，例如现在高版本压缩了一次路径，低版本的fa数组值被改变了，之后查询低版本时就会出错！如果没有了路径压缩那么时间就会慢很多，所以一定要按秩合并来优化一下，为什么按秩合并会快一点呢？ 看这个图，倘若询问2和4是否在一个集合，第一个畸形图就需要多往上走两步，而第二个图就可以省下些时间。 CODE1234567891011 ...

可持久化数组(可持久化线段树) 前置知识：主席树 作用：记录下历史版本，可以进入历史版本进行修改或者查询 洛谷P3919 题意给定初始版本数组的n个数，之后m次操作，可以查询或者单点修改，每次查询或者修改都会产生一个新版本，查询产生一摸一样的版本，修改会产生一个只有一个位置不同的版本，版本数连续递增，输出每次查询某一个版本的某一个位置的数是几？ 解法原本想用vector开n个表示数组的每一个位置的不同版本，想的是每次只把一个数塞进要修改的ve里，不过这样会有问题。正解是可持续化数组，本质上就是一个保存历史版本的线段树，利用主席树的思想单点修改时只拉出来一条链保存修改过的信息。 CODE123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include <bits/stdc++.h>//#pragma G++ optimize(2)//#pragma G++ optim ...

计算几何皮克定理： 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步的坐标，即使它旋转了，这个坐标也只不过是换了一个角度而已，我们是知道图形的尺寸的，那就可以根据这个尺寸来推出这个点的坐标 CODE123456789101112131415161718192021222324252627282930313233343536#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int,int> pii;const int N=100010;int n,m; pii dfs(int x){ if( ...

主席树(可持续化权值线段树) 可持续化系列的一种数据结构，可以保存修改的版本，本质上是一种可持续化权值线段树 区间第k小倘若不是区间，而是每次求所有值的第k小，一个权值线段树就搞定了，将所有数离散化一下，将数值作为插入位置建树，之后查询第k小时，如果左子树插入点数量大于k就在右子树上，否则就在左子树上，这样就能第k小的数在排好序的数组中排第几个了，每次修改花费logn时间，查询也花费logn时间 而如果现在变成了区间第k小，单纯的线段树就维护不了了，因为无法保存过去的信息，如果可以保存过去没有修改过的信息就好了，（每次修改都建一颗新树，空间炸不炸呀），其实容易想到修改一个点后，变动的点只是这个点的所有祖宗节点（包括父亲节点），只有logn个（n个点的树深度最多是logn），所以可以拉出来一条链来保存修改过的信息 如图，红色的链就是修改过的信息 主席树因为要保存版本信息，无法用2*id表示左孩子那种方式建树，要用朴素的lson和rson数组表示左右孩子 个人理解主席树本质就是前缀权值线段树，权值线段树保存的是每一个区间的值的个数，而主席树就是对每一个前缀都建了一棵树，只不过是优化了 ...