分治

1/3ページ

分治

分治的基本概念 把一個任務,分為形式和原任務相同,但是規模更小的幾個部分任務,分別完成,或只需要選一部分完成。然後再處理完成後的這一個或幾部分的結果,實現整個任務的完成。 分治的生活例子——稱假幣 分治的典型應用:歸併排序 陣列排序任務可以如下完成: 把前一半排序 把後一半排序 把兩半歸併到一個新的 […]

【大話資料結構&演算法】快速排序演算法

快速排序是交換類的排序,比如在站隊的時候,老師說:“第一個同學出列,其他同學以第一個同學為中心,比他矮的全排在左邊,比他高的全排在右邊。”這就是一趟快速排序。可以看出,一趟快速排序是以一個“樞軸”為中心,將序列分成兩個部分,樞軸的一邊全是比它小(或者小於等於)的,另一邊則全是比它大(或者大於等於)的 […]

[bzoj3720]Gty的妹子樹 解題報告

大概看了一眼網上的題解,跟塊爺一樣都寫的會被卡的分塊。(反正塊爺出的題也不會卡自己。。) 這裡說一種比較科學的做法。就是用塊鏈維護dfs序。 維護每個節點按dfs序是在哪個塊的哪個位置,對每個塊維護塊中節點的最淺深度、它的下一個塊是哪個塊,塊中節點按dfs序排序的序列,按權值排序的序列。 一開始的時 […]

BZOJ4555: [Tjoi2016&Heoi2016]求和

我們省選的題… 考慮這個式子的組合意義,對於每一個i,列舉j表示將i個小球放入j個有序集合,且每個集合選擇或者不選的方案數。 我們用f[i]表示將i個小球放入任意個有序集合,且每個集合選擇或不選的方案數,則列舉最後一個集合的大小i-j,可以得到遞推式: for(int i = 1;i <=n […]

平面最近點對 洛谷1257 分治 c

題目描述 給定平面上n個點,找出其中的一對點的距離,使得在這n個點的所有點對中,該距離為所有點對中最小的。 輸入格式: 第一行:n;2≤n≤10000 接下來n行:每行兩個實數:x y,表示一個點的行座標和列座標,中間用一個空格隔開。 輸出格式: 僅一行,一個實數,表示最短距離,精確到小數點後面4位 […]

瑞士輪 洛谷1309 排序

題目背景 在雙人對決的競技性比賽,如乒乓球、羽毛球、國際象棋中,最常見的賽制是淘汰賽和迴圈賽。前者的特點是比賽場數少,每場都緊張刺激,但偶然性較高。後者的特點是較為公平,偶然性較低,但比賽過程往往十分冗長。 本題中介紹的瑞士輪賽制,因最早使用於1895年在瑞士舉辦的國際象棋比賽而得名。它可以看作是淘 […]

bzoj4059 [Cerc2012]Non-boring sequences 分治

Description 我們害怕把這道題題面搞得太無聊了,所以我們決定讓這題超短。一個序列被稱為是不無聊的,僅當它的每個連續子序列存在一個獨一無二的數字,即每個子序列裡至少存在一個數字只出現一次。給定一個整數序列,請你判斷它是不是不無聊的。 1 <= n <= 200000。接下來一行n […]