淺談二分策略的應(yīng)用-文庫吧資料
2025-01-27 12:56本頁面
【正文】 … X ?? … ? … … ?? … ?? X X Y X YYY X5/19/2023 14 WinterCamp 2023 問題的解決 ?于是，我們可以 二分枚舉 獲勝的 X。 ?解決方法： 枚舉！ 3?1 4?2 7?5 8?6 4?3 8?7 4?8 圖 BTP1 6?7 5?3 4?8 2?1 6?5 4?2 6?4 圖 BTP2 5/19/2023 12 WinterCamp 2023 性質(zhì)：隱含的有序性 ? 如果 排名為 X的選手最終獲勝，那么 排名在 X前 的選手 Y也可以獲勝。 5/19/2023 10 WinterCamp 2023 初步分析 ?由于 N很大，猜想可以通過貪心方法解決。 Answer— 現(xiàn)在觀眾們想知道，哪頭奶牛是所有可能成為冠軍的牛中排名最靠后的。每頭奶牛都有一個 BTP排名，恰為 1－ N。即 N頭奶牛分成 N/2組，每組兩頭奶牛比賽，決出N/2位勝者；所有勝者繼而分成 N/4組比賽 …… 直至剩下一頭牛是冠軍。 如果 ip，我們將范圍確定為 S中比 x小的元素，求該范圍內(nèi)第 i個元素； 如果 i=p，表示第 i小的元素就是 x ip，我們將范圍確定為 大的元素，求該范圍內(nèi)第 p1個元素； 5/19/2023 7 WinterCamp 2023 小結(jié) ?舉這個例子，是想說明兩點(diǎn)： ? 第一，二分查找 == logn ? 第二，二分查找 == 平均 ? ?5/19/2023 8 WinterCamp 2023 類型二：二分枚舉 —— 應(yīng)用于退化了的有序序列 ?與類型一中的二分查找相比， 最大的區(qū)別 在于這里的二分在判斷選擇哪一個部分遞歸調(diào)用時沒有了 比較運(yùn)算 *。二分策略 在信息學(xué)競賽中的 應(yīng)用 華東師大二附中 楊俊 5/19/2023 1 Winter
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1