Codeforces - tag::data structures 大合集 [占坑 25 / 0x3f3f3f3f]
371D
小盤子不斷嵌套與大盤子,最后與地面相連,往里面灌水,溢出部分會(huì)往下面流,求每次操作時(shí)當(dāng)前的盤子的容量
其實(shí)這道題是期末考前就做好了的..
鏈?zhǔn)浇Y(jié)構(gòu)考慮并查集,然后沒(méi)了(求大佬解釋第一個(gè)T的點(diǎn))
https://paste.ubuntu.com/p/tFycq2zYqz/
242E
線段樹操作,1.求\([l,r]\)的和,2.更新\(a[l,r]\)為\(a[l,r]⊕x\)
對(duì)于操作2,把線段樹拆位后就變?yōu)?1翻轉(zhuǎn)操作了
https://paste.ubuntu.com/p/9J73wp4V7V/
1000C
求被1...n次線段覆蓋的各端點(diǎn)個(gè)數(shù)
口胡一下,離散化亂搞
858D
給出n個(gè)定長(zhǎng)10的字符串,求每一個(gè)字符串的最短可區(qū)分子串
把所有的后綴掛到字典樹上,然后n次從小到大暴力枚舉子串,若字典樹中刪去相應(yīng)的單個(gè)子串后不存在或等于自身剩余的相同子串個(gè)數(shù),則表明該子串為可識(shí)別最短子串
另外解法的細(xì)節(jié)上的不同是不統(tǒng)計(jì)自身相同子串,而是維護(hù)前綴串來(lái)自于哪個(gè)原串,似乎做法這種更優(yōu)
//此處應(yīng)有代碼
808D(水)
給定數(shù)列\(a[1...n]\),最多可移動(dòng)一個(gè)元素到任意地方,問(wèn)是否可以把數(shù)列分割成連續(xù)的兩塊
如果某一塊比另一塊的總和大\(t\),那就看大的那塊有沒(méi)有\(t/2\)大小的可移動(dòng)到另一邊,哈希表O(n)完成
https://paste.ubuntu.com/p/BZCKYHvJgq/
629D
LIS那啥,我討厭這題,不做了
342E
給定一棵n節(jié)點(diǎn)的樹，除了1節(jié)點(diǎn)為X外其他全為O
有m個(gè)操作，操作1為置某節(jié)點(diǎn)為X，操作2為詢問(wèn)某節(jié)點(diǎn)與最近的X節(jié)點(diǎn)的距離
qls曾說(shuō)過(guò)是樹剖套路題，題解給了一種很好用的分塊暴力方法
對(duì)詢問(wèn)分塊處理，把每\(\sqrt m\)個(gè)置X節(jié)點(diǎn)存入塊中
每當(dāng)塊滿了就進(jìn)行一次\(O(n)\)的bfs更新所有節(jié)點(diǎn)的最近距離，然后清空，復(fù)雜度\(O(n \sqrt m)\)
否則先取先前一直做好的bfs的最近距離，然后與塊內(nèi)的置X節(jié)點(diǎn)進(jìn)行暴力LCA詢問(wèn)取最小距離，復(fù)雜度\(O(m \sqrt m)\)
這里忽略詢問(wèn)節(jié)點(diǎn)部分的分塊會(huì)使效率高不少
https://paste.ubuntu.com/p/znTK2GzGD3/
670E
給出括號(hào)匹配串，求m次操作后（移動(dòng)和刪除，注意刪除時(shí)是匹配的一連串刪除）的匹配串
用棧預(yù)處理出所有左右括號(hào)匹配的下標(biāo)，刪除時(shí)用并查集相連兩端表示一連串刪除，移動(dòng)時(shí)檢查當(dāng)前下標(biāo)并查集是否為空或有刪除標(biāo)記，有就大幅度滑動(dòng)，O(n)精神AC
519E
多次詢問(wèn)一棵樹中到達(dá)某兩點(diǎn)u,v距離相等的點(diǎn)的個(gè)數(shù)
這次做的太糾結(jié)了,情況比較麻煩
考慮u,v路徑的長(zhǎng)度,若為奇數(shù),則不存在路徑中點(diǎn),輸出0,
否則就是中點(diǎn)分支上所有點(diǎn)的個(gè)數(shù),除去到達(dá)u方向的分支和v方向的分支,此時(shí)用size來(lái)表示就是中點(diǎn)的size減去深度較深的點(diǎn)距中點(diǎn)低一層的祖先的size,即使單鏈也是如此
需要注意的是若中點(diǎn)為L(zhǎng)CA要單獨(dú)考慮(注意size域的方向),答案為所有的點(diǎn)減去uv兩邊距l(xiāng)ca低一層的size
https://paste.ubuntu.com/p/8wMcF8ykwk/
474F
數(shù)論不行,只想到了GCD但沒(méi)有聯(lián)系到區(qū)間的最小值
https://blog.csdn.net/S_Black/article/details/47189051
實(shí)現(xiàn)比較簡(jiǎn)單就不搞了
914D
給定\(a[1...n]\),兩種操作,操作2單點(diǎn)更新,操作1詢問(wèn)區(qū)間gcd能否等于x,詢問(wèn)過(guò)程中可允許暫時(shí)修改最多1個(gè)數(shù)
分析一下,如果某個(gè)數(shù)不為x的倍數(shù),那么它與任何數(shù)gcd都不可能為x,必須要改
如果某個(gè)數(shù)為x的倍數(shù),那么它可能不改,而由另外一部分限制它因子指數(shù)的上限也可以做到gcd為x
因此,在線段樹中查詢區(qū)間gcd且統(tǒng)計(jì)底層不為x倍數(shù)的個(gè)數(shù)
若個(gè)數(shù)為0,則證明gcd恰好為x的倍數(shù),雖然不能直接表明相等,但任意修改其中一個(gè)數(shù)為x那么gcd就為x
若個(gè)數(shù)為1,我們只能在不為x的倍數(shù)的值上修改
其他情況均為非法
https://paste.ubuntu.com/p/MP829x39Yf/
685B
求所有子樹的重心
性質(zhì):把兩個(gè)樹通過(guò)一條邊相連得到一個(gè)新的樹，那么新的樹的重心在連接原來(lái)兩個(gè)樹的重心的路徑上。
遞歸處理
一個(gè)點(diǎn)的樹的重心是他自己。
如果一棵樹的根的所有子樹大小都不超過(guò)整個(gè)樹大小的一半，那么樹根是重心。
否則找到子樹大小超過(guò)整個(gè)樹大小的一半的子樹（只會(huì)有一個(gè)），假定當(dāng)前樹的重心為子樹的重心，用調(diào)整的方式得到當(dāng)前樹的重心。
280B
求\(a[1...n]\)的所有區(qū)間的最大值與次大值的最大異或值
這種一般都用到單調(diào)棧,只是寫的過(guò)程極為混亂ORZ
只要定擴(kuò)展區(qū)間的中心為次大值那就寫起來(lái)很輕松了,只需向前向后分別各擴(kuò)展一次
我怎么就想到定最大值找次大值從左邊枚舉右邊RMQ+二分BLABLA找了呢..
https://paste.ubuntu.com/p/BgHq2bhbkt/
731F
給定\(a[1...n]\),允許選定一個(gè)數(shù)字,使小于它的數(shù)為0,大于它的數(shù)變?yōu)椴怀^(guò)自身大小的它的倍數(shù),然后累和,求該操作下累和的最大值
用哈希表存儲(chǔ)并統(tǒng)計(jì)前綴個(gè)數(shù)和,類似素?cái)?shù)篩地枚舉倍數(shù),分段累和
或者排序然后每次lowerbound查找
https://paste.ubuntu.com/p/h8KkDNshwG/
903D
變種前綴和,求數(shù)列\(a[1...n]\)所有區(qū)間的差,若兩數(shù)相差小于等于1則不計(jì)算
算好前綴后再補(bǔ)回不計(jì)算的部分就行了,小的減掉,大的加回來(lái)
令人惡心的是會(huì)爆ll,因此用long double
https://paste.ubuntu.com/p/WGX8brYW74/
367B(水)
給定數(shù)列\(a[1...n]\)和\(b[1...m]\)和\(p\),找出符合每項(xiàng)相差p的a子數(shù)列使與b匹配
枚舉所有等差長(zhǎng)度的數(shù)列O(n),是否相等直接用map對(duì)比(還挺好用的)
(這題居然能放div1)
https://paste.ubuntu.com/p/xWszDDTgRn/
292E
給定數(shù)組\(a[1...n]\)和\(b[1...n]\),
操作1使\(a[L...R]\)快速?gòu)?fù)制到\(b[k...k+R-L]\),保證操作不越界
操作2查詢\(b[k]\)的值
感覺(jué)蠻有創(chuàng)意的一道題,我一開始想到用并查集維護(hù)區(qū)間信息了(按道理應(yīng)該可行吧)
另一種思路是用線段樹區(qū)間覆蓋,值僅與詢問(wèn)前最后一次覆蓋到它的更新油管
把\(b\)建成線段樹,只需知道當(dāng)前節(jié)點(diǎn)的開端和復(fù)制\(a\)的開端以及自身節(jié)點(diǎn)所在的對(duì)應(yīng)數(shù)組下標(biāo)就能推出\(b\)目前的任一點(diǎn)信息
注意沒(méi)有更新的特判
具體看代碼
https://paste.ubuntu.com/p/kpNS9cPXn5/
766D
推斷同義詞和反義詞
挑戰(zhàn)程序設(shè)計(jì)競(jìng)賽同款題目,略
920F
給定數(shù)組\(a[1...n]\),操作1使\(a[L...R]\)變?yōu)楦髯詳?shù)值對(duì)應(yīng)的因子數(shù)\(D[a[i]]\),操作2求和
由于因子數(shù)能在\(O(logn)\)時(shí)間內(nèi)降至平凡個(gè)數(shù)1或者2,直接樹上暴力\(O(nlognlogn)\)
https://paste.ubuntu.com/p/4fMC7HKdfd/
961E
給定\(a[1...n]\),求有多少對(duì)\((i,j)\)滿足\(i<j \ \& \ a[i]≥j \ \& \ a[j]≥i\)
沒(méi)有第三個(gè)條件那是相當(dāng)好辦,多了那條件就變得極其地繞(我是這么覺(jué)得)
首先,要方便地求大小關(guān)系和數(shù)量關(guān)系,樹狀數(shù)組是必須的,注意到大于n的都沒(méi)用那么把每個(gè)元素比較一下取min
求解的方法可以這樣枚舉:\(i\)是一個(gè)一個(gè)插入的,那么對(duì)于\(j,j>i\)而言,求有多少個(gè)\(a[1...i_{max,max≤i}]≥j\)的元素
所以我們要維護(hù)一個(gè)對(duì)于每一個(gè)j能遍歷到的最遠(yuǎn)的i,以滿足\(i≤a[j]\),但因?yàn)槊杜e過(guò)程是i開始的,那么倒過(guò)來(lái)維護(hù)\(vec[maxto:i]={j_1,j_2...}\)
https://paste.ubuntu.com/p/Kr2gV27DHC/
375D
給出一棵有顏色的樹,多次詢問(wèn)某子樹下相同顏色節(jié)點(diǎn)大于某個(gè)值的顏色個(gè)數(shù)
第一反應(yīng):樹分塊啊
第二反應(yīng):不大會(huì)寫hhh
由于是子樹問(wèn)題,那么可以通過(guò)啟發(fā)式合并離線處理或者dfs序+線段樹暴力(不大靠譜)解決
先掛著
920E / 190E
給你一個(gè)\(n\)個(gè)點(diǎn)\(m\)條邊的無(wú)向圖,求其補(bǔ)圖的連通塊個(gè)數(shù)及各個(gè)連通塊大小
暴力遍歷
707D
主席樹模板/可持久化KD樹(當(dāng)我沒(méi)說(shuō))
Gym - 101142G
題意:給你一棵樹,邊為水流過(guò)的路徑,葉子為房子其余為閘開關(guān),有一些搶匪會(huì)占領(lǐng)屋子或者撤離屋子,你需要求出每一步最少關(guān)閉的水流路徑,其次要求最少誤殺的房屋
正解是直接用DFS序來(lái)求,但我嘗試了自己的二分線段樹方法
首先是要解決的是如何表示水流路徑/開關(guān)/屋子與誤殺的問(wèn)題
對(duì)原樹求出葉子的標(biāo)記,開了一棵用于標(biāo)記是否為葉子的線段樹ori,那么誤殺的房屋=ori線段樹上的區(qū)間求和-占領(lǐng)線段樹1的區(qū)間求和(由于沒(méi)用到快速?gòu)?fù)原的操作所以線段樹2等價(jià)于ori)
我們還多開一棵用于標(biāo)記總開關(guān)的線段樹0,若某節(jié)點(diǎn)為1則表示該節(jié)點(diǎn)上方的流水被截?cái)?/p>
觀察容易得出每一步操作最多只影響到自身除1以外的最遠(yuǎn)祖先,這時(shí)候RMQ就派上用場(chǎng)了,但需要改動(dòng)1以下的兒子的父親為自己,這樣會(huì)方便二分
為什么要二分,很顯然占領(lǐng)數(shù)從葉子到頂上是一個(gè)單調(diào)遞增的過(guò)程,我們只需找到一個(gè)占領(lǐng)最多的lowerbound就可以斷定某一點(diǎn)要斷水流
注意求之前要吧最大子樹的影響清零,如最小誤傷人數(shù)要先減除先前誤殺的人數(shù),然后再重新統(tǒng)計(jì)誤傷人數(shù)
大概思路是這樣,實(shí)現(xiàn)過(guò)程中注意到了如果刪除某節(jié)點(diǎn)后只有另一邊有一個(gè)占領(lǐng)點(diǎn),那詢問(wèn)的節(jié)點(diǎn)的原路徑會(huì)錯(cuò)誤地二分到它的父親,這時(shí)要特殊標(biāo)記一下直接斷定最佳截?cái)帱c(diǎn)
目前ans1是正解,不知道ans2錯(cuò)在哪里了..明天醒來(lái)再看吧
https://paste.ubuntu.com/p/4nccbsYyrC/
UPD:我不改了,用正解方法秒A
https://paste.ubuntu.com/p/KvkhyYNqkx/
558E
給你一個(gè)僅26字母的串,q次操作,k=1時(shí)使[L,R]升序,k=0時(shí)降序,求最終的串
使用計(jì)數(shù)排序和26個(gè)線段樹即可
609E
給出一個(gè)圖,多次詢問(wèn)求強(qiáng)制包含(u,v)邊的最小生成樹的權(quán)重
先求出MST,若強(qiáng)制包含的邊為MST里的邊那就不作處理,否則必然形成一個(gè)包含u,v的環(huán),此時(shí)的最小生成樹不同在于必須要?jiǎng)h除環(huán)中的最大權(quán)邊(環(huán)外顯然不受影響)
求的方法常見的對(duì)鏈操作有樹鏈剖分,另一種較為巧妙的是倍增法,一邊求祖先一邊更新MST路徑的最大權(quán)邊值
//此處應(yīng)有代碼
689D
已知區(qū)間\(a[1...n]\)和\(b[1...n]\),求多少個(gè)區(qū)間滿足\(max(a[L...R])=min(b[L...R])\)
顯然區(qū)間有單調(diào)性,枚舉左端點(diǎn),二分右端點(diǎn),兩次二分找出最近和最遠(yuǎn)的右端點(diǎn),O(1)或O(logn)計(jì)算貢獻(xiàn)即可
587C
一棵樹中的節(jié)點(diǎn)帶有權(quán)值集合(多個(gè)權(quán)值),多次詢問(wèn)求路徑\((u,v)\)的第\(k\)小(\(k<10\),每次均可不同)的權(quán)值是多少
k很小,那么每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)大小為10的大根堆,樹剖暴力合并,常數(shù)應(yīng)該不爆炸吧?(似乎st表維護(hù)堆也行)
明天上代碼
475D
877F
待做(不想做/做不動(dòng)):644B/359D/755D/830B/487B/777E/724D/514D/637D/721D/534D/754D/893D
834D(unordered)
題意:給出\(a[1...n]\),問(wèn)劃分成k個(gè)連續(xù)序列的最大代價(jià)，其中每一個(gè)序列的代價(jià)為序列中不同的數(shù)字種類
列出樸素的DP方程\(f[i][j]\):把前\(i\)個(gè)數(shù)字劃分成\(j\)短的最大代價(jià),轉(zhuǎn)移\(f[i][j]=max(f[k][j-1]+s[k+1][i])\),其中\(s[i][j]\)表示\(i\)到\(j\)的個(gè)數(shù)種類
有一種動(dòng)態(tài)維護(hù)種類的方法是記錄每個(gè)數(shù)上一次出現(xiàn)的位置\(last[a[i]]\),每次枚舉到\(i\)時(shí)更新\(s[last_{a_i}+1,i]\)加一,那么\(s[j]\)就代表當(dāng)前\(j\)到\(i\)的種類個(gè)數(shù)(感覺(jué)好神奇
基于這種策略改寫方程:\(f[j][i]=max(f[j-1][k]+s[k+1])\)
第二維可用滾動(dòng)的線段樹來(lái)維護(hù),s直接錯(cuò)位累加到上一維的\(f[j-1]\)中(直接加一就好)
https://paste.ubuntu.com/p/vJVNK6kMPN/
913D(unordered)
題意:給出n個(gè)任務(wù)和總時(shí)間T,每個(gè)任務(wù)占時(shí)間c_i和要求最后完成的不得超過(guò)t_i個(gè)任務(wù)(包括)才能得1分,求最高得分和方案
倒序枚舉得分k,當(dāng)t_i≥k時(shí)才是有效得分,用平衡樹動(dòng)態(tài)維護(hù)前k大的和,具體看代碼
https://paste.ubuntu.com/p/Z3dztvY5Jv/
HDU待做 : 5111/6010/5700
轉(zhuǎn)載于:https://www.cnblogs.com/caturra/p/9260225.html
總結(jié)
以上是生活随笔為你收集整理的Codeforces - tag::data structures 大合集 [占坑 25 / 0x3f3f3f3f]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 客户端检测的含义和方法
- 下一篇： C# 执行查询语句，返回DataSet