散文網(wǎng) » 科技 »學(xué)習(xí) » [Codeforces is All You Need] CR 833 ABC (1748ABC) - Solution

[Codeforces is All You Need] CR 833 ABC (1748ABC) - Solution

2022-11-13 02:30 作者:故寓諸無竟 0人讀過 | 我要投稿

這是ABC的合集題解

問題簡(jiǎn)述

????????Problem A：給定 $n$ ，計(jì)算使用大小為 $1%5Ctimes%20%5Cleft%5Clceil%20%5Cfrac%7Bi%7D%7B2%7D%20%5Cright%5Crceil%20(1%5Cle%20i%5Cle%20n)$ （每個(gè) $i$ 各有一個(gè)）的方塊能拼出的最大的正方形。

????????Problem B：給定一個(gè)長度為 $n$ 的數(shù)字串 $s$ ，求其所有“多樣”的子串。一個(gè)子串“多樣”意味著其中所有的數(shù)字出現(xiàn)的次數(shù)不超過該子串中不同數(shù)字的數(shù)目。

????????Problem C：給定一個(gè)長度為 $n$ 的序列 $a$ ，現(xiàn)在可以將其中的 $0$ 變成任意整數(shù)。求變化后最多有多少個(gè) $a$ 前綴序列之和為 $0$ 。

????????原比賽鏈接：https://codeforces.com/contest/1748

思路

????????Problem A：答案就是 $%5Cleft%5Clceil%20%5Cfrac%7Bn%7D%7B2%7D%20%5Cright%5Crceil$ 。首先說明只有邊長 $%5Cle%20%5Cleft%5Clceil%20%5Cfrac%7Bn%7D%7B2%7D%20%5Cright%5Crceil$ 的正方形才可行：不難發(fā)現(xiàn) $%5Csum_%7Bi%3D1%7D%5E%7Bn%7D%20%5Cleft%5Clceil%20%5Cfrac%7Bi%7D%7B2%7D%20%5Cright%5Crceil%20%3D%20%0A%5Cbegin%7Bcases%7D%0A%5Cleft%5Clceil%20%5Cfrac%7Bn%7D%7B2%7D%20%5Cright%5Crceil%5E2%20%26%2C%20n%20%5C%262%20%3D%201%20%5C%5C%0A%5Cleft%5Clceil%20%5Cfrac%7Bn%7D%7B2%7D%20%5Cright%5Crceil%5E2%2B%5Cleft%5Clceil%20%5Cfrac%7Bn%7D%7B2%7D%20%5Cright%5Crceil%20%3C%20(%5Cleft%5Clceil%20%5Cfrac%7Bn%7D%7B2%7D%20%5Cright%5Crceil%2B1)%5E2%26%20%2C%20n%20%5C%26%202%20%3D%200%0A%5Cend%7Bcases%7D$

（真的不難發(fā)現(xiàn)，就是簡(jiǎn)單的分類討論，然后等差數(shù)列求和），由此可行的正方形邊長不會(huì)超過 $%5Cleft%5Clceil%20%5Cfrac%7Bn%7D%7B2%7D%20%5Cright%5Crceil$ 。也不難構(gòu)造出一個(gè)邊長為 $%5Cleft%5Clceil%20%5Cfrac%7Bn%7D%7B2%7D%20%5Cright%5Crceil$ 的解：取一個(gè) $1%5Ctimes%20%5Cleft%5Clceil%20%5Cfrac%7Bn%7D%7B2%7D%20%5Cright%5Crceil$ 的方塊；此外大小為 $1%5Ctimes%20u$ 和大小為 $1%5Ctimes%20(%20%5Cleft%5Clceil%20%5Cfrac%7Bn%7D%7B2%7D%20%5Cright%5Crceil%20-u)$ 的方塊拼一起作為一組（ $1%20%5Cle%20u%20%3C%20%5Cleft%5Clceil%20%5Cfrac%7Bn%7D%7B2%7D%20%5Cright%5Crceil%2F2$ ）；總共得到恰好 $%5Cleft%5Clceil%20%5Cfrac%7Bn%7D%7B2%7D%20%5Cright%5Crceil$ 組。證畢。

????????Problem B：由于一共就只有 $0%5Csim9$ 這10個(gè)數(shù)字，因此實(shí)際上符合要求的子串長度不超過 $100$ 。直接暴力判斷的復(fù)雜度為 $O(10000n)$ ，略高了。可以使用前綴和優(yōu)化（統(tǒng)計(jì)不同數(shù)字出現(xiàn)次數(shù)的前綴和，這樣可以在 $O(1)$ 內(nèi)計(jì)算每個(gè)數(shù)字出現(xiàn)了多少次），這樣復(fù)雜度為 $O(100n)$ 。

????????Problem C：（貪心）對(duì)于前綴和序列 $s$ ，不難發(fā)現(xiàn)，（1）當(dāng)我們將 $a_i(a_i%3D0)$ 調(diào)整為任意其它整數(shù)時(shí)，等價(jià)于把 $s_j%20(i%5Cle%20j%20%5Cle%20n)$ 同時(shí)增加了某個(gè)整數(shù)。另一個(gè)重要的發(fā)現(xiàn)是，（2）如果我們調(diào)整了 $a_i(a_i%20%3D%200)$ ，如果存在 $a_j%20%3D%200%2C%20j%20%3E%20i$ ，那么 $a_i$ 的調(diào)整對(duì) $s_k%20(j%20%5Cle%20k%20%5Cle%20n)$ 并沒有影響（因?yàn)檎{(diào)整是任意的）。于是，對(duì)于 $a_i%3D0$ ，我們只需要貪心地考慮 $i%5Cle%20k%20%3C%20j$ 下標(biāo)對(duì)應(yīng)的前綴和（其中 $j$ 是 $i$ 之后第一個(gè)為 $0$ 的元素的位置；如果 $i$ 已經(jīng)是最后一個(gè)了，那么 $j%3Dn%2B1$ ）。根據(jù)（1）的結(jié)果，這時(shí)候最佳的貢獻(xiàn)應(yīng)該是該下標(biāo)區(qū)間內(nèi)出現(xiàn)最多的前綴和值。使用std::map就可以輕松地統(tǒng)計(jì)每個(gè)前綴和值出現(xiàn)的次數(shù)?？偟膹?fù)雜度為 $O(n%20%5Clog%20n)$ 。如果用hash表會(huì)更快一點(diǎn)。另外，不要忘記統(tǒng)計(jì)第一個(gè) $0$ 之前的前綴和中值為 $0$ 的個(gè)數(shù)！（因?yàn)檫@個(gè)WA了幾發(fā)。）