A: 排列字母(簽到題)

小藍(lán)要把一個(gè)字符串中的字母按其在字母表中的順序排列。

例如，LANQIAO 排列后為 AAILNOQ。

又如，GOODGOODSTUDYDAYDAYUP 排列后為 AADDDDDGGOOOOPSTUUYYY

請(qǐng)問(wèn)對(duì)于以下字符串，排列之后字符串是什么？

WHERETHEREISAWILLTHEREISAWAY

根據(jù)ANCII值直接排序即可, 時(shí)間復(fù)雜度:(nlgn)

B: 特殊時(shí)間 (枚舉)

2022 年 2 月 22 日 22:20 是一個(gè)很有意義的時(shí)間，年份為 2022，由 3 個(gè) 2 和 1 個(gè) 0 組成，如果將月和日寫成 4 位，為 0222，也是由 3 個(gè) 2 和 1 個(gè) 0 組

成，如果將時(shí)間中的時(shí)和分寫成 4 位，還是由 3 個(gè) 2 和 1 個(gè) 0 組成。

小藍(lán)對(duì)這樣的時(shí)間很感興趣，他還找到了其它類似的例子，比如 111 年 10

月 11 日 01:11，2202 年 2 月 22 日 22:02 等等。

請(qǐng)問(wèn)，總共有多少個(gè)時(shí)間是這種年份寫成 4 位、月日寫成 4 位、時(shí)間寫成

4 位后由 3 個(gè)一種數(shù)字和 1 個(gè)另一種數(shù)字組成。注意 1111 年 11 月 11 日 11:11

不算，因?yàn)樗锩鏇](méi)有兩種數(shù)字。

由于年份沒(méi)有限制, 我們只要判斷枚舉出來(lái)的月份和時(shí)間是否合法就行了, 然后利用乘法原理就可以計(jì)算出有多少個(gè)特殊時(shí)間了!

另外有一個(gè)更奇妙的方法: 我們可以推出實(shí)際上滿足的月份日期只有16種, 再每個(gè)日期月份排列看看時(shí)間合法的數(shù)量, 再根據(jù)乘法原理相乘就會(huì)得出答案:

C.紙張尺寸 (模擬)

在 ISO 國(guó)際標(biāo)準(zhǔn)中定義了 A0 紙張的大小為 1189mm × 841mm，將 A0 紙沿長(zhǎng)邊對(duì)折后為 A1 紙，大小為 841mm × 594mm，在對(duì)折的過(guò)程中長(zhǎng)度直接取下整（實(shí)際裁剪時(shí)可能有損耗）。將 A1 紙沿長(zhǎng)邊對(duì)折后為 A2 紙，依此類推。?

輸入紙張的名稱，請(qǐng)輸出紙張的大小。?

樣例輸入

A0

樣例輸出

1189 841

直接模擬, 時(shí)間復(fù)雜度 O(n):

D.求和 (前綴和)

給定 n 個(gè)整數(shù) a1, a2, · · · , an?，求它們兩兩相乘再相加的和，即 S = a1?· a2?+ a1?· a3?+ · · · + a1?· an?+ a2?· a3?+ · · · + an-2?· an-1?+ an-2?· an?+ an-1?· an.

對(duì)于 30% 的數(shù)據(jù)，1 ≤ n ≤ 1000，1 ≤ ai?≤ 100。

對(duì)于所有評(píng)測(cè)用例，1 ≤ n ≤ 200000，1 ≤ ai?≤ 1000。

注意到 n 的范圍會(huì)達(dá)到 200000 (10^5數(shù)量級(jí)), 如果我們直接用兩個(gè) for 循環(huán)枚舉的話時(shí)間復(fù)雜度會(huì)達(dá)到 O(n^2) 超出時(shí)間限制. 我們觀察到S 實(shí)際上等于

a1 * (a2?+?a3 + ... + an) + a2 * (a3 + a4 + ... + an) + ... + an-1(an)

假如我們計(jì)算出數(shù)組的前綴和pre, 于是答案就為 ,于是我們就可以只用一個(gè) for 循環(huán)將時(shí)間復(fù)雜度優(yōu)化到 O(n) 級(jí)別了(求和可能會(huì)溢出，C++要開(kāi)long long):

E.數(shù)位排序 (模擬 + 排序)

小藍(lán)對(duì)一個(gè)數(shù)的數(shù)位之和很感興趣，今天他要按照數(shù)位之和給數(shù)排序。當(dāng)兩個(gè)數(shù)各個(gè)數(shù)位之和不同時(shí)，將數(shù)位和較小的排在前面，當(dāng)數(shù)位之和相等時(shí)，將數(shù)值小的排在前面。

例如，2022 排在 409 前面，因?yàn)?2022 的數(shù)位之和是 6，小于 409 的數(shù)位之和 13。

又如，6 排在 2022 前面，因?yàn)樗鼈兊臄?shù)位之和相同，而 6 小于 2022。

給定正整數(shù) n，m，請(qǐng)問(wèn)對(duì) 1 到 n 采用這種方法排序時(shí)，排在第 m 個(gè)的元素是多少？?

對(duì)于 30% 的評(píng)測(cè)用例，1 ≤ m ≤ n ≤ 300。

對(duì)于 50% 的評(píng)測(cè)用例，1 ≤ m ≤ n ≤ 1000。

對(duì)于所有評(píng)測(cè)用例，1 ≤ m ≤ n ≤ 106。?

我們發(fā)現(xiàn)直接模擬是可行的, 因?yàn)?n 的數(shù)量級(jí)才 10 ^ 6, 我們枚舉每一個(gè)數(shù)并求出它的數(shù)位和進(jìn)行排序, 時(shí)間復(fù)雜度為 O(nlgn):

注意題目中的 "當(dāng)數(shù)位之和相等時(shí)，將數(shù)值小的排在前面", 看漏眼不小心 WA 了一發(fā)。。。

?

F: 選數(shù)異或(數(shù)學(xué) + 動(dòng)態(tài)規(guī)劃)

給定一個(gè)長(zhǎng)度為 n 的數(shù)列 A1, A2, · · · , An 和一個(gè)非負(fù)整數(shù) x，給定 m 次查

詢, 每次詢問(wèn)能否從某個(gè)區(qū)間 [l,r] 中選擇兩個(gè)數(shù)使得他們的異或等于 x 。

輸入的第一行包含三個(gè)整數(shù) n, m, x 。

第二行包含 n 個(gè)整數(shù) A1, A2, · · · , An 。

接下來(lái) m 行，每行包含兩個(gè)整數(shù) li,ri 表示詢問(wèn)區(qū)間 [li,ri] 。

對(duì)于每個(gè)詢問(wèn), 如果該區(qū)間內(nèi)存在兩個(gè)數(shù)的異或?yàn)?x 則輸出 yes, 否則輸出

no。

4 4 1

1 2 3 4

1 4

1 2

2 3

3 3

【樣例輸出】

yes

no

yes

no

對(duì)于 20% 的評(píng)測(cè)用例，n, m ≤ 500, 1 ≤ a1, a2, · · · , an ≤ 1000；

對(duì)于 40% 的評(píng)測(cè)用例，n, m ≤ 5000；

對(duì)于所有評(píng)測(cè)用例，1 ≤ n, m ≤ 100000, 1 ≤ a1, a2, · · · , an ≤ 100000, 1 ≤ li ≤ ri ≤ n, 1 ≤ ki ≤ n。

由于題目中的n, m數(shù)量級(jí)很高, 直接暴力會(huì)很容易超時(shí), 假設(shè)我們?cè)谝淮尾樵冎性趨^(qū)間[li, ri]找到了兩個(gè)數(shù)使得異或?yàn)?x, 那么對(duì)任意包含于[li, ri]的區(qū)間, 我們的答案都為yes.

我們的目標(biāo)是找到兩個(gè)數(shù) a, b使得 a ^ b = x, 對(duì)于 a, b 我們唯一知道的是它在[li, ri]中, 但是只知道這一點(diǎn)是不夠的, 我們繼續(xù)來(lái)看看a,b和x 滿足什么性質(zhì):

a ^ b = x

a ^ b ^ a?= x ^ a

b ^ 0 = x ^ a

b = x ^ a

于是我們發(fā)現(xiàn) a, b 在區(qū)間[li, ri]中,并且 b = x ^ a 也會(huì)在 區(qū)間 [li, ri]中, 于是我們可以使用map來(lái)記錄 a 和 b 的位置.

于是我們定義一個(gè) dp[i]: 在[0, i]區(qū)間中最大a的位置，并且我們確保了a,b中的a一定是前面那個(gè)元素(因?yàn)槭钦?for 循環(huán)), 于是查詢的時(shí)候我們只需要判斷dp[r] 是否大于等于 l 就知道這個(gè)區(qū)間是否合法了。

G: 消除游戲(暴力)

在一個(gè)字符串 S 中，如果 S i = S ii 1 且 S i , S i+1 ，則稱 S i 和 S i+1 為邊緣

字符。如果 S i , S ii 1 且 S i = S i+1，則 S ii 1 和 S i 也稱為邊緣字符。其它的字符

都不是邊緣字符。

對(duì)于一個(gè)給定的串 S，一次操作可以一次性刪除該串中的所有邊緣字符

（操作后可能產(chǎn)生新的邊緣字符）。

請(qǐng)問(wèn)經(jīng)過(guò) 2

64 次操作后，字符串 S 變成了怎樣的字符串，如果結(jié)果為空則

輸出 EMPTY。

【輸入格式】

輸入一行包含一個(gè)字符串 S 。

【輸出格式】

輸出一行包含一個(gè)字符串表示答案，如果結(jié)果為空則輸出 EMPTY。

【樣例輸入 1】

edda

【樣例輸出 1】

EMPTY

H: 重新排序(差分 + 前綴和 + 貪心)

給定一個(gè)數(shù)組 A 和一些查詢 Li, Ri，求數(shù)組中第 Li 至第 Ri 個(gè)元素之和。

小藍(lán)覺(jué)得這個(gè)問(wèn)題很無(wú)聊，于是他想重新排列一下數(shù)組，使得最終每個(gè)查

詢結(jié)果的和盡可能地大。小藍(lán)想知道相比原數(shù)組，所有查詢結(jié)果的總和最多可

以增加多少?

【輸入格式】

輸入第一行包含一個(gè)整數(shù) n。

第二行包含 n 個(gè)整數(shù) A1, A2, · · · , An，相鄰兩個(gè)整數(shù)之間用一個(gè)空格分隔。

第三行包含一個(gè)整數(shù) m 表示查詢的數(shù)目。

接下來(lái) m 行，每行包含兩個(gè)整數(shù) Li、Ri ，相鄰兩個(gè)整數(shù)之間用一個(gè)空格分

隔。

【輸出格式】

輸出一行包含一個(gè)整數(shù)表示答案。

【樣例輸入】

5

1 2 3 4 5

2

1 3

2 5

【樣例輸出】

4

【樣例說(shuō)明】

原來(lái)的和為 6 + 14 = 20，重新排列為 (1, 4, 5, 2, 3) 后和為 10 + 14 = 24，增

加了 4。

【評(píng)測(cè)用例規(guī)模與約定】

對(duì)于 30% 的評(píng)測(cè)用例，n, m ≤ 50 ；

對(duì)于 50% 的評(píng)測(cè)用例，n, m ≤ 500 ；

對(duì)于 70% 的評(píng)測(cè)用例，n, m ≤ 5000 ；

對(duì)于所有評(píng)測(cè)用例，1 ≤ n, m ≤ 105，1 ≤ Ai ≤ 106，1 ≤ Li ≤ Ri ≤ 106 。

為了使得總和盡可能的大, 我們需要使得變化后的數(shù)組在頻繁查詢的區(qū)間盡可能大。

我們先統(tǒng)計(jì)數(shù)組中每個(gè)區(qū)間被查詢到的次數(shù),?再對(duì)數(shù)組進(jìn)行排序, 使得大的數(shù)能夠放到查詢次數(shù)多的區(qū)間中去:

注意我們 num 定義剛開(kāi)始是一個(gè)差分形式[0 ,..., 0](因?yàn)槊總€(gè)元素被查詢到的次數(shù)都是 0, 0 - 0 = 0), 于是當(dāng)查詢到 [l, r], 其中涉及到到每一個(gè)位置+1, 我們的差分式就有: num[l]++, num[r + 1]--, 最后我們對(duì) num 進(jìn)行求和就得到每個(gè)位置被查詢到的次數(shù)(有點(diǎn)像積分哈哈哈)。