精华内容
下载资源
问答
  • 可以直接调用 Python库和 FPGA硬件库进行开发,即 Python代码可以在板子上运行,它 Xilinx公司开发出来的一个全新的开源框架,使得嵌入式编程人员能够在无需设计可编程逻辑电路的情况下即可充分发挥 Xilinx Zynq ...

    Pynq 指的就是使用 Python 语言进行 FPGA 开发,而 Pynq 是 Python + Zynq 的一种开发板。可以直接调用 Python 库和 FPGA 硬件库进行开发,即 Python 代码可以在板子上运行,它是 Xilinx 公司开发出来的一个全新的开源框架,使得嵌入式编程人员能够在无需设计可编程逻辑电路的情况下即可充分发挥 Xilinx Zynq All Programmable SoC(APSoC)的功能。

    Zynq 一般基于 C/C++ 开发,功能更全面、扩展性更强,相比于 Pynq 更成熟,相关的学习教程较多,便于学习与开发过程中问题的解决。

    而 Python 基于 Zynq 开发,Python 库和 FPGA 硬件库可以直接调用,极大加快开发进程、缩短开发周期、降低开发难度,更方便、快捷;使用 Jupyter 在线编程工具,简单易行。用 Pynq 开发,当 Python 有更加有效的可用库时(如图像处理 OpenCV ),其性能要比 C/C++ 开发更强。

    要用于个人学习与开发,Pynq 的功能(如嵌入式、AI终端实现等)应该完全足够。(一般用 Python 应该就够了,需要的话再结合 C/C++、设计新的硬件库等)。

    若要研发类似 Pynq 的板子,可以借鉴:在 Zynq 的基础上加入 Python 内核和 Python 编译环境的网络服务器以及 FPGA 硬件库等。

    Zynq 分为 PS 和 PL 两个部分,PS 有两个 ARM 的核,在上面运行 Linux 操作系统,在操作系统上再运行 Python。PL部分就是 FPGA 的逻辑资源,开发者在 PL 中添加 IP 或者将自己用 C 或者 HDL 语言设计成的模块封装成 IP,这些 IP 都被连接到 PS 端,一般都是通过 AXI 总线。Pynq 有一个特有的库叫 Overlay,使用这个库可以对连接到 PS 端的接口进行解析,进而控制 FPGA 逻辑资源及 IO。每次当你需要开始一个新的涉及 PL 端的开发的时候,先在 Vivado 里面建一个工程,添加你需要的各种 IP,然后以 Zynq 为核心连接的设计,经过编译后,生成一个 bit 文件和一个 tcl 文件。bit 文件就是你的硬件设计,tcl 文件描述了接口关系。将这两个文件复制到 Pynq 的目录下,即可进行调用。每一次调用的时候,你设计的硬件都是被动态加载的,这一点不同于大家熟悉的加载过程。动态加载无需重启硬件,操作系统无需重启。这一是一个极有优势的设计,我记得当年调试过 Intel 和 Altera 共同推出的阿童木平台完全不同。经过上面的描述,我们可以得知,在 Pynq 框架下,可以非常方便地进行 FPGA 开发,可以充分利用 Pyhon 的灵活性和 FPGA 的硬件资源。Pyhon 可以帮你轻松完成各种复杂设计,比如图像处理和人工智能的算法,FPGA 可以为你提供灵活的接口和硬件加速能力。

    具体可以搜索“Pynq系列学习”“Pynq上手笔记”。

    展开全文
  • 什么是二叉搜索(BST)?   其实这个概念非常简单,二叉树里每个节点都是一个爸爸,每个爸爸有两个儿子 而二叉“搜索”就是要满足一个...比如我们玩一个游戏,我心里想一个数字,你要猜这个数字是什么,那你可以

    什么是二叉搜索树(BST)?


    其实这个概念非常简单,二叉树里每个节点都是一个爸爸,每个爸爸有两个儿子
    而二叉“搜索”树就是要满足一个额外的条件:所有左儿子的数字都比爸爸数字小,所有右儿子的数字都比爸爸数字大。
    示例:
    屏幕快照 2020-07-03 下午12.04.44.png
    (图源:力扣(LeetCode))
    我们可以很容易看见,每个爸爸节点分出来的左边部分里,任何一个数字都比这个爸爸数字小;右边部分里,任何一个数字都比这个爸爸数字大。

    至于为什么叫二分“搜索”树,我的理解是这样的:
    比如我们玩一个游戏,我心里想一个数字,你要猜这个数字是什么,那你可以用这样一棵搜索树,从最顶上的父节点开始,每次问我,“你想的数字比当前节点大还是小?”,你就可以一步步顺着树往下走,搜索到我心里想的数字。所以这就是一个搜索的过程,是一个不断缩小搜索范围的过程。

    言归正传,为什么我们已经满足了题目二分搜索树的条件,因为题目一开始就给了我们一个有序的数列,你每次在中间取一个爸爸,爸爸的左边部分必定小于爸爸数,右边部分也必定大于爸爸树。

    什么是中序遍历?

    “前序遍历”、“中序遍历”、“后序遍历”里说的遍历,实际上是我们遍历二叉树的方式
    其实一张图就能给你解释什么叫中序遍历:
    (其中,箭头表示遍历顺序。二叉树本身的箭头没画。)
    在这里插入图片描述

    我们发现,这个“前”、“中”、“后”其实指的就是ROOT在遍历当中的位置嘛,左右两部分一直都是从左到右。

    比如中序遍历的过程,我们来看一个例子:
    如下一棵随便画的二叉树,搞得很丑但我不管:
    在这里插入图片描述

    注意,遍历的时候,记住一个关键点:我们遍历的是树而不是节点
    这么说有点抽象,具体一点说:每次遍历的时候,要把子树看成一个整体,
    比如我们来看一个最大的格局:爸爸节点是1号,那么左子树是2、4、5、7、8整个整体,右子树是3、6、9、10整个整体,
    在这个最大格局上进行遍历,那就是左子树整体->1号->右子树整体

    所以我们现在知道要从左子树开始,那么左子树也要遵循中序遍历,所以顺序应该是
    4、7整体 -> 2 -> 5、8整体

    然后进入1

    然后进入右子树,右子树也遵循中序遍历:
    空白(3开头的右子树并没有左边部分) -> 3 -> 6、9、10整体

    依此类推,如果你能理解完整的顺序:
    4、7、2、8、5、1、3、9、6、10
    说明你已经理解了中序遍历,记住每次进入一个子树的时候,不要急着先遍历这个子树的爸爸,每个子树也都是要从左边开始才能是中序遍历的!

    如果用前序、后序遍历这棵树呢?

    其实是一样的道理,只要每次遵循前序、后序遍历的规则,而不是用中序的规则而已。
    前序:1、2、4、7、5、8、3、6、9、10
    后序:7、4、8、5、2、9、10、6、3、1

    展开全文
  • 首先,对于小于n的每个数,我们可以确定它的约数之和(不包括自己)固定的,就像4的约数之和一定3,不可能其他的,那么我们就可以将2-n的每个数的约数之和求出sum[i],对于sum[i]<i 的我们连一条sum[i]----...

    题面

    在这里插入图片描述

    题解

    1. 首先,对于小于n的每个数,我们可以确定它的约数之和(不包括自己)是固定的,就像4的约数之和一定是3,不可能是其他的,那么我们就可以将2-n的每个数的约数之和求出sum[i],对于sum[i]<i 的我们连一条sum[i]---->i 的边(因为对于每个i,sum[i]是唯一确定的),也就是说每个儿子都有唯一一个父节点,那么我们最终就会构成森林(多课树),题中找最长的变换步骤就转换成了求树的最长直径
    1. 为什么不从1开始 ,因为1除本身外约数之和就是0,题中要求最小为1,所以1是不符合要求的
    1. 如何找一树的最长直径,我们可以依次枚举每个点,找这个点最长和次长距离,然后相加即可 ,具体可看树的最长路径,这里就不详细讲解了

    代码

    #include<iostream>
    #include<cstdio>
    #include<string>
    #include<cstring>
    #include<algorithm>
    
    using namespace std;
    const int N = 5e4 + 10;
    
    int n;
    int h[N], e[N], ne[N], idx;
    int sum[N];   //约数之和
    bool is[N];   //是否已经用过
    int ans;
    
    
    void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    
    int dfs(int u) {
    
        int d1 = 0, d2 = 0;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            int d = dfs(j) + 1;
            if (d > d1) d2 = d1, d1 = d;
            else if (d > d2) d2 = d;
        }
    
        ans = max(ans, d1 + d2);
    
        return d1;
    }
    
    
    int main() {
    
        memset(h, -1, sizeof h);
    
        cin >> n;
    
        for (int i = 1; i <= n; i++) {
            for (int j = 2; j <= n / i; j++) {  //不能是自己的本身
                sum[i * j] += i;
            }
        }
    
        for (int i = 2; i <= n; i++) {
            if (sum[i] < i) {
                add(sum[i], i);
            }
            is[i] = true;
        }
    
        for (int i = 1; i <= n; i++) {
            if (!is[i]) {   //说明是父节点
                dfs(i);
            }
        }
    
        cout << ans << endl;
    
        return 0;
    }
    
    
    展开全文
  • 那么什么是主席? 一言以蔽之:带历史版本的线段。 所谓历史版本,即在插入某个数字之前,这棵线段的样子。 如果用n (数字的数量) 棵线段实现这种“历史版本”会炸内存的。 不过在思考的过程中还是很有必要...

    主席树

    ~

    有问题欢迎在评论区一起讨论(๑•̀ㅂ•́)و✧

    问题引入

    n个数字,m次查询。
    查询方式:l, r, k.
    即求区间[l, r]中第k大的数字

    使用主席树

    为了高效率地解决这个问题,我们需要使用主席树。

    那么什么是主席树?
    一言以蔽之:带历史版本的线段树。
    所谓历史版本,即在插入某个数字之前,这棵线段树的样子。

    如果用n (数字的数量) 棵线段树实现这种“历史版本”会炸内存的。
    不过在思考的过程中还是很有必要实践一下的。
    在稍加模拟之后可以发现相邻的两棵子树中有近乎半数的节点没有发生改变,极大地浪费了空间,所以对于这些节点,我们不再每次都新建,而是直接使用原来的节点。
    主席树就是这样了。

    前置技能

    如上所言,我们需要建立n棵线段树,不过多数不变的节点不再新建。
    那么我们需要提前知道数据的范围。如果数据的范围超级大呢?为了避免这种情况下的MLE, 我们需要用到离散化的知识(很简单的,不要打退堂鼓呀!)。
    离散化链接:离散化
    此外,既然是n棵线段树,那么必然要学过线段树的呀~
    线段树链接:线段树

    要用的变量

    int nodeNum;
    // 当前节点的全局编号
    int L[N << 5], R[N << 5], sum[N << 5];
    // L[i]  : 节点i的左子树的根节点的全局编号
    // R[i]  : 节点i的右子树的根节点的全局编号
    // sum[i]: 以节点i为根节点的树所储存的数字的数量
    int a[N], b[N];
    // a: 初始数组
    // b: 初始数组的副本,用于离散化
    int T[N];
    // T[i]: 第i+1棵子树的根节点
    

    建树

    // 建树, 返回根节点
    int build(int l, int r) {
        // num 为当前树的根节点编号
        int num = ++nodeNum;
        if (l != r) {
            int mid = (l + r) >> 1;
            // 建立左子树
            L[num] = build(l, mid); // 当前num节点的左子树的根节点编号
            // 建立右子树
            R[num] = build(mid + 1, r);
        }
        return num;
    }
    

    插入节点

    // 插入节点x,返回所生成的线段树的根节点
    // pre为上一棵子树的根节点
    int udNode(int pre, int l, int r, int x) {
        int num = ++nodeNum;
        // 将上一棵子树的左右子树连接到新树的根节点
        L[num] = L[pre];
        R[num] = R[pre];
        // 新树中插入了一个数字,所以sum[num]比sum[pre]大 1
        sum[num] = sum[pre] + 1;
        if (l != r) {
            int mid = (l + r) >> 1;
            // 确定待插入的节点所在的子树
            // 生成新的左/右子树并更新根节点的对应的子树编号
            if (x <= mid) L[num] = udNode(L[pre], l, mid, x);
            else R[num] = udNode(R[pre], mid + 1, r, x);
        }
        return num;
    }
    

    区间查询

    // 查询[l,r]中第k大/小的数字并返回该数字
    int query(int u, int v, int l, int r, int k) {
        // 递归出口:到达叶子节点
        if (l == r) return b[l];
        int mid = (l + r) >> 1;
        // 设 u: l-1, v: r
        // 则 num: 第r+1棵树的左子树的数字的数量减去第l棵树的左子树的数字的数量所得的数字的数量
        int num = sum[L[v]] - sum[L[u]];
        // 若 k 小于等于 num,说明所求数字在左子树
        // 否则说明所求数字在右子树
        if (num >= k) return query(L[u], L[v], l, mid, k);
        else return query(R[u], R[v], mid + 1, r, k - num); 
        // 在右子树时,需要减去左子树的数字的数量。因为全局的第k大/小的数字,在右子树中为第k-num大/小的数字
    }
    

    模板题的代码(注释很有用哦!)

    题目链接:LG模板题

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<cstdlib>
    #include<string>
    #include<queue>
    #include<map>
    #include<stack>
    #include<list>
    #include<set>
    #include<deque>
    #include<vector>
    #include<ctime>
    
    using namespace std;
    //#pragma GCC optimize(2)
    #define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
    #define ull unsigned long long
    #define ll long long
    #define rep(i, x, y) for(int i=x;i<=y;i++)
    #define mms(x, n) memset(x, n, sizeof(x))
    #define mmc(A, b) memcpy(A, b, sizeof(b))
    #define INF (0x3f3f3f3f)
    #define mod (ull)(1e9+7)
    typedef pair<int, int> P;
    const int N = 2e5 + 10;
    int nodeNum;
    // 当前节点的全局编号
    int L[N << 5], R[N << 5], sum[N << 5];
    // L[i]  : 节点i的左子树的根节点的全局编号
    // R[i]  : 节点i的右子树的根节点的全局编号
    // sum[i]: 以节点i为根节点的树所储存的数字的数量
    int a[N], b[N];
    // a: 初始数组
    // b: 初始数组的副本,用于离散化
    int T[N];
    // T[i]: 第i+1棵子树的根节点
    
    // 建树, 返回根节点
    int build(int l, int r) {
        // num 为当前树的根节点编号
        int num = ++nodeNum;
        if (l != r) {
            int mid = (l + r) >> 1;
            // 建立左子树
            L[num] = build(l, mid); // 当前num节点的左子树的根节点编号
            // 建立右子树
            R[num] = build(mid + 1, r);
        }
        return num;
    }
    
    // 插入节点x,返回所生成的线段树的根节点
    // pre为上一棵子树的根节点
    int udNode(int pre, int l, int r, int x) {
        int num = ++nodeNum;
        // 将上一棵子树的左右子树连接到新树的根节点
        L[num] = L[pre];
        R[num] = R[pre];
        // 新树中插入了一个数字,所以sum[num]比sum[pre]大 1
        sum[num] = sum[pre] + 1;
        if (l != r) {
            int mid = (l + r) >> 1;
            // 确定待插入的节点所在的子树
            // 生成新的左/右子树并更新根节点的对应的子树编号
            if (x <= mid) L[num] = udNode(L[pre], l, mid, x);
            else R[num] = udNode(R[pre], mid + 1, r, x);
        }
        return num;
    }
    
    // 查询[l,r]中第k大/小的数字并返回该数字
    int query(int u, int v, int l, int r, int k) {
        // 递归出口:到达叶子节点
        if (l == r) return b[l];
        int mid = (l + r) >> 1;
        // 设 u: l-1, v: r
        // 则 num: 第r+1棵树的左子树的数字的数量减去第l棵树的左子树的数字的数量所得的数字的数量
        int num = sum[L[v]] - sum[L[u]];
        // 若 k 小于等于 num,说明所求数字在左子树
        // 否则说明所求数字在右子树
        if (num >= k) return query(L[u], L[v], l, mid, k);
        else return query(R[u], R[v], mid + 1, r, k - num); 
        // 在右子树时,需要减去左子树的数字的数量。因为全局的第k大/小的数字,在右子树中为第k-num大/小的数字
    }
    
    int main() {
    //    freopen("input.txt", "r", stdin);
        int n, m;
        scanf("%d%d", &n, &m);
    
        // 离散化
        rep(i, 1, n) {
            scanf("%d", &a[i]);
            b[i] = a[i]; // b 数组为 a 数组的副本
        }
        // 排序后去重
        sort(b + 1, b + 1 + n);
        // 获取去重后的数组大小
        int size = unique(b + 1, b + 1 + n) - b - 1;
        // T[0] 为第一棵线段树(空树)的根节点
        T[0] = build(1, size);
        for (int i = 1; i <= n; i++) {
            // 获取映射值
            int x = lower_bound(b + 1, b + 1 + size, a[i]) - b;
            // T[i] 为第i+1棵线段树的根节点
            T[i] = udNode(T[i - 1], 1, size, x);
        }
    
        // 查询
        while (m--) {
            int l, r, k;
            // [l, r]区间中第k大/小的数字
            scanf("%d%d%d", &l, &r, &k);
            printf("%d\n", query(T[l - 1], T[r], 1, size, k));
        }
        return 0;
    }
    
    展开全文
  • 字典(前缀)

    万次阅读 多人点赞 2018-08-24 00:41:07
    什么是字典? 叫前缀更容易理解 字典的样子 Trie又被称为前缀、字典,...这些字符可以是任意一个字符集中的字符。比如对于都是小写字母的字符串,字符集就是’a’-‘z’;对于都是数字的字符串,字...
  • 眨眼间数据结构课已经接近尾声了。Rose-Hulman这个数据结构课,从非线性数据结构开始讲起(因为线性数据结构——链表、堆栈和队列——...首先介绍了基本的结构(Tree): 由此可见,其实可以算是一个链表形式的结
  • 可以保证第一次搜到的就是最短路。 题目要求最短/最优之类的,一般都使用BFS。 题目比较奇怪,对复杂度要求高的,一般都用DFS。 注意两个概念 回溯:在DFS中,这条路走不通了,回退到父节点 剪枝:提前判断这个方法...
  • 首先,我们会有需求分析,就是说你要为谁做一个的产品,有了这个需求以后,会先一步的细化,我们的芯片的规格是什么样子,把我们的spec定义出来,定义出来以后会把这个spec进一步的break down,比如说到一些子系统的...
  • 我们先把原数列$a_i-=i$,那么本来要求递增序列,现在只需要求一个非严格递增的就行了(可以看做最后每个$b_i+=i$,那么非严格递增会变为递增) 如果一个数列递增的,一个一个相等的取,如果递减的,取他们的中...
  • 权值线段树 是什么 权值线段树也是一棵线段树,但是它与普通线段树有所区别: 普通线段树记录的是一段区间 [l,r] 中的a[l]~a[r]...简单来看,权值线段树可以非常方便地查询一段区间的数字出现的次数。 引申出它...
  • 线段

    2020-07-20 23:04:25
    前置内容 学习线段前,你需要掌握二叉搜索,只补充一个内容,就是关于二叉...这因为虽然节点4和节点5不存在,但是仍然应该为他们保留4和5这2个编号,你可以把这棵看成这样: 线段的概念 线段,英文名
  • 决策

    2019-01-30 12:47:29
    什么是决策 决策树是帮助探索所有决策备选方案及其可能结果的流程图或图表。 的每个“分支”表示做出决策时可用的可能选项之一。当一个备选结果导致必须做出的另一个决定时,分支可以扩展。在每个分支中添加与每...
  • Trie,又称字典,单词查找或者前缀一种用于快速检索的多叉结构,如英文字母的字典树是一个26叉数字的字典树是一个10叉。 我理解字典树是看了这位大佬博客。还不了解字典可以先进去学习一下...
  • 首先你要知道什么是二叉搜索? 对于节点来说,根节点比左节点大,比右节点小, 后序序列代表着遍历顺序左右根 这样就知道数组最后一个肯定根节点,而可以用根节点把这个数组分割开,分成两部分,前部分都比根...
  • 字典

    万次阅读 2018-03-29 13:03:15
    了解它究竟是什么 游戏终于开始了. 了解它究竟是什么 字典(trie)是一个神奇的东西.它利用了字符串的公共前缀来存放字符串,从而减小了这些字符串的总空间. 它可以用来解决一些关于前缀的问题. 同理它也能...
  • 先回顾一下,什么是前序遍历,中序遍历和后序遍历: (1)前序遍历: 先访问根节点 再先序访问左子树 再先序右子。 (2)中序遍历: 中序遍历左子树 再访问根节点 再中序遍历右子 (3)后序遍历: 先后序遍历左...
  • 静态主席

    2018-07-06 16:08:29
    最经典的问题就是:区间第k小问题(也就是指定一个区间,要求求出这个区间中第k小的数字)在搞懂什么是主席之前,我们要先对权值线段有一定的了解,下面我们就先说一下权值线段,然后详细说一下主席以及主席...
  • 接下去一行一个序列,序列长度小于10,包含(0~9)的数字,没有重复数字,根据这个序列可以构造出一颗二叉搜索。 接下去的n行有n个序列,每个序列格式跟第一个序列一样,请判断这两个序列是否能组成同一颗二叉...
  • 主席 (模板)

    2017-08-02 16:13:23
    //思想:主席就是一颗持久化线段, 为什么叫持久化了, 因为它可以保存之前的线段版本, 并且可以拿来用, 从而优化空间. (至于为什么叫主席了, 大概因为发明这个算法的人的名字的缘故吧….) 详细说说: ...
  • GDFZOJ 美丽

    2016-10-22 09:44:00
    一段连续的数字必定有一个最大的数字和最小的数字,如果现在知道最大和最小的数是什么了,判断是否连续就可以通过找出数的个数了。。 所以需要找出:一棵子树的最大值,最小值,节点个数 代码: #include <...
  • 线段维护的区间,然后对于线段维护的区间的所有数字都维护一个平衡,然后所有的操作都对每个平衡单独处理。 比如说操作3,需要先二分答案,然后再询问每个区间的平衡来judgejudge 这样的复杂度log3...
  • 的存储结构

    2018-02-26 13:54:09
    双亲表示法: 注:其中r=0表示的是根,n=11表示是11个结点。...因此可是,如果我们要知道某结点的孩子是什么?那么不好意思,请遍历整个结构。 我们可以稍微改变下结构: 那么我们现在...
  • BST二叉搜索

    2016-08-09 21:45:39
    1、二叉搜索 (1)、逼近折半查找的查找算法;... (4)左子树和右子二叉搜索;2、为什么叫二叉搜索? 如果对一颗二叉搜索进行中序遍历,可以按从小到大的顺序输出,此时又叫做二叉排序。如图:3、搜索...
  • 2.求出l到r上的第k大的数字是什么 思路:这种题一看就是树套,关键是怎么套,怎么写。(话说我也不会来着。。)最容易想到的方法就是区间线段树套一个权值线段,但是区间线段上的标记就会变得异常复杂。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 480
精华内容 192
关键字:

树可以是什么数字