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