首页 > 其他分享 >【持续更新】平衡树笔记

【持续更新】平衡树笔记

时间：2024-07-11 08:58:00浏览次数：6  
标签：lc val int tree 更新 fa 笔记 nid 平衡

目录

1 从 BST 到平衡树

众所众知，二叉搜索树（BST）是一棵能方便实现插入、删除，找前驱、后驱，按排名找数、找数的排名的数据结构，但是在构造数据下，ta 的单次复杂度甚至有 \(O(N)\)。因此，平衡树就登场了，ta 的单次复杂度仅为 \(O(\log N)\)。
map/set 等 STL 的实现方式也是平衡树的一种——红黑树。

2 替罪羊树

2.1 替罪羊树的维护

替罪羊树就是比较优雅的暴力啦。
众所周知，一棵树不平衡了怎么办？重建呗（反正对于不同的二叉搜索树，其中序遍历不变）。例如：
在这里插入图片描述
中序遍历：\([1,2,3,4,5,6]\)。
重建：在这里插入图片描述
此时，该 BST 就平衡了不少。
那么，我们只要在该树不平衡时，重建就可以了。
设某树的左子树有 \(lsize\) 个点（包括未删除的点，下同），右子树上有 \(rsize\) 个点，我们定义该树的不平衡率为 \(\alpha'=\dfrac{\max(lsize,rsize)}{lsize + rsize}\)。
显然，\(0.5 \le \alpha' \le 1\)（两种极端情况分别为：左右子树节点数相等、左右子树其中有一个子树为空），且 \(\alpha'\) 越大，该树越不平衡。
所以，我们只要设定一个阈值 \(\alpha\)，使得某树不平衡率 \(\alpha' > \alpha\) 时重建即可。
一般来说，\(\alpha\) 为 \(0.7\) 或 \(0.75\)。
还有一种情况，替罪羊树的删除是打标，而不真正删掉，所以当删除的节点个数为 \(del\)， \(\dfrac{del}{lsize + rsize} > \beta\) 时，也要重建。
同样的，一般来说，\(\beta\) 为 \(0.3\)。

2.2 替罪羊树的基本操作

2.2.1 替罪羊树的结点信息

lc、rc：左右儿子。不存在则为 \(-1\)。
fa：父亲。
val、cnt：结点的值及个数。
nodesize、avsize、numsize：该子树的总结点数目、未打标（也就是未删除）结点数目、存储的数字个数（也就是 \(\sum cnt\)）。
del：是否被删除。
root：树根。空树则为 \(-1\)。

    struct tNode
    {
        int lc, rc, fa, val, cnt, nodesize, avsize, numsize;
        bool del;
    }tree[N << 1];
    int root;
    Scapegoat_Tree() { root = -1; }

2.2.2 替罪羊树的空间利用

由于替罪羊树删除为打标，因此替罪羊树的空间利用是一个问题。
所以定义内存池（用栈实现）mem，使用 newmem 函数来新建节点，返回新结点的编号。用 used 表示到现在为止使用过（包括已删除）的结点的编号，inst 表示栈中结点数目。

    int used, inst;
    stack<int>mem;
    int newmem()
    {
        if(inst > 0) // 栈非空，弹出栈顶
        {
            inst--;
            int top = mem.top();
			mem.pop();
			return top;
        }
        return ++used; // 否则再建一个节点
    }

2.2.3 替罪羊树的重建

首先，最基础的，对于已知的位置，初始化点。

    void Add_Node(int nid, int val, int fa)
    {
        tree[nid].fa = fa, tree[nid].lc = tree[nid].rc = -1, tree[nid].val = val;
        tree[nid].cnt = tree[nid].nodesize = tree[nid].avsize = tree[nid].numsize = 1, tree[nid].del = false;
    }

找到某个值的位置。若不存在，返回一个结点，使得该值可作为该结点的左儿子或右儿子。

    int Find_Pos(int x, int val)
    {
        if(val < tree[x].val && tree[x].lc != -1) // 可能在左子树
            return Find_Pos(tree[x].lc, val);
        if(val > tree[x].val && tree[x].rc != -1) // 可能在右子树
            return Find_Pos(tree[x].rc, val);
        return x; // 找到目标结点
    }

还有 Update 函数，用来更新祖先结点的 nodesize、avsize、numsize，用 nodeadd、avadd、numadd 来表示祖先结点的 nodesize、avsize、numsize 需要加上的值。

    void Update(int x, int nodeadd, int avadd, int numadd)
    {
        if(x == -1) // 跳到头了
            return ;
        tree[x].nodesize += nodeadd, tree[x].avsize += avadd, tree[x].numsize += numadd;
        Update(tree[x].fa, nodeadd, avadd, numadd); // 向上跳
    }

然后就是替罪羊树的核心重建。
第一步是求中序遍历。

// 在结构体外
int seqsize;
struct tSeq
{
    int val, cnt;
}tseq[N << 1];

// 在结构体内
    void Dfs(int x)
    {
        if(x == -1) // 跳到了空结点
            return;
        Dfs(tree[x].lc); // 先遍历左子树
        if(!tree[x].del) // 如果未删除
            tseq[++seqsize].val = tree[x].val, tseq[seqsize].cnt = tree[x].cnt, mem.push(x), inst++;
        Dfs(tree[x].rc); // 最后遍历右子树
    }

ReAdd 函数，对区间 \([l, r]\) 进行重建，父节点为 fa，并返回根节点。

    int ReAdd(int l, int r, int fa)
    {
        if(l > r)
            return -1;
        int mid = (l + r) >> 1; // 取中间的结点
        int nid = newmem(); // 取出新的结点
        tree[nid].fa = fa;
		tree[nid].cnt = tseq[mid].cnt;
        tree[nid].val = tseq[mid].val;
        tree[nid].lc = ReAdd(l, mid - 1, nid); // 递归左边
        tree[nid].rc = ReAdd(mid + 1, r, nid); // 递归右边
        tree[nid].numsize = tree[tree[nid].lc].numsize + tree[tree[nid].rc].numsize + tseq[mid].cnt;
        tree[nid].nodesize = tree[nid].avsize = r - l + 1; // 注意已经自动删掉了打标了的结点
        return nid;
    }

ReBuild，对已知的结点 \(x\) 做重建。

    void ReBuild(int x)
    {
        seqsize = 0;
        Dfs(x);
        if(x == root)
            root = ReAdd(1, seqsize, -1);
        else
        {
            Update(x, tree[x].avsize - tree[x].nodesize, 0, 0);
            if(tree[tree[x].fa].lc == x)
                tree[tree[x].fa].lc = ReAdd(1, seqsize, tree[x].fa);
            else
                tree[tree[x].fa].rc = ReAdd(1, seqsize, tree[x].fa);
        }
    }

最后，当我们修改结点的时候，只有根结点到 \(val\) 代表的结点这一条路径上的结点可能会不平衡，所以从根节点开始，向下递归看是否要重建。

// 在结构体外
const double Alpha = 0.75, Beta = 0.3;

// 在结构体内
    void Find_ReBuild(int x, int val)
    {
        if(double(max(tree[tree[x].lc].nodesize, tree[tree[x].rc].nodesize)) > (tree[x].nodesize - 1) * Alpha || double(tree[x].nodesize - tree[x].avsize) > tree[x].nodesize * Beta) // 对应要重建的两种情况
        {
            ReBuild(x); // 重建
            return ;
        }
        if(tree[x].val != val) // 继续往下找
            Find_ReBuild((tree[x].val > val)?tree[x].lc:tree[x].rc, val);
    }

剩下的操作就很简单了。

2.2.4 替罪羊树的插入、删除

插入函数 Add，用 Find_Pos 函数找到位置，再讨论在何处插入。

    void Add(int val)
    {
        if(root == -1) // 为空树
        {
            Add_Node(root = newmem(), val, -1);
            return ;
        }
        int p = Find_Pos(root, val); // 找到应插入的位置
        if(tree[p].val == val) // 树中有这个结点
        {
            tree[p].cnt++;
            if(tree[p].del) // 删除了就复活
                tree[p].del = false, Update(p, 0, 1, 1);
            else
                Update(p, 0, 0, 1);
        }
        else if(tree[p].val > val) // 树中无该结点，判断新加的结点是左儿子还是右儿子
            Add_Node(tree[p].lc = newmem(), val, p), Update(p, 1, 1, 1);
        else
            Add_Node(tree[p].rc = newmem(), val, p), Update(p, 1, 1, 1);
		Find_ReBuild(root, val); // 判断是否重建
    }

删除函数 Del，也是用 Find_Pos 函数找到位置，再删除，判断是否打标。

    void Del(int val)
    {
        int p = Find_Pos(root, val); // 找到应删除的位置
        tree[p].cnt--;
        if(!tree[p].cnt) // 需要打标
            tree[p].del = true, Update(p, 0, -1, -1);
        else
            Update(p, 0, 0, -1);
        Find_ReBuild(root, val); // 判断是否重建
    }

2.2.5 替罪羊树的按数找排名、按排名找数

Find_Rank 函数，查找 \(val\) 的排名，从根节点递归查找。

    int Find_Rank(int val)
    {
        int x = root, ans = 0;
        while(tree[x].val != val)
        {
            if(x == -1) // 如果到了空树，那么 ans + 1 即为答案
                return ans + 1;
            if(val < tree[x].val) // 如果 val 比当前根的 val 小，那么在左子树
                x = tree[x].lc;
            else
                ans += tree[tree[x].lc].numsize + tree[x].cnt, x = tree[x].rc; // 否则在右子树，比 val 小的数有当前的左子树的 numsize + 当前根的 cnt
        }
        if(tree[x].lc != -1) // 左子树不为空，还有当前左子树的 numsize 没有算
            ans += tree[tree[x].lc].numsize;
        return ans + 1;
    }

Find_Num 函数，查找排名为 \(rank\) 的数，同样从根节点递归查找。

    int Find_Num(int rank)
    {
        int x = root, rrank = rank;
        while(true)
        {
            if(rrank <= tree[tree[x].lc].numsize) // 如果 rank 不大于左子树的 numsize，那么就是左子树的第 rank 个
                x = tree[x].lc;
            else // 否则要么是根，要么在右子树
            {
                rrank -= tree[tree[x].lc].numsize; // 先将 rank 减去左子树的 numsize
                if(rrank <= tree[x].cnt) // rank 小于等于根节点的 cnt，就在根节点
                    return tree[x].val;
                rrank -= tree[x].cnt, x = tree[x].rc; // 否则在右子树，根的值应该比答案小，减去根的 cnt
            }
        }
    }

2.2.6 替罪羊树的找前驱、后继

思维上略微复杂。
为了方便，定义 \(isrc(x)\) 表示 \(x\) 是否是一个结点的右儿子，是则为 \(1\)，不是则为 \(0\)。
首先用 Find_Pos 函数找到 \(val\) 的位置（记为 \(p\)），is_rc 表示上一个结点是否为该结点的右儿子。如果它是上一个结点是该结点的左儿子，一定往上跳（若答案在某个跳过的点的左子树上，答案不受影响），若是右儿子，那么如果比 \(val\) 小且存在，那么一定为该点，否则如果其有左儿子，在左儿子上找最大值。如果上述均不满足，那么往上跳 \(^\dag\)。
\(^\dag\) 一开始，无论 \(isrc(p)\) 值如何，is_rc 的初始值为 \(\text{true}\)，这样，在一开始就能检查左子树是否有答案（见代码）。
该做法的正确性：答案有两种情况：

  • 在 \(p\) 的左子树上；
  • 在 \(p\) 的某个祖先的左子树上。

易证这些数能覆盖所有 \(<val\) 的数。
若答案在 \(p\) 的左子树上，那么一开始即已经检查到。
否则，如果当前的点为 \(x\)，那么若 \(isrc(x) = 0\)，那么往上跳。这样除了 \(p\) 左子树上的数就没有 \(< val\) 的数了。若 \(isrc(x) = 1\)，那么答案在左子树（因为 \(< val\) 的数只在 \(x\) 的左子树上）。还有一种特殊情况，答案为某个祖先，需要判断一下。
特别的，无需担心左子树有结点但全被打标的情况，因为此时左子树的 \(\beta' = 1 \ge \beta\)。

    int tans;
    void Dfs_Pre(int x)
    {
        if(tree[x].rc != -1)
            Dfs_Pre(tree[x].rc);
        if(tans != -1)
            return ;
        if(!tree[x].del)
        {
            tans = tree[x].val;
            return ;
        }
        if(tree[x].lc != -1)
            Dfs_Pre(tree[x].lc);
    }
    int Find_Pre(int x, int val, bool is_rc)
    {
        tans = -1;
        if(!is_rc) // is_rc = 0，向上跳
            return Find_Pre(tree[x].fa, val, (tree[x].fa != -1)?(tree[tree[x].fa].rc == x):false);
        if(!tree[x].del && tree[x].val < val) // 答案为某个祖先
            return tree[x].val;
        if(tree[x].lc != -1) // is_rc = 1 且左子树不为空
        {
            Dfs_Pre(tree[x].lc);
            return tans;
        }
        return Find_Pre(tree[x].fa, val, (tree[x].fa != -1)?(tree[tree[x].fa].rc == x):false); // 继续往上
    }

找后继代码 Dfs_Nxt 和 Find_Nxt 几乎与找前驱类似，原理也类似，相当于 Dfs_Pre 函数和 Find_Pre 函数全部反过来。

    void Dfs_Nxt(int x)
    {
        if(tree[x].lc != -1)
            Dfs_Nxt(tree[x].lc);
        if(tans != -1)
            return ;
        if(!tree[x].del)
        {
            tans = tree[x].val;
            return ;
        }
        if(tree[x].rc != -1)
            Dfs_Nxt(tree[x].rc);
    }
    int Find_Nxt(int x, int val, bool is_lc)
    {
        tans = -1;
        if(!is_lc)
            return Find_Nxt(tree[x].fa, val, (tree[x].fa != -1)?(tree[tree[x].fa].lc == x):false);
        if(!tree[x].del && tree[x].val > val)
            return tree[x].val;
        if(tree[x].rc != -1)
        {
            Dfs_Nxt(tree[x].rc);
            return tans;
        }
        return Find_Nxt(tree[x].fa, val, (tree[x].fa != -1)?(tree[tree[x].fa].lc == x):false);
    }

2.3 替罪羊树完整代码

抽象的 \(258\) 行。

/**                                                                                        {        
 * problem: 替罪羊树        
 * site: \	
 * author: _Z_F_R_
 * date: 2023-10-05 14:26:30    
 **/       
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
const double Alpha = 0.75, Beta = 0.3;
int seqsize;
struct tSeq
{
    int val, cnt;
}tseq[N << 1];
struct Scapegoat_Tree
{
    struct tNode
    {
        int lc, rc, fa, val, cnt, nodesize, avsize, numsize;
        bool del;
    }tree[N << 1];
    int root, used, inst;
    Scapegoat_Tree() { root = -1; }
    stack<int>mem;
    int newmem()
    {
        if(inst > 0)
        {
            inst--;
            int top = mem.top();
			mem.pop();
			return top;
        }
        return ++used;
    }
    void Add_Node(int nid, int val, int fa)
    {
        tree[nid].fa = fa, tree[nid].lc = tree[nid].rc = -1, tree[nid].val = val;
        tree[nid].cnt = tree[nid].nodesize = tree[nid].avsize = tree[nid].numsize = 1, tree[nid].del = false;
    }
    int Find_Pos(int x, int val)
    {
        if(val < tree[x].val && tree[x].lc != -1)
            return Find_Pos(tree[x].lc, val);
        if(val > tree[x].val && tree[x].rc != -1)
            return Find_Pos(tree[x].rc, val);
        return x;
    }
    void Update(int x, int nodeadd, int avadd, int numadd)
    {
        if(x == -1)
            return ;
        tree[x].nodesize += nodeadd, tree[x].avsize += avadd, tree[x].numsize += numadd;
        Update(tree[x].fa, nodeadd, avadd, numadd);
    }
    void Dfs(int x)
    {
        if(x == -1)
            return;
        Dfs(tree[x].lc);
        if(!tree[x].del)
            tseq[++seqsize].val = tree[x].val, tseq[seqsize].cnt = tree[x].cnt, mem.push(x), inst++;
        Dfs(tree[x].rc);
    }
    int ReAdd(int l, int r, int fa)
    {
        if(l > r)
            return -1;
        int mid = (l + r) >> 1;
        int nid = newmem();
        tree[nid].fa = fa;
        tree[nid].cnt = tseq[mid].cnt;
        tree[nid].val = tseq[mid].val;
        tree[nid].lc = ReAdd(l, mid - 1, nid);
        tree[nid].rc = ReAdd(mid + 1, r, nid);
        tree[nid].numsize = tree[tree[nid].lc].numsize + tree[tree[nid].rc].numsize + tseq[mid].cnt;
        tree[nid].nodesize = tree[nid].avsize = r - l + 1;
        return nid;
    }
    void ReBuild(int x)
    {
        seqsize = 0;
        Dfs(x);
        if(x == root)
            root = ReAdd(1, seqsize, -1);
        else
        {
            Update(x, tree[x].avsize - tree[x].nodesize, 0, 0);
            if(tree[tree[x].fa].lc == x)
                tree[tree[x].fa].lc = ReAdd(1, seqsize, tree[x].fa);
            else
                tree[tree[x].fa].rc = ReAdd(1, seqsize, tree[x].fa);
        }
    }
    void Find_ReBuild(int x, int val)
    {
        if(double(max(tree[tree[x].lc].nodesize, tree[tree[x].rc].nodesize)) > (tree[x].nodesize - 1) * Alpha || double(tree[x].nodesize - tree[x].avsize) > tree[x].nodesize * Beta)
        {
            ReBuild(x);
            return ;
        }
        if(tree[x].val != val)
            Find_ReBuild((tree[x].val > val)?tree[x].lc:tree[x].rc, val);
    }
    void Add(int val)
    {
        if(root == -1)
        {
            Add_Node(root = newmem(), val, -1);
            return ;
        }
        int p = Find_Pos(root, val);
        if(tree[p].val == val)
        {
            tree[p].cnt++;
            if(tree[p].del)
                tree[p].del = false, Update(p, 0, 1, 1);
            else
                Update(p, 0, 0, 1);
        }
        else if(tree[p].val > val)
            Add_Node(tree[p].lc = newmem(), val, p), Update(p, 1, 1, 1);
        else
            Add_Node(tree[p].rc = newmem(), val, p), Update(p, 1, 1, 1);
		Find_ReBuild(root, val);
    }
    void Del(int val)
    {
        int p = Find_Pos(root, val);
        tree[p].cnt--;
        if(!tree[p].cnt)
            tree[p].del = true, Update(p, 0, -1, -1);
        else
            Update(p, 0, 0, -1);
        Find_ReBuild(root, val);
    }
    int Find_Rank(int val)
    {
        int x = root, ans = 0;
        while(tree[x].val != val)
        {
            if(x == -1)
                return ans + 1;
            if(val < tree[x].val)
                x = tree[x].lc;
            else
                ans += tree[tree[x].lc].numsize + tree[x].cnt, x = tree[x].rc;
        }
        if(tree[x].lc != -1)
            ans += tree[tree[x].lc].numsize;
        return ans + 1;
    }
    int Find_Num(int rank)
    {
        int x = root, rrank = rank;
        while(true)
        {
            if(rrank <= tree[tree[x].lc].numsize)
                x = tree[x].lc;
            else
            {
                rrank -= tree[tree[x].lc].numsize;
                if(rrank <= tree[x].cnt)
                    return tree[x].val;
                rrank -= tree[x].cnt, x = tree[x].rc;
            }
        }
    }
    int tans;
    void Dfs_Pre(int x)
    {
        if(tree[x].rc != -1)
            Dfs_Pre(tree[x].rc);
        if(tans != -1)
            return ;
        if(!tree[x].del)
        {
            tans = tree[x].val;
            return ;
        }
        if(tree[x].lc != -1)
            Dfs_Pre(tree[x].lc);
    }
    int Find_Pre(int x, int val, bool is_rc)
    {
        tans = -1;
        if(!is_rc)
            return Find_Pre(tree[x].fa, val, (tree[x].fa != -1)?(tree[tree[x].fa].rc == x):false);
        if(!tree[x].del && tree[x].val < val)
            return tree[x].val;
        if(tree[x].lc != -1)
        {
            Dfs_Pre(tree[x].lc);
            return tans;
        }
        return Find_Pre(tree[x].fa, val, (tree[x].fa != -1)?(tree[tree[x].fa].rc == x):false);
    }
    void Dfs_Nxt(int x)
    {
        if(tree[x].lc != -1)
            Dfs_Nxt(tree[x].lc);
        if(tans != -1)
            return ;
        if(!tree[x].del)
        {
            tans = tree[x].val;
            return ;
        }
        if(tree[x].rc != -1)
            Dfs_Nxt(tree[x].rc);
    }
    int Find_Nxt(int x, int val, bool is_lc)
    {
        tans = -1;
        if(!is_lc)
            return Find_Nxt(tree[x].fa, val, (tree[x].fa != -1)?(tree[tree[x].fa].lc == x):false);
        if(!tree[x].del && tree[x].val > val)
            return tree[x].val;
        if(tree[x].rc != -1)
        {
            Dfs_Nxt(tree[x].rc);
            return tans;
        }
        return Find_Nxt(tree[x].fa, val, (tree[x].fa != -1)?(tree[tree[x].fa].lc == x):false);
    }
    void Print()
    {
		printf("%d\n", root);
        int i;
        for(i = 1; i <= used; i++)
            printf("%d : [%d] fa : %d lc : %d rc : %d cnt : %d val : %d size : [%d, %d, %d]\n", i, tree[i].del, tree[i].fa, tree[i].lc, tree[i].rc, tree[i].cnt, tree[i].val, tree[i].nodesize, tree[i].avsize, tree[i].numsize);
    }
}bst;

int main()
{
	int n;
    scanf("%d", &n);
    while(n--)
    {
        int op, val;
        scanf("%d %d", &op, &val);
        if(op == 1)
            bst.Add(val);
        else if(op == 2)
            bst.Del(val);
        else if(op == 3)
            printf("%d\n", bst.Find_Rank(val));
        else if(op == 4)
            printf("%d\n", bst.Find_Num(val));
        else if(op == 5)
            printf("%d\n", bst.Find_Pre(bst.Find_Pos(bst.root, val), val, true));
        else
            printf("%d\n", bst.Find_Nxt(bst.Find_Pos(bst.root, val), val, true));
    }
}

敬请期待后续 Treap / FHQ Treap / Splay 等多种平衡树

参考：
https://blog.csdn.net/a_forever_dream/article/details/81984236

标签：lc,val,int,tree,更新,fa,笔记,nid,平衡
From： https://www.cnblogs.com/IncludeZFR/p/18295341

相关文章

  • 【国赛赛题详解】2024年数学建模国赛ABCDEF题（点个关注，后续会更新）
     您的点赞收藏是我继续更新的最大动力！一定要点击如下的蓝色字体链接，那是获取资料的入口!点击链接加入群聊【2024国赛资料合集】：http://qm.qq.com/cgi-bin/qm/qr?_wv=1027&k=eQt5WRIvc5-fogZRrrahAhbqDa2nKfW8&authKey=%2BqQfThTxNnhw5LGJFRIcneF8JXBj1ufd2K01UpKPrpcgkKDskF......
  • 【国赛赛题详解】2024年数学建模国赛ABCDEF题（点个关注，后续会更新）
    您的点赞收藏是我继续更新的最大动力！一定要点击如下的蓝色字体链接，那是获取资料的入口!点击链接加入群聊【2024国赛资料合集】：http://qm.qq.com/cgi-bin/qm/qr?_wv=1027&k=eQt5WRIvc5-fogZRrrahAhbqDa2nKfW8&authKey=%2BqQfThTxNnhw5LGJFRIcneF8JXBj1ufd2K01UpKPrpcgkKDskFkr......
  • Systemd 学习笔记
    Unit的配置文件[Unit]区块通常是配置文件的第一个区块，用来定义Unit的元数据，以及配置与其他Unit的关系[Install]通常是配置文件的最后一个区块，用来定义如何启动，以及是否开机启动[Service]区块用来Service的配置，只有Service类型的Unit才有这个区块Unit文件[Unit......
  • Python学习笔记（一）（更新中）
    提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档Python基础语法（一）一、变量1、变量命名的规则2、变量的常见类型二、注释提示：以下是本篇文章正文内容，下面案例可供参考一、变量变量是指存储信息的容器。变量的赋值包括变量名、等号、存储的信息这......
  • 《未来世界的幸存者》读书笔记
    信息《未来世界的幸存者》阮一峰https://www.ruanyifeng.com/survivor/摘录以前，我们常听到的口号是“技术让生活更美好”，但现在不是这样，技术只是刺激消费的工具。理想中，技术应该发扬人性的正面因素，实际上技术却被用来放大和推动人性的负面因素。比如，我们动用大量的金钱和能......
  • 《杀死一只知更鸟》读书笔记
    信息《杀死一只知更鸟》[美]哈珀·李/高红梅/译林出版社摘录有一天在学校里，我又被迫想到了他们。我们每周有一节“时事讲评”课。每个孩子都要从报纸上剪一条新闻，背熟内容，之后再讲给全班同学听。这项练习据说能克服种种缺点：站在同学面前可以鼓励他姿势端正，神情泰然；做一......
  • 《论语》读书笔记
    信息《论语》杨逢彬注译长江文艺出版社摘录子曰：弟子入则孝，出则悌，谨而信，泛爱众而亲仁，行有余力，则以学文。子曰：君子食无求饱，居无求安，敏于事而慎于言，就有道而正焉，可谓好学也已矣。子曰：学而不思则罔，思而不学则殆。子曰：多闻阙疑，慎言其余，则寡尤。多见阙殆，慎行其余，则寡......
  • 2024/7/10 笔记
    CF1693F对0,1个数相等的0,1串进行排序一定是最优的贪心策略。我们把0记为1，1记为-1.求前缀和如果1的个数大于0的个数，那么就把整个串翻转然后取反，推一下就可以知道结果不会变。CF1646F这题我写了半天发现假了；一开始看了样例很容易想到，每个人每轮都把自己不需要的牌往下......
  • Open3D点云算法与点云深度学习案例汇总（长期更新）
    目录引言Open3D算法汇总Open3D快速安装测试点云资料一、点云的读写与显示二、KDtree和八叉树的应用三、点云特征提取四、点云滤波算法五、点云配准算法六、点云分割算法（待更新）七、常用操作八、数据转换九、常用小工具三维点云深度学习PointNet++引言  ......
  • 宋红康MySQL笔记
    MySQL数据库入门到大牛，mysql安装到优化，百科全书级，全网天花板https://www.bilibili.com/video/BV1iq4y1u7vj?p=43&vd_source=ecbebcd4db8fad7f74c518d13e78b165HAVING的使用#练习：查询各个部门中最高工资比10000高的部门信息#错误的写法：SELECTdepartment_id,MAX(salary)FROMem......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99