gpt4 book ai didi

algorithm - 长波紫外线 - 1394 : And There Was One Algorithm

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:19:22 29 4
gpt4 key购买 nike

问题的链接是UVA - 1394 : And There Was One .
朴素的算法是扫描整个数组并在每次迭代中标记第 k 个元素并在最后停止:这需要 O(n^2) 时间。
我搜索了一种替代算法并遇到了 chinese blog这让我知道线段树使用惰性传播作为 O(N lgN) 时间的解决方案。
研究了线段树后,我尝试在 O(N lgN) 时间内形成一种算法,但无济于事。


我的问题是:
1.线段树可以用于获得所需的运行时间?
2.如果是,请教我如何使用它们。
3。线段树和“zkw”线段树是一回事吗? - 他在博客中提到了 zkw 段树。
更新:上述问题是 Josephus 问题的一个例子。

最佳答案

  1. 是的,可以。

  2. 你可以在下面看到数据结构的描述,这里我只是提示如何在给定的问题中使用它。我们所代表的人口显然是石头圈。我们从所有的 N 石头开始活着,并且在每一步杀死我们树中适当的石头。只需要知道我们当前在哪个元素上(我觉得叫它m比较合适)。高级算法(我把细节留给你)如下(P 是我们的数据结构):

    While P.size > 1:
    P.toggle(m) // remove the m-th stone
    m = P.kth(next stone to be killed)

    上面代码中的 P.size 只是所有剩余石头的数量。在下面的描述中,它对应于tree[1]。

    注意:数据结构中使用的符号k与问题输入中代表跳跃距离的符号不同。 p>

  3. 差不多。我以前没见过这个名字,但代码看起来和我看到的人们所说的人口树一样。

    人口树是使用线段树的一种简单方法。您有 N 个元素,每个元素都有两种可能的状态:1 表示活着,0 表示死了。该树支持两种操作:

    • 切换编号为 i 的元素的状态。
    • 返回第 k 个(按其索引的大小)事件元素的索引。

    为了阐明第二个操作,假设生命元素的集合是 {1, 2, 4, 7}。如果 N = 8,则对应于状态数组 01101001(元素 0 已死,元素 1 是活的,元素 3 是活的,依此类推)。

    那么,如何实现呢?像往常一样,树的叶子对应于数组。也就是说,如果第 i 个元素存活,则第 i 个叶子的值为 1,否则为 0。每个内部节点都记住其子节点值的总和。

    要切换元素的状态,我们切换相应叶子的值,然后固定从该叶子到根的路径:

    const int size = 1 << 18; // 2^17 elements, the rest are internal nodes
    int tree[size]; // number of living elements in the subtree of a node

    void toggle(int i) {
    tree[i + size / 2] ^= 1; // toggle the leaf
    for (i /= 2; i > 0; i /= 2)
    tree[i] = tree[2 * i] + tree[2 * i + 1];
    }

    注意:标记节点的常用方法是让等于 1,然后递归地,节点 n 的子节点是 2n2n+1

    要找到第 k-th 个生命元素,我们可以递归地思考:我们目前在节点 n,并且正在寻找其子树的 k-th 事件元素(节点的子树是以该节点为根的树)。如果n的左 child 2nk个或更多的活元素,设n = 2n 。否则,我们显然会找到正确的 child ,即集合 n = 2n+1。在这种情况下,我们不再寻找子树的第 k 个存活元素。因为我们跳过了左 child 的所有活元素,所以我们从 k 中减去该计数。为简单起见,我们在这里查看基于 1 的生命元素。

    这里的基本思想可能是递归的,但是描述暗示迭代地做它也应该很简单:

    int kth(int k) {
    ++k; // because this method looks at elements 1-based
    int current_node = 1; // start at the root
    while (current_node < size / 2) {
    if (tree[2 * current_node] >= k)
    current_node = 2 * current_node; // descend into the left child
    else {
    k -= tree[2 * current_node]; // fix k
    current_node = 2 * current_node + 1; // descend into the right child
    }
    }
    }

    这两个函数使线段树成为种群树

这是一道数据结构题,所以所描述的思路使用了数据结构。不过,我想提一下,这个问题被称为 Josephus 问题,并且有替代解决方案,因此您可能有兴趣查找它。

关于algorithm - 长波紫外线 - 1394 : And There Was One Algorithm,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14462401/

29 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com