- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
问题的链接是UVA - 1394 : And There Was One .
朴素的算法是扫描整个数组并在每次迭代中标记第 k 个元素并在最后停止:这需要 O(n^2) 时间。
我搜索了一种替代算法并遇到了 chinese blog这让我知道线段树使用惰性传播作为 O(N lgN) 时间的解决方案。
研究了线段树后,我尝试在 O(N lgN) 时间内形成一种算法,但无济于事。
最佳答案
是的,可以。
你可以在下面看到数据结构的描述,这里我只是提示如何在给定的问题中使用它。我们所代表的人口显然是石头圈。我们从所有的 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>
差不多。我以前没见过这个名字,但代码看起来和我看到的人们所说的人口树一样。
人口树是使用线段树的一种简单方法。您有 N 个元素,每个元素都有两种可能的状态:1 表示活着,0 表示死了。该树支持两种操作:
为了阐明第二个操作,假设生命元素的集合是 {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 的子节点是 2n 和 2n+1。
要找到第 k-th 个生命元素,我们可以递归地思考:我们目前在节点 n,并且正在寻找其子树的 k-th 事件元素(节点的子树是以该节点为根的树)。如果n的左 child 2n有k个或更多的活元素,设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/
我在一本书(Interview Question)中读到这个问题,想在这里详细讨论这个问题。请点亮它。 问题如下:- 隐私和匿名化 马萨诸塞州集团保险委员会早在 1990 年代中期就有一个绝妙的主意
我最近接受了一次面试,面试官给了我一些伪代码并提出了相关问题。不幸的是,由于准备不足,我无法回答他的问题。由于时间关系,我无法向他请教该问题的解决方案。如果有人可以指导我并帮助我理解问题,以便我可以改
这是我的代码 public int getDist(Node root, int value) { if (root == null && value !=0) return
就效率而言,Strassen 算法应该停止递归并应用乘法的最佳交叉点是多少? 我知道这与具体的实现和硬件密切相关,但对于一般情况应该有某种指南或某人的一些实验结果。 在网上搜索了一下,问了一些他们认为
我想学习一些关于分布式算法的知识,所以我正在寻找任何书籍推荐。我对理论书籍更感兴趣,因为实现只是个人喜好问题(我可能会使用 erlang(或 c#))。但另一方面,我不想对算法进行原始的数学分析。只是
我想知道你们中有多少人实现了计算机科学的“ classical algorithms ”,例如 Dijkstra's algorithm或现实世界中的数据结构(例如二叉搜索树),而不是学术项目? 当有
我正在解决旧编程竞赛中的一些示例问题。在这个问题中,我们得到了我们有多少调酒师以及他们知道哪些食谱的信息。制作每杯鸡尾酒需要 1 分钟,我们需要使用所有调酒师计算是否可以在 5 分钟内完成订单。 解决
关闭。这个问题是opinion-based .它目前不接受答案。 想要改进这个问题? 更新问题,以便 editing this post 可以用事实和引用来回答它. 关闭 8 年前。 Improve
我开始学习 Nodejs,但我被困在中间的某个地方。我从 npm 安装了一个新库,它是 express -jwt ,它在运行后显示某种错误。附上代码和错误日志,请帮助我! const jwt = re
我有一个证书,其中签名算法显示“sha256rsa”,但指纹算法显示“sha1”。我的证书 SHA1/SHA2 的标识是什么? 谢谢! 最佳答案 TL;TR:签名和指纹是完全不同的东西。对于证书的强度
我目前在我的大学学习数据结构类(class),并且在之前的类(class)中做过一些算法分析,但这是我在之前的类(class)中遇到的最困难的部分。我们现在将在我的数据结构类(class)中学习算法分
有一个由 N 个 1x1 方格组成的区域,并且该区域的所有部分都是相连的(没有任何方格无法到达的方格)。 下面是一些面积的例子。 我想在这个区域中选择一些方块,并且两个相邻的方块不能一起选择(对角接触
我有一些多边形形状的点列表,我想将其包含在我页面上的 Google map 中。 我已经从原始数据中删除了尽可能多的不必要的多边形,现在我剩下大约 12 个,但它们非常详细以至于导致了问题。现在我的文
我目前正在实现 Marching Squares用于计算等高线曲线,我对此处提到的位移位的使用有疑问 Compose the 4 bits at the corners of the cell to
我正在尝试针对给定算法的约束满足问题实现此递归回溯函数: function BACKTRACKING-SEARCH(csp) returns solution/failure return R
是否有包含反函数的库? 作为项目的一部分,我目前正在研究测向算法。我正在使用巴特利特相关性。在 Bartlett 相关性中,我需要将已经是 3 次矩阵乘法(包括 Hermitian 转置)的分子除以作
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 这个问题似乎与 help center 中定义的范围内的编程无关。 . 关闭 8 年前。 Improve
问题的链接是UVA - 1394 : And There Was One . 朴素的算法是扫描整个数组并在每次迭代中标记第 k 个元素并在最后停止:这需要 O(n^2) 时间。 我搜索了一种替代算法并
COM 中创建 GUID 的函数 (CoCreateGUID) 使用“分散唯一性算法”,但我的问题是,它是什么? 谁能解释一下? 最佳答案 一种生成 ID 的方法,该 ID 具有一定的唯一性保证,而不
在做一个项目时我遇到了这个问题,我将在这个问题的实际领域之外重新措辞(我想我可以谈论烟花的口径和形状,但这会使理解更加复杂).我正在寻找一种(可能是近似的)算法来解决它。 我有 n 个不同大小的容器,
我是一名优秀的程序员,十分优秀!