國(guó)家集訓(xùn)隊(duì)20xx論文集-侯啟明(編輯修改稿)
2024-08-21 03:36 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 n+1,2)種方案，放兩個(gè)相交的 Rod共有 C2(n+2,3)種方案，所以： f(n)=(n2(n+1)/2)2((n+2)(n+1)n/6)2 =(2n6+3n5n43n3n2)/9 當(dāng) n充分大時(shí)： L=log(f(n))/log2log2(2n6/9)≈ 例 2： Rods(IOI2022) 下面討論 f(n)的值： 由于各種原因，不一定總是使兩種返回值概率相等，所以最壞情況下的調(diào)用次數(shù)往往達(dá)不到信息論下界，兩者大約相差一個(gè)常數(shù)，因此，可以認(rèn)為 6log2n+C是 rect函數(shù)最大調(diào)用次數(shù)的下界。這樣，在得到一個(gè)這樣的算法之后，就沒有什么必要再去徒勞地優(yōu)化步數(shù)了。 例 2： Rods(IOI2022) 6log2n+C! 例 3： Coins(選手推薦題 0024，推薦者饒向榮 ) 有一堆 n個(gè)硬幣，其中有 n1個(gè)好的，一個(gè)壞的。所有好的硬幣的質(zhì)量是相同的，但壞的硬幣的質(zhì)量卻不一樣，現(xiàn)在告訴你某一枚是好的，能否用一架天平在 k次以內(nèi)稱出哪個(gè)是壞的硬幣。 輸入 n和 k，如果能在 k此比較中找到 n枚硬幣中的哪枚為壞的，就輸出 39。POSSIBLE39。，否則輸出 39。IMPOSSIBLE39。 例 3： Coins(選手推薦題 0024，推薦者饒向榮 ) 兩年前我的一位遠(yuǎn)房親戚曾給我出過(guò)一個(gè)類似的題目（ n=14， k=3），當(dāng)時(shí)我苦苦思索了一晚上，終于想出來(lái)一個(gè)可行解法。于是，那位親戚加大了數(shù)據(jù)規(guī)模 (n=1101， k=7，IMPOSSIBLE)，我想了大概一周，覺得應(yīng)該無(wú)解，但苦于無(wú)法證明我的解法的最優(yōu)性，始終不能理直氣壯地回答 IMPOSSIBLE。 例 3： Coins(選手推薦題 0024，推薦者饒向榮 ) 后來(lái)她給了我一個(gè) 說(shuō)明 ，但我始終覺得不太嚴(yán)密；拿來(lái)問(wèn)我們班的 IMO金牌，回答是顯然 ，我覺得也不嚴(yán)密 :(。于是，這件事就成了我這兩年來(lái)的一個(gè)遺憾。 現(xiàn)在，有了信息論的武器，這個(gè)遺憾終于得到了解決 ! ？ 初步分析 首先，對(duì)硬幣用 1到 n進(jìn)行編號(hào)，設(shè)壞硬幣的編號(hào)為 x。可以認(rèn)為 x的所有取值情況概率相等： ∴ H(x)=logn。 ∵ 用天平稱一次的結(jié)果 y只有 3種可能情況（左邊較重，右邊較重，平衡） ∴ Hmax(y)=log3。
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1