[Codeforces is All You Need]CR 827 G (1742G) - Solution

2022-10-14 15:43 作者:故寓諸無竟 0人讀過 | 我要投稿

讓我感覺有點意思的總想寫一個題解。

問題簡述

????????給定一個序列 $a$ ，請將其重新排列，使得前綴按位或得到的序列 $b$ 字典序最大，其中 $b_i%20%3D%20%7C_%7Bj%3D1%7D%5E%7Bi%7D%20a_j$ 。

????????題目鏈接：https://codeforces.com/contest/1742/problem/G

思路

????????由于最后得到的序列長度恒定為 $n$ ，因此字典序最小只需令 $b$ 靠前的項盡可能大，換言之，可以直接構(gòu)造解 $%5Cpi$ ：

$%5Cpi_i%20%3D%20%5Carg%20%5Cmax_%7B%5Bn%5D%20%5Cbackslash%20%5Cpi%5B%3Ai-1%5D%7D%20%5Cleft(%20a_%7B%5Cpi_i%7D%20%7C%20b%5E%7B%5Cpi%7D_%7Bi-1%7D%20%5Cright)$

????????（注：因為任意解均可，當有多個結(jié)果相同時，取最小下標。）我們可以直接如此構(gòu)造，得到一個復雜度為 $O(n%5E2)$ 的算法。但實際上沒有必要：一個int型（哪怕不帶符號）數(shù)至多32位，因此一種樸素的感覺是， $b$ 序列會很快（ $32$ 項之內(nèi)）變成常列，于是此后 $a$ 的排序?qū)⒉辉儆绊?img type="latex" class="latex" src="http://api.bilibili.com/x/web-frontend/mathjax/tex?formula=b" alt="b">的字典序大小。這一樸素的感覺很容易得到證明。

? ? ? ? 假設(shè)對某一個 $i$ ，有 $b_i%5E%7B%5Cpi%7D%20%3D%20b_%7Bi-1%7D%5E%7B%5Cpi%7D$ ，這意味著對任意 $j%20%5Cin%20%5Bn%5D%5Cbackslash%20%5C%7B%5Cpi%5B%3Ai-1%5D%5C%7D$ ，有：

$b_%7Bi-1%7D%5E%7B%5Cpi%7D%20%3D%20a_%7B%5Cpi_i%7D%20%7C%20b_%7Bi-1%7D%5E%5Cpi%20%5Cge%20a_%7Bj%7D%20%7C%20b_%7Bi-1%7D%5E%7B%5Cpi%7D%20%5Cge%20b_%7Bi-1%7D%5E%7B%5Cpi%7D$

????????如果我們將整數(shù)看作集合，上式意味著對任意 $j%20%5Cin%20%5Bn%5D%5Cbackslash%20%5C%7B%5Cpi%5B%3Ai-1%5D%5C%7D$ ，有 $a_j%20%5Csubseteq%20b_%7Bi-1%7D%5E%7B%5Cpi%7D$ 。而注意到 $b$ 的通項按集合為 $b_i%20%3D%20%5Ccup_%7Bj%3D1%7D%5Ei%20a_j$ ，因此有：

$a_j%20%5Csubseteq%20b_%7Bi-1%7D%5E%7B%5Cpi%7D%20%5Csubseteq%20b_%7Bi%7D%5E%7B%5Cpi%7D%20%5Csubseteq%20b_%7Bi%2B1%7D%5E%7B%5Cpi%7D%20%5Csubseteq%20...$

????????根據(jù)上式不難發(fā)現(xiàn)，序列將變?yōu)槌Ａ?，?img type="latex" class="latex" src="http://api.bilibili.com/x/web-frontend/mathjax/tex?formula=b_%7Bi-1%7D%5E%7B%5Cpi%7D%20%3D%20b_%7Bi%7D%5E%7B%5Cpi%7D%20%20%3D%20..." alt="b_%7Bi-1%7D%5E%7B%5Cpi%7D%20%3D%20b_%7Bi%7D%5E%7B%5Cpi%7D%20%20%3D%20...">。而如果 $b_i%5E%7B%5Cpi%7D%20%5Cne%20b_%7Bi-1%7D%5E%7B%5Cpi%7D$ ，則至少集合中多出 $1$ 個元素，而全集僅包含 $32$ 個元素，因此實際上只需要計算 $%5Cpi$ 的前 $32$ 項即可，時間復雜度為 $O(32n)$ 。