UVA - 1394：有一種算法

問題的鏈接是UVA - 1394 : And There Was One。
樸素的算法是掃描整個數組並在最後一次停止的每次迭代中標記第k個元素：這需要O（n^2）時間。
我已經搜索了一種替代算法，並且遇到了一個chinese blog，它指向我分段樹使用懶惰傳播作爲O（N lgN）時間的解決方案。
研究了分段樹之後，我試圖形成O（N lgN）時間的算法，但無濟於事。
UVA - 1394：有一種算法

我的問題是：
1.段樹是否可以用來獲得所需的運行時間？
2.如果是，請告訴我如何使用它們。
3.段樹和「zkw」段樹是否相同？ - 他在博客中提到zkw分段樹。
UPDATE：上述問題是約瑟夫問題的一個示例..

來源

2013-01-22 jemmanuel

是它可以。
你可以看到下面的數據結構的描述，這裏我只是提示如何在給定的問題中使用它。我們代表的人口顯然是石頭圈。我們從所有的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在上面的代碼只是所有剩餘棋子的數量。在下面的描述中，它對應於樹[1]。

注：在該數據結構中所用的符號ķ是從一個在問題輸入表示跳躍距離不同。
非常多。我以前沒有見過這個名字，但代碼看起來與我所看到的人們所稱的種羣樹一樣。

種羣樹是使用分段樹的簡單方法。您有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，並遞歸地，的一個節點ñ的兒童是2n個和2N + 1。

要了解我們可以遞歸認爲第k個生活元素：我們目前正處在節點ñ，並正在尋找第k個生活元素及其子樹（節點的子樹是以該節點爲根的樹）。如果Ñ的左子2n個已ķ或多個活元件，設置Ñ = 的2n。否則，我們顯然會去正確的孩子，那就是設置n = 2n + 1。在這種情況下，我們不再尋找子樹的活動元素第k個。因爲我們跳過了左側孩子的所有生活元素，所以我們從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 
    } 
    } 
} 
```
這兩個功能是什麼使這段樹一個人口樹。

這是一個數據結構問題，所以所描述的想法使用數據結構。但是，我想提一下，這個問題被稱爲約瑟夫問題，並有其他解決方案，因此您可能有興趣查找它。

來源

2013-01-22 17:42:04 gus

我有點形成了這個想法（發現下一個元素是在左側或右側的孩子，然後遞歸），但它是陰天...和thnx很多引用約瑟夫問題...我會給+2如果可能的話... – jemmanuel

UVA - 1394：有一種算法

回答

相關問題