國家集訓(xùn)隊20xx論文集-侯啟明-文庫吧資料
2025-07-31 03:36本頁面
【正文】 界是達不到的，不過如果沒有這個結(jié)論，真正最優(yōu)的解法的最優(yōu)性就無從證明。 ∴ 從 n個硬幣中通過天平找出一個壞硬幣至少需要 H(x)/Hmax(y)=log3n步 初步分析 下面通過構(gòu)造證明當(dāng)知道壞硬幣比好硬幣輕還是重的時候，這個下界是可以達到的： 每次把所有硬幣分成三等份，比較其中兩份，如果平衡，說明壞硬幣在第三份中，否則壞硬幣就在重的一份中，這樣每次比較得到三種結(jié)果的概率相等， H(y)≡Hmax(y)?？梢哉J(rèn)為 x的所有取值情況概率相等： ∴ H(x)=logn。于是，這件事就成了我這兩年來的一個遺憾。于是，那位親戚加大了數(shù)據(jù)規(guī)模 (n=1101， k=7，IMPOSSIBLE)，我想了大概一周，覺得應(yīng)該無解，但苦于無法證明我的解法的最優(yōu)性，始終不能理直氣壯地回答 IMPOSSIBLE。IMPOSSIBLE39。POSSIBLE39。所有好的硬幣的質(zhì)量是相同的，但壞的硬幣的質(zhì)量卻不一樣，現(xiàn)在告訴你某一枚是好的，能否用一架天平在 k次以內(nèi)稱出哪個是壞的硬幣。這樣，在得到一個這樣的算法之后，就沒有什么必要再去徒勞地優(yōu)化步數(shù)了。而由于庫函數(shù)只有兩種返回值，其熵最大為 Hmax(y)=log2。因此，看過答案以后，我試著從信息論的角度分析了一下這個問題： 例 2： Rods(IOI2022) 6log2n+C? 由于題目中沒有涉及到概率，因此假設(shè)所有情況都是等概率的。否則，如果調(diào)用 rect的次數(shù)至多為100，你將得到 5分；在101到 200間，你將得到3分；在 201到 400間，你將得到 1分。如果至少一個屬于某個 Rod的方格落在矩形 [a,b]x[c,d] (如圖 1中陰影區(qū)域 )內(nèi)的話，rect返回 1，否則返回 0。 圖 1 最初我們并不知道兩個 Rod的位置，你的任務(wù)是編程序找出它們的位置。因此，在這種情況下我們假定它同時屬于兩個 Rod。如圖 1，其中 Rod用 X表示。 例 2： Rods(IOI2022) 一個 Rod是一個由至少 2個單位正方形連成的水平或豎直的長條。(x)。(x)的數(shù)學(xué)期望為： H39。由于種種原因，我希望知道貓當(dāng)時的狀況，因此，我往上看了一眼，結(jié)果發(fā)現(xiàn)在這個位置只能知道屋內(nèi)貓的只數(shù) …… 例 1：驗證一下定理 1 問題 1： 把所有貓的情況作為一個隨機變量 x，則當(dāng)我在小賣部的時候， x的熵
公司管理相關(guān)推薦
鄂ICP備17016276號-1