20xxacm區(qū)域賽北京賽區(qū)題目講評(編輯修改稿)
2024-09-03 11:10 本頁面
【文章內(nèi)容簡介】 12+30=42 ?封榜前 AC數(shù)： 5 ?題目解法：預(yù)處理出以集合 S內(nèi)的點(diǎn)構(gòu)成 L拐點(diǎn)的子集個(gè)數(shù)。首先求出允許子集交不為空的有序?qū)€(gè)數(shù)。在此基礎(chǔ)上減去子集的交一定不為空的有序?qū)€(gè)數(shù) 即 可。時(shí)間復(fù)雜度 ??(??3)， X為整點(diǎn)坐標(biāo)的最大值（小于 200） Fluorescent ?題目大意： 有 N盞燈， M個(gè)開關(guān)，每個(gè)開關(guān)可以控制若干盞燈（打開開關(guān)可以反轉(zhuǎn)燈的暗滅狀態(tài)）。在初始的時(shí)候所有燈都是暗的狀態(tài)。每個(gè)開關(guān)以 。令 X表示最后亮著的燈的個(gè)數(shù)，求 ??[??3] ?總提交人數(shù)： 23+36=59 ?封榜前 AC數(shù)： 13 ?題目解法： Fluorescent ?題目解法： ，可枚舉三盞燈，并通過 DP求 出這三盞燈最終同時(shí)處于亮的狀態(tài)的概率。最終答案即為所有概率的總和。 DP的狀態(tài)為 F[I][J][K][L]（依次枚舉至第 I個(gè)開關(guān)，三盞燈的亮滅情況分別是 J,K,L，此情況發(fā)生的概率） DP的時(shí)間復(fù)雜度為 ??(??)?？倳r(shí)間復(fù)雜度 ??(??3??)。 Fluorescent ?題目解法： ，可枚舉三盞燈，求出這三盞燈最終同時(shí)處于亮的狀態(tài)的概率。最終答案即為所有概率的總和。由于該概率可轉(zhuǎn)化為判斷一個(gè) 3*M的矩陣的秩?？捎梦贿\(yùn)算在常數(shù)時(shí)間內(nèi)求解。時(shí)間復(fù)雜度 ??(??3)。 Happy Matt Friends ?題目大意：給 N個(gè)數(shù)構(gòu)成的集合。詢問有多少個(gè)子集滿足，子集中的數(shù)的 異 或和大于等于 M ?總提交人數(shù)： 293+48=341 ?封榜前 AC數(shù)： 135 ?題目解法： Happy Matt Friends ?題目解法： ，高斯消元求解自由元的個(gè)數(shù)。 總時(shí)間復(fù)雜度 ??(??log2 ??3)。 Happy Matt Friends ?題目解法：
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1