信息學(xué)-zwt雜題選講

熱身題：cf286C

Main

Sequence定義幸運(yùn)數(shù)列：空數(shù)列是幸運(yùn)數(shù)列如果S是幸運(yùn)數(shù)列，那么{r,S,-r}也是幸運(yùn)數(shù)列(r>0)如1果S和2T都-是2幸運(yùn)-數(shù)1列，1那么-{S1,T}也1是幸-運(yùn)1數(shù)列

給定一個(gè)幸運(yùn)數(shù)列中每個(gè)數(shù)的絕對值，并且要求其中的一些數(shù)是負(fù)數(shù)(其他的可正可負(fù))問是否有合法方案，如果有，給出任意

案N<=1000000稍加嘗試后發(fā)現(xiàn)，這道題實(shí)質(zhì)上就是給兩個(gè)相同的數(shù)配對，且兩對數(shù)不允許交叉1

2

-2

–1既然不允許交叉，那

最直觀的想法就是讓每個(gè)數(shù)和離它最近的數(shù)配對。1

1

2

1

1

2貪心圖中紅色的1必然要與綠色的1配對(最近)，而不會(huì)和紫色的1配對。(若紅色的1跟最前面那個(gè)紫色的1配對，那么綠色的1得跟后面那個(gè)紫色的1配對，但是如果紅色1能跟綠色1配對的話，必然前面兩個(gè)紫色1也能配對，沒必要去繞前面的遠(yuǎn)路)從后向前，將所有元素壓到一個(gè)棧中。如果棧頂?shù)膬蓚€(gè)元素可以配對(要注意如果棧頂?shù)脑乇仨毷秦?fù)數(shù)的話也是不能配對的)那么就配對。如果最后棧為空，那么就有解，否則無解。2021/11/6BZOJ

2889

Tree

Conundrum2021/11/6給定一棵N個(gè)節(jié)點(diǎn)的無根樹，現(xiàn)在要求有

多少種分塊方案，將樹分為若干個(gè)連通塊，滿足每個(gè)連通塊內(nèi)點(diǎn)數(shù)相同。N<=1000000顯然，每塊的大小K一定是N的約數(shù)1.枚舉每塊大小K2.判斷是否可行有兩個(gè)顯然但是比較難想到的性質(zhì)：1.如果某個(gè)子樹的大小不是K的倍數(shù)，那么

這個(gè)子樹的根一定和其父親在 通塊內(nèi)。證明：否則這個(gè)子樹就要被分成若干個(gè)大小為K的塊，但是其大小又不是K的倍數(shù)，必定不可能。2021/11/62.如果某個(gè)子樹的大小是K的倍數(shù)，那么這個(gè)子樹的根一定不和其父親在 通塊內(nèi)。證明：否則這個(gè)子樹中其它的點(diǎn)都要自己解決，那么這棵子樹中和根在 通塊的點(diǎn)一定也是K的倍數(shù)，進(jìn)一步地，一定恰好是K。但是這么一來，根就不可能再往上多連了。最終結(jié)論：如果恰好有N/K個(gè)子樹的大小是K的倍數(shù)，則K是一個(gè)可行的方案。于是預(yù)處理出所有子樹大小后枚舉K，然后每個(gè)K

統(tǒng)計(jì)各個(gè)倍數(shù)出現(xiàn)了幾次即可。2021/11/6CODEFORCES

212BPolycarpus

is

Looking

f

ood

Substrings現(xiàn)在有一個(gè)的字符串，都是有小寫字母構(gòu)成。再給你很多個(gè)集合。對于每個(gè)集合，求以下子串s[a,b]的數(shù)量：子串中出現(xiàn)的字母必須出現(xiàn)在集合中。集合中的字母必須在子串中找得到不存在比這個(gè)子串更長的子串s[x,y],使得s[x,y]滿足1,2，且x<=a<=b<=y,y-x+1>b-a+1字符串長度<=10^6，詢問<=10^4狀態(tài)壓縮？將26個(gè)字母狀態(tài)壓縮，用0~2^26-1表示字母集合。盡管這樣將用去很大的內(nèi)存，但不妨先這么表示。對于一個(gè)字母集合，如果能知道以某個(gè)位置結(jié)尾的符合要求的子串?dāng)?shù)量，那么各個(gè)位置加起來也就知道答案了。令f[i][sta]表示對于sta字母集合，以位置i結(jié)尾的子串?dāng)?shù)量。(僅為了表述方便)仔細(xì)思考，對于一個(gè)i，其實(shí)有很多sta形成的f[i][sta]的值是0，另一些值是1，而關(guān)鍵是知道那些是1的sta2021/11/6引入一個(gè)數(shù)組last[‘a(chǎn)’~’z’]記錄到當(dāng)前位置i最后一個(gè)出現(xiàn)的’a’~’z’所在位置這個(gè)數(shù)組很有用！例如，當(dāng)前i=8,last[a]=8,last[z]=6，由于最后出現(xiàn)的z在a的前面，f[8]['z']的值只能是0（以i結(jié)尾向前延伸，要出現(xiàn)一個(gè)

z必定經(jīng)過一個(gè)a）而f[8]['a','z']則有可能不是0的為什么說是“有可能的”呢？因?yàn)榕e的例子里還不知道有沒有一個(gè)last[*]=7的，有的話就不可能了。2021/11/6到這里，大家都有點(diǎn)思路了吧。將last[]數(shù)組排序，按靠當(dāng)前位置i最近的到最遠(yuǎn)的順序?qū)⒆帜敢来渭尤爰稀＜尤胍淮?，?dāng)前形成的集合的答案+1加到什么時(shí)候呢？加到碰到的那個(gè)字母和s[i+1]是同個(gè)字母時(shí)停止因?yàn)轱@然，后面所枚舉到的情況，給它拼上s[i+1]所形成的子串更優(yōu)，并不以i結(jié)尾。2021/11/6算法完成。但內(nèi)存真的夠用嗎？看神奇的代碼：charjw[1<<26];unsigned

short

ans[1<<26];......for(inti=0;i<n;i++){......for(int

j=0;j<26&&ex[no[j]]&&no[j]!=q;j++){sta|=1<<no[j];ans[sta]++;if(ans[sta]==60000){jw[sta]++;ans[sta]=0;}}}這么實(shí)現(xiàn)實(shí)在喪心病狂，建議大家把輸入的詢問hash一下或者用二分查詢來更新答案。2021/11/6給定一個(gè)長度為n的字符串S和k個(gè)詢問，每次詢問一個(gè)最長的字符串a(chǎn)，使得a在S中出現(xiàn)的次數(shù)大于等于x。n<=3000000,k<=50000字符串工廠3設(shè)f(x)=長度大于等于x的串在S中出現(xiàn)的最大次數(shù)。如果

求出了所有的f(x)，那么接下來二分就可以解決這個(gè)問題了怎么求f(x)呢后綴數(shù)組！求出height數(shù)組。初始時(shí)N個(gè)后綴為N段，通過合并這些段來計(jì)算f(x)。從大到小枚舉x，將height[]值大于等于當(dāng)前枚舉的x的相鄰兩個(gè)后綴段合并。合并后當(dāng)前最長的一段后綴段的長度作為f(x)的答案?？梢杂貌⒉榧瘉韺?shí)現(xiàn)由于出題人沒節(jié)操，n<=3000000，所以需要DC3算法BZOJ2870最長道路給定一棵N個(gè)點(diǎn)的樹，求樹上一條鏈?zhǔn)沟面湹拈L度乘鏈上所有點(diǎn)中的最小權(quán)值所得的積最大。其中鏈長度定義為鏈上點(diǎn)的個(gè)數(shù)。N<=50000樹的分治（點(diǎn)分）不知道樹的分治的同學(xué)請課后自行學(xué)習(xí)。。選定重心之后的處理：bfs至樹上每個(gè)點(diǎn)，計(jì)算出從重心到這個(gè)點(diǎn)的路徑中的最小權(quán)值記為v[i]算法思想是設(shè)一個(gè)空的集合，按v[i]從大到小排序，依次加入點(diǎn)，加入時(shí)用與原先集合中的點(diǎn)形成的路徑來更新答案。(上面說的路徑必須指重心的路徑，即要求兩點(diǎn)不在以重心為根的同一子樹中)2021/11/6完全記錄這個(gè)集合太費(fèi)時(shí)間，不可行?？梢园l(fā)現(xiàn)這樣做的話，后加的點(diǎn)與已經(jīng)加的點(diǎn)形成的路徑上的最小值，一定是后加點(diǎn)的v[]。當(dāng)前加的點(diǎn)的深度是確定的，路徑長度只跟集合里另一個(gè)點(diǎn)有關(guān)。要讓路徑盡量長，也就是說只需要另一個(gè)點(diǎn)深度最深，那么的集合簡化成了記一個(gè)最深的點(diǎn)。那如果當(dāng)前加的點(diǎn)和記錄的點(diǎn)在同一子樹里？看來記一個(gè)點(diǎn)還不夠，需要記兩個(gè)不在同一子樹的最深的點(diǎn)。2021/11/6Catch

The

Penguins數(shù)點(diǎn)。給定 空間內(nèi)n個(gè)點(diǎn)的坐標(biāo)，有m個(gè)詢問坐標(biāo)都比這每次給出一個(gè)點(diǎn)，詢問所有個(gè)點(diǎn)小的點(diǎn)有多少個(gè)。

n,m<=30000兩重循環(huán)時(shí)間復(fù)雜度O(n^2)先離散化離線回答詢問。分別將詢問和企鵝按照第一維坐標(biāo)排序，然后按排好的順序一個(gè)一個(gè)處理詢問。對于每一個(gè)詢問，加入所有第一 它小的企鵝并按照第二維排序，為了保證復(fù)雜度，

sqrt(n)個(gè)企鵝，就

進(jìn)行一次排序，當(dāng)沒有到sqrt(n)時(shí)，不到sqrt(n)的那部分就不進(jìn)行排序而 詢問（這部分總復(fù)雜度O(nsqrt(n))）。當(dāng)進(jìn)行一次 排序時(shí)，設(shè)已經(jīng)加入排序的企鵝的個(gè)數(shù)為M， 再把它們分成sqrt(M)塊，每塊里面按照第三維坐標(biāo)排序，排好序后把序列按第 前綴的權(quán)值線段樹（用函數(shù)式線段樹）。進(jìn)行詢問。對于“整塊的第二維坐標(biāo)”都比“當(dāng)前詢問第二維坐標(biāo)”小的那些塊，在塊中二分出詢問第三維坐標(biāo)所對應(yīng)的位置，再在那棵函數(shù)式線段樹上詢問第比它小的企鵝的個(gè)數(shù)。對于不是“整塊的第二維坐標(biāo)”都比“當(dāng)前詢問第二維坐標(biāo)”小的那些塊， 仍然只需要詢問即可。總復(fù)雜度O(nsqrt(n)log(n))復(fù)雜度更優(yōu)秀的算法同樣的，還是離散化。還是離線回答詢問。先將詢問和企鵝全都放在一起，按第一維坐標(biāo)排序，那么只有前面的企鵝可能為在它之后的詢問增加答案。從第一維排好序的順序開始，再按照第二維坐標(biāo)進(jìn)行類似歸并排序的分治算法：1.假設(shè)排好序后的序列為id[L]~id[R]，令MID為其中點(diǎn)。2.遞歸處理L~MID，MID+1~R部分的答案。3.發(fā)現(xiàn)還沒有處理的情況就只有左半部分的企鵝對右半部分的詢問的影響，這時(shí)左右兩部分都已經(jīng)按第二維坐標(biāo)排好序（為什么已經(jīng)排好序見后），而它們按第一維排的順序已經(jīng)不需要了，我們把左右部分按第二維坐標(biāo)進(jìn)行歸并（有序線性表合并），合并成新的表時(shí)，如果添加的是左邊的企鵝，就把它三四兩維形成的點(diǎn)一個(gè)“集合”，如果添加的是右邊的詢問，就在“集合”里詢問有多少點(diǎn)在以它三四兩維形成的點(diǎn)的左下方，把答案累加到這個(gè)詢問里。至于這個(gè)“集合”的實(shí)現(xiàn)，

可以用樹狀數(shù)組（或線段樹）套平衡樹?？倳r(shí)間復(fù)雜度O(nlog^3(n))AC算法將詢問和企鵝一起按第一維坐標(biāo)排序。分治：按照第二維坐標(biāo)進(jìn)行“歸并”。11/6/20213

,

1

2

,

34

,4 3

,34

,53

,3由經(jīng)于過開初分始始治按按，第第二一二維維“排坐歸序標(biāo)并，有”所序以左側(cè)第一維坐標(biāo)<=右側(cè)6

,61,4

2

,

6

4

,2

3

,

5

3

,

75

,5 2

,311/6/20214

,53

,

1

2

,

3

1,4

2

,

64

,4 3

,3

3

,3

5

,5開始按第二維“歸并”4

,

2

3

,

5

3

,

72

,

35,54,43,3