【正文】 og2n+C是 rect函數(shù)最大調(diào)用次數(shù)的下界。所以此時(shí)，從 n個(gè)硬幣中找出一個(gè)壞硬幣只需 log3n步。 下面進(jìn)行構(gòu)造證明 最后的構(gòu)造 根據(jù)計(jì)算 g(k)時(shí)的推理，第一次比較應(yīng)該有 3k1枚“有嫌疑”的硬幣上天平。雖然這道題的重點(diǎn)在構(gòu)造而不是信息論，但信息論在證明解法的最優(yōu)性時(shí)是十分必要的，而且，信息論的分析也在本題如理亂麻的構(gòu)造過程中起著關(guān)鍵性的指導(dǎo)作用。這樣，第二次比較的方案也被唯一確定了。 ?好球較輕：說明壞硬幣就在這些硬幣中，且較重，由上文結(jié)論，可以在 k1步內(nèi)找出。 現(xiàn)在，有了信息論的武器，這個(gè)遺憾終于得到了解決 ! ？ 初步分析 首先，對硬幣用 1到 n進(jìn)行編號(hào)，設(shè)壞硬幣的編號(hào)為 x。 例 2： Rods(IOI2022) 圖 1 比賽時(shí)我很快想到了一個(gè)最多調(diào)用 rect函數(shù) 6log2n+C（某個(gè)常數(shù)）次的方法，但是因?yàn)檫@個(gè)數(shù)差不多剛好達(dá)到 100，所以我在這時(shí)就開始試圖優(yōu)化上式中 log2n的系數(shù)，結(jié)果徒勞無功，反而耽誤了時(shí)間。(x)是多少？ 解答 3： 此時(shí)貓的只數(shù)為 0,1,2,3的四種情況的概率依次是 (1/8,3/8,3/8,1/8)，而每種情況的熵分別為(0,log3,log3,0)，所以此時(shí) H39。因此，三只貓的狀態(tài)共有 8種可能情況，假設(shè)它們是等概率的。如果至少一個(gè)屬于某個(gè) Rod的方格落在矩形 [a,b]x[c,d] (如圖 1中陰影區(qū)域 )內(nèi)的話，rect返回 1，否則返回 0。于是，那位親戚加大了數(shù)據(jù)規(guī)模 (n=1101， k=7，IMPOSSIBLE)，我想了大概一周，覺得應(yīng)該無解，但苦于無法證明我的解法的最優(yōu)性，始終不能理直氣壯地回答 IMPOSSIBLE。 由于可以通過剩下的 k1次比較把壞硬幣從這 t個(gè)硬幣中找出來，所以 t=g(k1)。 最后的構(gòu)造 因?yàn)檫@三種情況出現(xiàn)的概率相同且必居其一。它可以為我們的解法提供強(qiáng)有力的理論依據(jù)，更可以通過估計(jì)上下界來指導(dǎo)解法的構(gòu)造。 最后的構(gòu)造 但假如比較結(jié)果是“不平衡”呢？此時(shí)，壞硬幣編號(hào)的熵為 log3k1，如果要在 k1次比較內(nèi)找出壞硬幣，那么此后每一次比較結(jié)果的熵都得是 log3。 請看進(jìn)一步的分析： 進(jìn)一步的分析 通過轉(zhuǎn)化，發(fā)現(xiàn)只要計(jì)算出給出一枚好硬幣， k次比較最多在多少枚硬幣（ 不 包括給出的好硬幣）中找出一枚壞硬幣，就可以解