算法合集之信息論在信息學(xué)競賽中的簡單應(yīng)用-wenkub
2022-10-31 03:11:35 本頁面
【正文】 一個(gè)常數(shù)，因此，可以認(rèn)為 6log2n+C是 rect函數(shù)最大調(diào)用次數(shù)的下界。 例 2： Rods(IOI2021) 圖 1 比賽時(shí)我很快想到了一個(gè)最多調(diào)用 rect函數(shù) 6log2n+C（某個(gè)常數(shù)）次的方法，但是因?yàn)檫@個(gè)數(shù)差不多剛好達(dá)到 100，所以我在這時(shí)就開始試圖優(yōu)化上式中 log2n的系數(shù)，結(jié)果徒勞無功，反而耽誤了時(shí)間。你只能通過庫函數(shù) rect(a,b,c,d)來定位兩個(gè) Rod。 圖 1 例 2： Rods(IOI2021) 兩個(gè) Rod可能有公共方格，比如在圖 1中，方格（ 4， 4）無法確定是僅屬于 1個(gè) Rod還是同時(shí)屬于兩個(gè) Rod。 定理 1得到了驗(yàn)證。(x)是多少？ 解答 3： 此時(shí)貓的只數(shù)為 0,1,2,3的四種情況的概率依次是 (1/8,3/8,3/8,1/8)，而每種情況的熵分別為(0,log3,log3,0)，所以此時(shí) H39。于是，每只貓就有了兩種狀態(tài)：在屋內(nèi)和在屋外。 ?通過它可以很方便地得到某些交互式問題的一個(gè)較好的步數(shù)下界 (“ 信息論下界” ) 讓我們先來看一些信息論的基本理論 理論基礎(chǔ) ?定義：如果一個(gè)隨機(jī)變量 x共有 n種取值，概率分別為 p0,p2,......,pn，則其熵為H(x)=f(p0,p2,......,pn)=∑Cpilogpi ?定理 1：在得到關(guān)于隨機(jī)變量 x的一個(gè)熵為 h的信息后， x的熵將會(huì)減少 h。 ?定理 2：當(dāng)一個(gè)隨機(jī)變量的各種取值概率相等時(shí)，它的熵最大。因此，三只貓的狀態(tài)共有 8種可能情況，假設(shè)它們是等概率的。(x)的數(shù)學(xué)期望為： H39。 例 2： Rods(IOI2021) 一個(gè) Rod是一個(gè)由至少 2個(gè)單位正方形連成的水平或豎直的長條。因此，在這種情況下我們假定它同時(shí)屬于兩個(gè) Rod。如果至少一個(gè)屬于某個(gè) Rod的方格落在矩形 [a,b]x[c,d] (如圖 1中陰影區(qū)域 )內(nèi)的話，rect返回 1，否則返回 0。因此，看過答案以后，我試著從信息論的角度分析了一下這個(gè)問題： 例 2： Rods(IOI2021) 6log2n+C? 由于題目中沒有涉及到概率，因此假設(shè)所有情況都是等概率的。這樣，在得到一個(gè)這樣的算法之后，就沒有什么必要再去徒勞地優(yōu)化步數(shù)了。POSSIBLE39。于是，那位親戚加大了數(shù)據(jù)規(guī)模 (n=1101， k=7，IMPOSSIBLE)，我想了
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1