Codeforces Round #833 (Div. 2)

2022-11-16 02:29 作者:Asunataisiki 0人讀過 | 我要投稿

A.The Ultimate Square

題意：你有n個長方體，每個長方形的高為1，寬為? $%5Clceil%20i%2F2%5Crceil%20$ ，你可以選擇一些長方形拼成一個正方形，使得正方形的邊長最大，求最大邊長

思路：手玩幾組樣例后發(fā)現(xiàn)，最大長度就是? $%5Clceil%20n%5Crceil%20$

B.Diverse Substrings

題意：定義一個字符串是好的，即數(shù)字字符種類數(shù)大于等于所有數(shù)字字符中出現(xiàn)最多的次數(shù)，求字符串的所有子串中有多少個字符串是好的

思路：首先數(shù)字字符一共只有10種，那么極限情況下10種字符各出現(xiàn)10次也就是100個字符，也就是說這個子串如果是好的，那么長度最長為100，那么就可以暴力了

C. Zero-Sum Prefixes

題意：定義某個前綴是好的，即這個前綴和為0，對于每個 $a_i%3D0$ 的位置，可以將它們變成任意的數(shù)字，求最大有多少個前綴是好的

思路：如果讓 $a_i%3D0$ 加上 $x$ ，即代表 $%5Bi%20%2C%20n%5D$ 的每個位置都加 $x$ ，如果此時有 $a_j%3D0(j%3Ei)$ ，先減去 $x$ ，再讓其加上 $y$ ，也就是說其實兩次操作只在 $%5Bj%20%2C%20n%5D$ 加上了 $y$ ，那么對于 $a_i$ ，我們就只用考慮 $%5Bi%2C%20j%20-%201%5D$ 這個區(qū)間了（因為操作 $a_j$ ，可以讓操作 $a_i$ 時對 $%5Bj%2Cn%5D$ 的影響消失），那么我們只用統(tǒng)計 $a_i$ 到 $a_j$ 這段區(qū)間里的前綴和出現(xiàn)次數(shù)最多的數(shù)，讓 $a_i$ 變成這個數(shù)字的相反數(shù)即可

D.ConstructOR

題意：給出a, b, d，求x，使得 (a | x) % d == 0 && (b | x) % d == 0

思路：首先，如果a末尾連續(xù)0的個數(shù)小于d末尾連續(xù)0的個數(shù)，那么一定是無解的，假設(shè)d末尾連續(xù)0的個數(shù)為k，那么d一定含有 $2%5Ek$ 這個因子，而a一定不含，or操作后的數(shù)也一定不含，則無解，b也是同樣的道理

接下來考慮如何構(gòu)造一個d的倍數(shù)，首先考慮，如果當前x這一位為1，那么or操作之后這一位一定也為1，所以可以不用考慮，如果這一位為0，那么or之后的結(jié)果就取決于a或者b這一位為1還是0了，那么我們考慮把這一位變成1，并且變的過程中保持x為d的倍數(shù)就可以了，既然要是d的倍數(shù)，那么一定用d來變這一位，那么我們可以考慮用d的最低位為1的那一位來填充，具體來說就是 x += d << (i - k);，即把k這個數(shù)字左移i - k位，讓他的末尾1與這一位1對其，這樣構(gòu)造出來一定是d的倍數(shù)，并且a | x = b | x。

標簽：