【数据结构】Splay树 + 文艺平衡树-程序员宅基地
技术标签： 数据结构
前置知识
二叉树
就是一个长这样的树，树中每个结点都有一个父结点（除了根结点没有父结点）和最多两个子结点，每个结点的左儿子一定比它小，右儿子一定比它大。
这棵树的先序遍历很容易知道就是：1 2 3 4 5 6 7 （根左右）
我们还可以从另一个角度理解先序遍历：把整棵树映射到 x 轴上，也就是把它压扁也就是这样：
先序遍历从左到右读出来就可以了
单旋：左旋 / 右旋
口诀：左旋拎右左挂右，右旋拎左右挂左
图示：
code
void rotate(int x) // 左/右旋 把编号为x的结点往上旋
{
int y = fa[x], z = fa[y];
int k = check(x); // k表示x是y的什么儿子
ch[y][k] = ch[x][k ^ 1], fa[ch[y][k]] = y;
ch[x][k ^ 1] = y, fa[y] = x, fa[x] = z;
if (z) ch[z][ch[z][1] == y] = x; // 如果结点z存在的话，更新其儿子为x
pushup(y), pushup(x);
}
主要内容
定义
后续代码全部基于下方定义：
int idx;
int root; // 根结点编号
int ch[N][2]; // 子结点 左0右1
int fa[N]; // 父结点
int val[N]; // 结点权值
int cnt[N]; // 权值个数
int sz[N]; // 子树大小
基本操作
void pushup(int x) // 更新编号为x的结点的子树大小
{
sz[x] = cnt[x] + sz[ch[x][0]] + sz[ch[x][1]];
}
int check(int x) // 判断编号为x的结点是其父结点的左儿子还是右儿子 左0右1
{
int f = fa[x];
return ch[f][1] == x;
}
双旋（伸展）
假设我们每次都要将最下层的结点挪到根结点，对于三个结点的组合，有以下四种双旋方式，其中对于一字型的调整也叫做同构调整，对于之字形的调整叫做异构调整
zig-zig
对于这样的一字型，且向左边，我们采用两次右旋
zag-zag
对于这样的一字型，且向右边，我们采用两次左旋
zig-zag
对于这样的之字形，大于号形状，我们采用先对蓝色结点右旋，再对根结点左旋
zag-zig
对于这样的之字形，小于号形状，我们采用先对蓝色结点左旋，再对根结点右旋
code
void splay(int x, int &goal) // 把编号为x的结点旋到编号为goal的结点的位置
{
int f = fa[goal];
while (fa[x] != f) // 如果x的父结点是原先goal的父结点说明已经旋到了
{
if (fa[fa[x]] != f) // 需要进行双旋
rotate(check(x) == check(fa[x]) ? fa[x] : x); // 链字形就旋x的父结点 之字形就旋x
rotate(x); // 第二步一定旋x
}
goal = x;
}
寻找值为x的结点编号 find
int find(int x) // 寻找值为x的结点编号
{
int cur = root;
while (val[cur] != x) cur = ch[cur][x > val[cur]];
return cur;
}
插入 insert
找到该插入的位置，然后再把这个结点splaying到根结点
void insert(int x) // 插入值为x的结点
{
if (!root) // 根结点为0说明整棵树都不存在 建树
{
root = ++ idx;
val[root] = x;
cnt[root] = 1;
pushup(root);
return;
}
int cur = root, f; // cur是当前结点 f是cur的父结点
while (cur && val[cur] != x)
f = cur, cur = ch[cur][x > val[cur]];
if (!cur) // 原树中不存在值为x的结点 需要自己创建
{
cnt[++ idx] = 1;
val[idx] = x;
fa[idx] = f;
ch[f][x > val[f]] = idx;
pushup(idx);
splay(idx, root); // 创建完把这个结点旋到根结点
return;
}
else // 原树中存在值为x的结点 更新信息
{
++ cnt[cur];
pushup(cur);
splay(cur, root); // 把更新后的结点旋到根结点
}
}
删除 del
先把要删除的结点splaying到根结点，然后：
- 如果根结点没有右子树（也就是没有后继（也就是根结点就是最大值）），那么直接删掉即可，也就是把根结点变成当前根结点的左儿子
- 如果根结点有右子树（也就是有后继），就递归找到根结点的后继（也就是从根结点开始，先往右走一步，再一直往左走），把后继splaying到根结点的右儿子，此时这个后继一定没有左子树（因为有左子树，后继就会是左子树里的值），我们要删去根结点，直接让根结点的右儿子的左儿子指向根结点的左儿子即可
code
void del(int x) // 删除值为x的结点
{
int cur = find(x); // 先找到值为x的结点 记录编号
splay(cur, root); // 把待删除的结点旋到根结点
if (cnt[root] > 1) // 如果值为x的结点不止一个 更新信息
{
cnt[root] -- ;
pushup(root);
return;
}
// 值为x的结点只有一个 需要删除
if ((!ch[root][0]) && (!ch[root][1])) root = 0; // 待删除的结点左右儿子都为空
else if (!ch[root][0]) root = ch[root][1], fa[root] = 0; // 待删除的结点没有左儿子 将它的右儿子变为根结点
else if (!ch[root][1]) root = ch[root][0], fa[root] = 0; // 待删除的结点没有右儿子 将它的左儿子变为根结点
else // 待删除的结点既有左儿子也有右儿子 把该结点的前驱旋到根结点
{
cur = ch[root][0]; // 待删除的结点的左儿子
while (ch[cur][1]) // 一直找待删结点的左儿子的右儿子作为前驱（也就是新的根结点）
cur = ch[cur][1];
splay(cur, ch[root][0]); // 把待删结点的前驱旋到根结点
ch[cur][1] = ch[root][1]; // 把待删结点删掉 结点的右儿子变成新根结点的右儿子
fa[ch[root][1]] = cur, fa[cur] = 0; // 更新新树信息
pushup(cur);
root = cur;
}
}
根据值查询排名
int rk(int x) // 查询值为x的结点排名
{
int cur = find(x); // 找到值为x的结点编号
splay(cur, root); // 把值为x的结点旋到根结点
return sz[ch[root][0]] + 1; // 排名即为根结点左子树的所有结点数加1
}
根据排名查询值
一定一定一定一定一定要注意，需要的是 值 还是 编号
如果需要编号，最后返回cur就可以了！！！！！！
int kth(int k) // 查询第k大的值
{
int cur = root;
while (1)
{
if (k <= sz[ch[cur][0]]) // 查询的结点在左子树中
cur = ch[cur][0];
else
{
k -= (sz[ch[cur][0]] + cnt[cur]); // 减去左子树所有点和当前子树根结点的所有点
if (k <= 0) // 说明第k大的值就是当前子树根结点
{
splay(cur, root); // 把当前子树的根结点旋到整棵树的根结点上
return val[cur]; // 返回第k大的值
}
cur = ch[cur][1]; // 继续往右子树走
}
}
}
查询前驱
int pre(int x) // 找值为x的点的前驱值（也就是小于x的最大值）
{
int ans;
int cur = root;
while (cur)
{
if (x > val[cur]) // 当前结点比x小 更新答案 往大了接着找
{
ans = val[cur];
cur = ch[cur][1];
}
else cur = ch[cur][0]; // 当前结点比x大 往小了找
}
return ans;
}
查询后继
int suf(int x) // 找值为x的点的后继值（也就是大于x的最小值）
{
int ans;
int cur = root;
while (cur)
{
if (x < val[cur]) // 当前结点比x大 更新答案 往小了接着找
{
ans = val[cur];
cur = ch[cur][0];
}
else cur = ch[cur][1]; // 当前结点比x小 往大了找
}
return ans;
}
文艺平衡树
其实整个平衡树都可以理解为一个可以旋转的动态开点线段树，普通平衡树就是不带懒标记的线段树，文艺平衡树就是可以区间修改的、带懒标记的线段树
splay 和 kth 里都要 pushdown ，特别注意 splay 里的 pushdown 需要把 x 上方的点先全都取出来，然后 从上到下 进行 pushdown
模板题即实现一个数组的多次区间翻转
方法是：比如我们要翻转 [l, r]，就把 l - 1 旋到根结点，把r + 1 旋到根结点的右儿子，那么翻转的部分就在r + 1 的左儿子了，我们不暴力翻转，而是在这个结点上打上标记（可以类似理解为线段树的懒标记），需要的时候再下传，最后的翻转结果即为整棵树中序遍历的结果（dfs）
void pushdown(int x)
{
if (lazy[x])
{
lazy[ch[x][0]] ^= 1;
lazy[ch[x][1]] ^= 1;
lazy[x] = false;
swap(ch[x][0], ch[x][1]);
}
}
void reverse(int x, int y)
{
int l = x - 1, r = y + 1;
l = kth(l);
r = kth(r);
splay(l, root);
splay(r, ch[root][1]);
lazy[ch[ch[root][1]][0]] ^= 1;
}
void dfs(int cur)
{
pushdown(cur);
if (ch[cur][0]) dfs(ch[cur][0]);
if (val[cur] != INF && val[cur] != -INF) cout << val[cur] << ' ';
if (ch[cur][1]) dfs(ch[cur][1]);
}
完整代码模板（不含文艺平衡树部分）
int idx; // 当前创建到的结点编号
int root; // 根结点编号
int ch[N][2]; // 子结点 左0右1
int fa[N]; // 父结点
int val[N]; // 结点权值
int cnt[N]; // 权值个数
int sz[N]; // 子树大小
void pushup(int x) // 更新编号为x的结点的子树大小
{
sz[x] = cnt[x] + sz[ch[x][0]] + sz[ch[x][1]];
}
int find(int x) // 寻找值为x的结点编号
{
int cur = root;
while (val[cur] != x) cur = ch[cur][x > val[cur]];
return cur;
}
int check(int x) // 判断编号为x的结点是其父结点的左儿子还是右儿子 左0右1
{
int f = fa[x];
return ch[f][1] == x;
}
void rotate(int x) // 左/右旋 把编号为x的结点往上旋
{
int y = fa[x], z = fa[y];
int k = check(x); // k表示x是y的什么儿子
ch[y][k] = ch[x][k ^ 1], fa[ch[y][k]] = y;
ch[x][k ^ 1] = y, fa[y] = x, fa[x] = z;
if (z) ch[z][ch[z][1] == y] = x; // 如果结点z存在的话，更新其儿子为x
pushup(y), pushup(x);
}
void splay(int x, int &goal) // 把编号为x的结点旋到编号为goal的结点的位置
{
int f = fa[goal];
while (fa[x] != f) // 如果x的父结点是原先goal的父结点说明已经旋到了
{
if (fa[fa[x]] != f) // 需要进行双旋
rotate(check(x) == check(fa[x]) ? fa[x] : x); // 链字形就旋x的父结点 之字形就旋x
rotate(x); // 第二步一定旋x
}
goal = x;
}
void insert(int x) // 插入值为x的结点
{
if (!root) // 根结点为0说明整棵树都不存在 建树
{
root = ++ idx;
val[root] = x;
cnt[root] = 1;
pushup(root);
return;
}
int cur = root, f; // cur是当前结点 f是cur的父结点
while (cur && val[cur] != x)
f = cur, cur = ch[cur][x > val[cur]];
if (!cur) // 原树中不存在值为x的结点 需要自己创建
{
cnt[++ idx] = 1;
val[idx] = x;
fa[idx] = f;
ch[f][x > val[f]] = idx;
pushup(idx);
splay(idx, root); // 创建完把这个结点旋到根结点
return;
}
else // 原树中存在值为x的结点 更新信息
{
++ cnt[cur];
pushup(cur);
splay(cur, root); // 把更新后的结点旋到根结点
}
}
void del(int x) // 删除值为x的结点
{
int cur = find(x); // 先找到值为x的结点 记录编号
splay(cur, root); // 把待删除的结点旋到根结点
if (cnt[root] > 1) // 如果值为x的结点不止一个 更新信息
{
cnt[root] -- ;
pushup(root);
return;
}
// 值为x的结点只有一个 需要删除
if ((!ch[root][0]) && (!ch[root][1])) root = 0; // 待删除的结点左右儿子都为空
else if (!ch[root][0]) root = ch[root][1], fa[root] = 0; // 待删除的结点没有左儿子 将它的右儿子变为根结点
else if (!ch[root][1]) root = ch[root][0], fa[root] = 0; // 待删除的结点没有右儿子 将它的左儿子变为根结点
else // 待删除的结点既有左儿子也有右儿子 把该结点的前驱旋到根结点
{
cur = ch[root][0]; // 待删除的结点的左儿子
while (ch[cur][1]) // 一直找待删结点的左儿子的右儿子作为前驱（也就是新的根结点）
cur = ch[cur][1];
splay(cur, ch[root][0]); // 把待删结点的前驱旋到根结点
ch[cur][1] = ch[root][1]; // 把待删结点删掉 结点的右儿子变成新根结点的右儿子
fa[ch[root][1]] = cur, fa[cur] = 0; // 更新新树信息
pushup(cur);
root = cur;
}
}
int rk(int x) // 查询值为x的结点排名
{
int cur = find(x); // 找到值为x的结点编号
splay(cur, root); // 把值为x的结点旋到根结点
return sz[ch[root][0]] + 1; // 排名即为根结点左子树的所有结点数加1
}
int kth(int k) // 查询第k大的值
{
int cur = root;
while (1)
{
if (k <= sz[ch[cur][0]]) // 查询的结点在左子树中
cur = ch[cur][0];
else
{
k -= (sz[ch[cur][0]] + cnt[cur]); // 减去左子树所有点和当前子树根结点的所有点
if (k <= 0) // 说明第k大的值就是当前子树根结点
{
splay(cur, root); // 把当前子树的根结点旋到整棵树的根结点上
return val[cur]; // 返回第k大的值
}
cur = ch[cur][1]; // 继续往右子树走
}
}
}
int pre(int x) // 找值为x的点的前驱值（也就是小于x的最大值）
{
int ans;
int cur = root;
while (cur)
{
if (x > val[cur]) // 当前结点比x小 更新答案 往大了接着找
{
ans = val[cur];
cur = ch[cur][1];
}
else cur = ch[cur][0]; // 当前结点比x大 往小了找
}
return ans;
}
int suf(int x) // 找值为x的点的后继值（也就是大于x的最小值）
{
int ans;
int cur = root;
while (cur)
{
if (x < val[cur]) // 当前结点比x大 更新答案 往小了接着找
{
ans = val[cur];
cur = ch[cur][0];
}
else cur = ch[cur][1]; // 当前结点比x小 往大了找
}
return ans;
}
例题 P2042 [NOI2005] 维护数列
这题真是毒瘤啊，不过感觉是平衡树的一道非常好的例题，这题如果能自己完完整整敲一遍，splay树至少在代码上就完全没有问题了
注释写的非常详细，参考这篇
#include <bits/stdc++.h>
using namespace std;
#define int long long
using i64 = long long;
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
int idx; // 当前创建到的结点编号
int root; // 根结点编号
int ch[N][2]; // 子结点 左0右1
int fa[N]; // 父结点
int val[N]; // 结点权值
int sz[N]; // 子树大小
int tag[N]; // 赋值标记
bool rev[N]; // 翻转标记
int sum[N]; // 区间权值和
int lt[N]; // 左最大子序列
int rt[N]; // 右最大子序列
int md[N]; // 中最大子序列
int id[N]; // 序号为i的点对应的结点编号
int a[N];
int rub[N]; // 没被使用的编号 后文叫做垃圾桶数组
int top; // 没被使用的编号数组目前用到哪里了
void clear(int x) // 把编号为x的结点删掉
{
ch[x][0] = ch[x][1] = fa[x] = val[x] = sz[x] = rev[x] = sum[x] = lt[x] = rt[x] = md[x] = 0;
tag[x] = INF;
}
int rublish() // 取一个没被用过的结点编号
{
if (top == 0) return ++ idx; // 如果垃圾桶数组里没有数 就取一个新的编号
int cur = rub[top -- ]; // 如果垃圾桶数组里有数 取一个数
return cur;
}
void modify_val(int cur, int v) // 把以cur为根的子树结点值都变成v
{
if (!cur) return; // 已经到叶子
tag[cur] = val[cur] = v; // 打标记 更新cur结点
sum[cur] = v * sz[cur];
lt[cur] = rt[cur] = max(sum[cur], (i64)0);
md[cur] = max(sum[cur], v);
}
void modify_rev(int cur) // 把以cur为根的子树翻转
{
swap(ch[cur][0], ch[cur][1]);
swap(lt[cur], rt[cur]);
rev[cur] ^= 1; // 打标记
}
void pushup(int cur) // 更新cur结点信息（类比线段树）
{
sum[cur] = sum[ch[cur][0]] + sum[ch[cur][1]] + val[cur];
sz[cur] = sz[ch[cur][0]] + sz[ch[cur][1]] + 1;
md[cur] = max({
md[ch[cur][0]], md[ch[cur][1]], rt[ch[cur][0]] + lt[ch[cur][1]] + val[cur]});
lt[cur] = max(lt[ch[cur][0]], sum[ch[cur][0]] + val[cur] + lt[ch[cur][1]]);
rt[cur] = max(rt[ch[cur][1]], sum[ch[cur][1]] + val[cur] + rt[ch[cur][0]]);
}
void pushdown(int cur) // 把cur结点的标记下传
{
if (tag[cur] != INF) // 有赋值标记
{
modify_val(ch[cur][0], tag[cur]);
modify_val(ch[cur][1], tag[cur]);
tag[cur] = INF; // 取消标记
}
if (rev[cur]) // 有翻转标记
{
modify_rev(ch[cur][0]);
modify_rev(ch[cur][1]);
rev[cur] = 0; // 取消标记
}
}
int check(int x) // 判断编号为x的结点是其父结点的左儿子还是右儿子 左0右1
{
int f = fa[x];
return ch[f][1] == x;
}
void rotate(int x) // 左/右旋 把编号为x的结点往上旋
{
int y = fa[x], z = fa[y];
int k = check(x); // k表示x是y的什么儿子
ch[y][k] = ch[x][k ^ 1], fa[ch[y][k]] = y;
ch[x][k ^ 1] = y, fa[y] = x, fa[x] = z;
if (z) ch[z][ch[z][1] == y] = x; // 如果结点z存在的话，更新其儿子为x
pushup(y), pushup(x);
}
void splay(int x, int &goal) // 把编号为x的结点旋到编号为goal的结点的位置
{
int f = fa[goal];
while (fa[x] != f) // 如果x的父结点是原先goal的父结点说明已经旋到了
{
if (fa[fa[x]] != f) // 需要进行双旋
rotate(check(x) == check(fa[x]) ? fa[x] : x); // 链字形就旋x的父结点 之字形就旋x
rotate(x); // 第二步一定旋x
}
goal = x;
}
void build(int l, int r, int father) // 把数组a从l到r的所有数建成一棵平衡树 接在father下面（类比线段树的建树）
{
int mid = l + r >> 1;
int cur = id[mid], pre = id[father]; // 取出mid的结点编号和father的结点编号
if (l == r) // 创建结点
{
md[cur] = sum[cur] = a[l];
tag[cur] = INF, rev[cur] = 0;
lt[cur] = rt[cur] = max(a[l], (i64)0);
sz[cur] = 1;
}
if (l < mid) build(l, mid - 1, mid); // 创建左子树
if (r > mid) build(mid + 1, r, mid); // 创建右子树
// 更新当前结点
val[cur] = a[mid];
fa[cur] = pre;
tag[cur] = INF;
pushup(cur);
ch[pre][mid >= father] = cur;
}
int kth(int k) // 查询第k大的值
{
int cur = root;
while (1)
{
pushdown(cur);
if (k <= sz[ch[cur][0]]) // 查询的结点在左子树中
cur = ch[cur][0];
else
{
k -= (sz[ch[cur][0]] + 1); // 减去左子树所有点和当前子树根结点的所有点
if (k <= 0) // 说明第k大的值就是当前子树根结点
{
splay(cur, root); // 把当前子树的根结点旋到整棵树的根结点上
return cur; // 返回第k大的值
}
cur = ch[cur][1]; // 继续往右子树走
}
}
}
void remove(int cur) // 把以cur结点为根结点的子树删掉（这些结点编号放进垃圾桶数组里重复利用）
{
if (ch[cur][0]) remove(ch[cur][0]); // 删左子树
if (ch[cur][1]) remove(ch[cur][1]); // 删右子树
rub[++ top] = cur; // 删本身
clear(cur);
}
// 要修改 [k, k + len - 1] （因为放进了正无穷和负无穷，所以实际上要修改 [k + 1, k + len]）
// 把第k个结点旋到根结点 第k+len+1个结点旋到根结点的右儿子
// 需要修改的部分就是根结点的右儿子的左儿子
int split(int k, int len)
{
int x = kth(k), y = kth(k + len + 1);
splay(x, root), splay(y, ch[root][1]);
return ch[y][0]; // 返回根结点的右儿子的左儿子编号
}
int query(int x, int len) // 返回[x, x + len - 1]的总和
{
int cur = split(x, len);
return sum[cur];
}
void update(int x, int len, int v) // 把[x, x + len - 1]的值全部变成v
{
int cur = split(x, len), y = fa[cur];
modify_val(cur, v);
pushup(y), pushup(root);
}
void reverse(int x, int len) // 翻转[x, x + len - 1]
{
int cur = split(x, len), y = fa[cur];
if (tag[cur] != INF) return; // 如果已经打了赋值标记 翻转之后也是一样的 就可以不翻转了
modify_rev(cur);
pushup(y), pushup(root);
}
void erase(int x, int len) // 删掉[x, x + len - 1]
{
int cur = split(x, len), y = fa[cur];
remove(cur);
ch[y][0] = 0;
pushup(y), pushup(root);
}
void insert(int k, int len) // 在第k个数后面加len个数
{
for (int i = 1; i <= len; i ++ ) cin >> a[i]; // 输入要加的len个数
for (int i = 1; i <= len; i ++ ) id[i] = rublish(); // 取len个编号出来
build(1, len, 0); // 要加的数先创建成一棵平衡树
int z = id[1 + len >> 1]; // 新建的平衡树的根结点
int x = kth(k + 1), y = kth(k + 2); // 要在xy之间插入新建的平衡树
splay(x, root), splay(y, ch[root][1]); // 把x旋到根 y旋到x的右儿子 新建的数放到y的左儿子
fa[z] = y, ch[y][0] = z;
pushup(y), pushup(x);
}
void solve()
{
int n, m;
cin >> n >> m;
md[0] = a[1] = a[n + 2] = -INF;
for (int i = 2; i <= n + 1; i ++ ) cin >> a[i];
for (int i = 1; i <= n + 2; i ++ ) id[i] = i;
build(1, n + 2, 0);
root = (n + 3) >> 1;
idx = n + 2;
while (m -- )
{
string s;
int x, len, y;
cin >> s;
if (s == "MAX-SUM") cout << md[root] << '\n';
else cin >> x >> len;
if (s == "INSERT") insert(x, len);
else if (s == "DELETE") erase(x, len);
else if (s == "MAKE-SAME")
{
cin >> y;
update(x, len, y);
}
else if (s == "REVERSE") reverse(x, len);
else if (s == "GET-SUM") cout << query(x, len) << '\n';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
}
智能推荐
Openmesh函数库设计及与CGAL的对比_openmesh和cgal-程序员宅基地
文章浏览阅读4.7k次。Openmesh函数库设计及与CGAL的对比在前面写了CGAL模板类设计的一些思路,这里尝试写一点openmesh库的设计思路以及和CGAL的对比.虽然OPENMESH代码量小，不过还是只看懂皮毛，很大部分算是翻译帮助文档吧，主要用作笔记，方便以后继续分析。相对CGAL的功能强大和庞大（包含大量计算几何算法的实现），Openmesh显得更加小巧轻量化，它更专_openmesh和cgal
常用验证函数-程序员宅基地
文章浏览阅读1.1k次。//函数名：chksafe//功能介绍：检查是否含有"",//,"/"//参数说明：要检查的字符串//返回值：0：是 1：不是function chksafe(a){ return 1;/* fibdn = new Array ("" ,"//", "、", ",", ";", "/"); i=fibdn.length; j=a.length; for (ii=0;ii { for (
关于C语言编译的可执行文件 exe 发给好友解决办法 Visual Studio 2013 版本_将c语言可执行程序发给别人-程序员宅基地
文章浏览阅读3.2k次，点赞2次，收藏14次。下面展示一些 内联代码片。前提是用的 Visual Studio 工具你是不是把 exe 可执行文件发给好友之后，好友打开是这种情况？下面展示一些 内联代码片。就解决办法：然后_将c语言可执行程序发给别人
mysql运行报错64bit_关于MySQL5.6.25在Win7 64bit下重装后无法启动的解决方法-程序员宅基地
文章浏览阅读340次。在重装MySQL5.6.25安装到进行配置的时候，一直在等待服务的启动。如果手动在系统服务启动会提示1067错误，这个错误在网上很常见，然而我试过了很多方法均无法解决。于是看ProgramData\MySQL Server 5.6\data下的 ***.err 错误日志，看出错的部分：2015-06-04 13:08:19 5200 [Warning] InnoDB: Doublewrite do..._windows [error] innodb: header page consists of zero bytes in datafile: .\ib
小李跟同桌说，他发现了一个免费学Python的地方，非广告 | Python技能树测评-程序员宅基地
文章浏览阅读1.9w次，点赞2次，收藏2次。Python 技能树，真免费学 Python
UOJ449 集训队作业2018 喂鸽子_uoj449 喂鸽子-程序员宅基地
文章浏览阅读671次。ProblemUOJ看题后：boshi：这是一道简单题队长：这题好像不难，感觉和猎人杀有点像我：Solution感觉自己越来越菜了，再这样下去，要是正式考试送温暖岂不是连温暖都拿不到了。。一脸min-max反演的样子，由于每个鸽子都等价，枚举子集大小 iii 即可ans=∑i=1n(ni)(−1)i+1nif(i)ans=\sum_{i=1}^n\binom n i(-1)..._uoj449 喂鸽子
随便推点
Java连接Redis存取数据(详细)_redis导入导出数据java-程序员宅基地
文章浏览阅读6.5k次，点赞4次，收藏30次。Java连接Redis存取数据一.相关工具二.准备工作1.启动redis2.外部连接测试3.新建连接。4.连接成功三.新建jedis项目1.新建项目2.命名项目3.引入相关jar包4.引入 junit5.新建包com.redis.test四.编写代码1.redis.properties : redis连接配置文件2.RedisPoolUtil : 连接池配置工具3.SerializeUtil : ..._redis导入导出数据java
android dialog自定义布局 圆角背景 点击空白处不关闭 设置dialog大小-程序员宅基地
文章浏览阅读748次。1.首先上布局文件<?xml version="1.0" encoding="utf-8"?><LinearLayout ="http://schemas.android.com/apk/res/android" android:orientation="vertical" android:layout_width="300d
【算法】从记忆化搜索到递推——动态规划入门_记忆化搜索和递推-程序员宅基地
文章浏览阅读311次。本文的题目其实都比较简单，但是为了学习记忆化搜索，还是要用记忆化搜索再做一遍，不要眼高手低。由于 dp 数组的无后效性，因此还可以将 dp 数组优化成两个变量。将大问题分解成子问题，即 dfs (i) 可以分解成 dfs (i - 1)对于简单的 dp 题，直接写 dp 还更简单一些，硬写记忆化搜索还有点难。因为——有些动态规划直接去想递推公式太难了，所以可以先写成记忆化搜索。由于记忆化搜索是从将大问题分解成子问题的角度去考虑的，所以会简单一些。如果读者觉得本文的题目太简单了，可以去尝试一下。_记忆化搜索和递推
2021-07-12嵌入式学习---交叉编译_交叉编译 prefix-程序员宅基地
文章浏览阅读336次。1、交叉编译交叉编译是在一个平台上生成另一个平台上的可执行代码。同一个体系结构可以运行不同的操作系统；同样，同一个操作系统也可以在不同的体系结构上运行。举例：我们在Ubuntu上面编写树莓派的代码，并编译成可执行代码，如a.out，是在树莓派上面运行的，不是在Ubuntu Linux上面运行。2、为什么要交叉编译1.有时是因为目的平台（C51）上不允许或不能够安装我们所需要的编译器，而我们又需要这个编译器的某些特征；2.有时是因为目的平台上的资源贫乏，无法运行我们所需要编译器；3.有时又是因为目的_交叉编译 prefix
使用java Future模式异步调用详细实例展示-程序员宅基地
文章浏览阅读821次。java Future模式想必大家都比较熟悉，大体实现起来也比较简单，因为模式单一，我先介绍一下一般步骤，再讲一下，目前项目中遇到具体问题的解决方式 一般来说，使用java Future模式实现多线程，具体步骤如下， 1.新建一个异步任务类，如 xxxTask 实现 Callable<xxxTask.Result>(或者Runnable<xxx>...
一张图看懂阿里云新发布的物联网设备上云神器——HiTSDB + IoT套件-程序员宅基地
文章浏览阅读276次。HiTSDB +IoT 套件是阿里云专门为物联网领域的开发人员推出的，目的是帮助开发者搭建安全性能强大的数据通道，方便终端（如传感器、执行器、嵌入式设备或智能家电等等）和云端的双向通信。全球多节点部署让海量设备在全球范围都可以安全低延时接入阿里云IoT Hub，在安全上提供多重防护保障设备云端安全，在性能上能够支撑亿级设备长连接以及百万消息并发。阿里云..._hitsdb +iot 套件