[Codeforces is All You Need] ER 137 D (1743D) - Solution

2022-10-18 01:25 作者:故寓諸無(wú)竟 0人讀過(guò) | 我要投稿

問(wèn)題簡(jiǎn)述

????????給定一個(gè) $0%2F1$ 串，要求找到它的兩個(gè)子串（可以有重疊），使得兩個(gè)子串表示的二進(jìn)制數(shù)按位或的結(jié)果最大。

????????題目鏈接：https://codeforces.com/contest/1743/problem/D

思路

????????“隨機(jī)生成”、“不允許Hack”。這樣的字眼提示非常明顯了——本題大概率需要利用隨機(jī)性質(zhì)來(lái)保證復(fù)雜度/貪心的正確性等。

????????首先不難發(fā)現(xiàn)兩個(gè)樸素的事實(shí)：1）給定字符串的前導(dǎo)零對(duì)于問(wèn)題而言毫無(wú)意義；2）讓其中一個(gè)子串從首個(gè)非零位延展到末位一定是最優(yōu)解的一部分。這樣問(wèn)題轉(zhuǎn)化為，假設(shè)原字符串刪去前導(dǎo)零之后的字符串為 $s$ ，求：

$%5Cmax_%7Bt%20%5Csubseteq%20s%7D%20s%20%7C%20t$

? ? ? ? 其中 $t$ 是 $s$ 的一個(gè)子串。這里將字符和其表示的二進(jìn)制數(shù)混用了，但不會(huì)帶來(lái)理解的困難。

????????即然問(wèn)題是按位或，那么關(guān)鍵的肯定是 $s$ 的 $0$ 的位置，假設(shè)首個(gè) $0$ 的位置是 $u$ 。由于 $s$ 必然以 $1$ 開(kāi)頭，因此不難發(fā)現(xiàn)，取 $t_x%3D1...(%E4%B8%80%E5%85%B1%7Cs%7C-u%E4%BD%8D)$ 時(shí)，按位或能將 $s$ 的 $u$ 處的 $0$ 轉(zhuǎn)變?yōu)?img type="latex" class="latex" src="http://api.bilibili.com/x/web-frontend/mathjax/tex?formula=1" alt="1">。由于越高位位權(quán)越大，那么如果某子串不能將 $s$ 的 $u$ 處的 $0$ 轉(zhuǎn)變?yōu)?img type="latex" class="latex" src="http://api.bilibili.com/x/web-frontend/mathjax/tex?formula=1" alt="1">，則一定比 $t_x$ 更差。這就意味著，最優(yōu)的子串 $t$ 必須以前 $u-1$ 個(gè) $1$ 中的某一個(gè)開(kāi)頭，且長(zhǎng)度至少為 $%7Cs%7C-u$ 。

????????由此，可以得到一個(gè)復(fù)雜度為 $O(u%5E2%7Cs%7C)$ 的暴力的枚舉算法。但由于生成數(shù)據(jù)的隨機(jī)性，我們得到 $p$ 的分布如下：

$P(u%20%3E%20u_0)%20%3D%20%5Cleft(%5Cfrac%7B1%7D%7B2%7D%5Cright)%5E%7Bu_0%7D$

????????那么，不小于概率 $p$ 地，該算法的實(shí)際復(fù)雜度為： $O(%7Cs%7C%5Ccdot%20%5Cleft%5B%5Clog_2%20%5Cfrac%7B1%7D%7B1-p%7D%5Cright%5D%5E2)$ ，取 $p%3D0.999$ 時(shí)，已經(jīng)能以超過(guò) $96%5C%25$ 的概率通過(guò)全部測(cè)試點(diǎn)（40個(gè)），而此時(shí)復(fù)雜度還不到 $O(100%5Ccdot%20%7Cs%7C)$ ，可以通過(guò)本題。