Doraemon's Blog

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

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

先排序，两层for循环，二分寻找-(nums[i]+nums[j])，用map去重 时复：O(n2logn) 算上常数差不多9e8左右 刚好超时 寻找能优化的地方 因为排过序了，如果-(nums[i]+nums[j])<nums[j]就没必要找了，加上这句正好卡过去 123456789101112131415161718192021222324252627282930313233343536373839struct node { int a, b, c; bool operator<(const node &o) const { return a == o.a ? (b == o.b ? (c < o.c) : b < o.b) : a < o.a; } node(int ta, int tb, int tc):a(ta),b(tb),c(tc){ };};map<node, bool> vis;class Solution ...

11. 盛最多水的容器 题目所求即为最大面积，面积=(较短边*两线段距离)，答案即为max{以每一条线段作为较短边的最大面积}，当较短边确定时，两线段距离越长越好，因此考虑双指针从两端向内进行移动 考虑以下状态： 两指针在两端时，对于较短边而言，以此线段为较短边的最大面积就是线段长度乘以两指针位置之差，因此较短边对应的指针就可以向前或向后移动了。 移动后的状态又是以上状态。 因此每次较短边指针移动 12345678910111213141516class Solution { public: int maxArea(vector<int>& height) { int i = 0, j = height.size() - 1, res = 0; while(i < j) { res = max(res, min(height[i], height[j])*(j-i)); if(height[i] > height[j]) j -- ...

117. 填充每个节点的下一个右侧节点指针 II 题目有点类似于层序线索化，就是在层序遍历的基础上魔改一下，使得可以获得当前遍历到第几层的信息。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465/*// Definition for a Node.class Node {public: int val; Node* left; Node* right; Node* next; Node() : val(0), left(NULL), right(NULL), next(NULL) {} Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {} Node(int _val, Node* _left, Node* _right, N ...

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) {} * }; ...

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

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; ...

题目 题意让你构造一个序列，满足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/ ...