算法合集之《信息論在信息學(xué)競賽中的簡單應(yīng)用》-文庫吧
2025-09-17 03:11 本頁面
【正文】 39。(x)。 定理 1得到了驗證。 例 2： Rods(IOI2021) 一個 Rod是一個由至少 2個單位正方形連成的水平或豎直的長條。在一個 N*N的方陣中，放了水平和豎直兩個 Rod。如圖 1，其中 Rod用 X表示。 圖 1 例 2： Rods(IOI2021) 兩個 Rod可能有公共方格，比如在圖 1中，方格（ 4， 4）無法確定是僅屬于 1個 Rod還是同時屬于兩個 Rod。因此，在這種情況下我們假定它同時屬于兩個 Rod。這樣，圖中豎直 Rod的上端點是（ 4， 4）而不是（ 5， 4）。 圖 1 最初我們并不知道兩個 Rod的位置，你的任務(wù)是編程序找出它們的位置。你只能通過庫函數(shù) rect(a,b,c,d)來定位兩個 Rod。如果至少一個屬于某個 Rod的方格落在矩形 [a,b]x[c,d] (如圖 1中陰影區(qū)域 )內(nèi)的話，rect返回 1，否則返回 0。 例 2： Rods(IOI2021) 圖 1 對每個測試點，如果你的程序沒有正確確定兩個 Rod的位置或調(diào)用 rect超過 400次，你將得到 0分。否則，如果調(diào)用 rect的次數(shù)至多為100，你將得到 5分；在101到 200間，你將得到3分；在 201到 400間，你將得到 1分。 例 2： Rods(IOI2021) 圖 1 比賽時我很快想到了一個最多調(diào)用 rect函數(shù) 6log2n+C（某個常數(shù)）次的方法，但是因為這個數(shù)差不多剛好達(dá)到 100，所以我在這時就開始試圖優(yōu)化上式中 log2n的系數(shù)，結(jié)果徒勞無功，反而耽誤了時間。因此，看過答案以后，我試著從信息論的角度分析了一下這個問題： 例 2： Rods(IOI2021) 6log2n+C? 由于題目中沒有涉及到概率，因此假設(shè)所有情況都是等概率的。所以，設(shè) Rod的擺放方法為隨機變量 x， x所有可能的取值數(shù)為 f(n)，那么 x的熵 H(x)就等于 log(f(n))。而由于庫函數(shù)只有兩種返回值，其熵最大為 Hmax(y)=log2。因此， rect調(diào)用次數(shù)的信息論下界就是 L=H(x)/Hmax(y)=log(f(n))/log2=log2f(n) 例 2： Rods(IOI2021) 在 n*n的方陣中放 1個 Rod（無論橫豎）共有 n*
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1