week隊(duì)互測(cè)Week1解題報(bào)告

省隊(duì)互Week1解題報(bào)VFleaKing&hjy96May18,2014題目大意題意已經(jīng)足夠抽象了……{0}∪{(xLxR)}0以外任何數(shù)都由一個(gè)數(shù)對(duì)表示，要你一個(gè)長(zhǎng)度為n的序列，共m個(gè)操作。Clrka[ka[l]a[r])Qlr所有數(shù)據(jù)中賦值操作與詢問(wèn)操作大約各占一半。編nm特殊限1==操作的參數(shù)均為均勻2=≤34=≤≤56=≤無(wú)78=≤910分算法1號(hào)測(cè)試點(diǎn)范圍較小，直接即可。見30分算法1231,2,3號(hào)測(cè)試點(diǎn)為什么要強(qiáng)調(diào)均勻隨機(jī)生成C111這樣如果數(shù)據(jù)足夠刁鉆，直接求解的時(shí)間復(fù)雜度其實(shí)是O(mn2m)。首先我們定義一個(gè)數(shù)的大小為其含有的0的個(gè)數(shù)Sm[imi個(gè)數(shù)的大小，Sˉmm次賦值操作后序列中數(shù)的平均大小，并假設(shè)第m次賦值為Clrk。那么就兩邊同時(shí)取期

Sˉm=(nSˉm?1?Sm?1[k]+Sm?1[l]+(ˉm(nE(m?1由于l,r,k是均勻隨機(jī)，所E(ˉm(nE(m?1(ˉm?1(ˉm?1E(m?1整理一下 1E(Sˉ) 1 E(ˉ Sˉ01ˉ

1

1nE(Sm) 1+ 1+n=50000(ˉm100000m/n2。所以平均大小的期望是e2≈7.3。當(dāng)然我們還沒有分析平均大小的標(biāo)準(zhǔn)差，是不嚴(yán)謹(jǐn)?shù)模ㄊ聦?shí)上這個(gè)問(wèn)題中最大大小才是真正要考慮的，不過(guò)實(shí)際隨機(jī)生成幾組數(shù)據(jù)發(fā)現(xiàn)確實(shí)還挺弱的。那么兩個(gè)數(shù)我們可以比較大小。所以我們只要用線段樹來(lái)這個(gè)序列即可。忽略比較兩個(gè)數(shù)的時(shí)間，則時(shí)間復(fù)雜度為O(mlogn)。50分算法通過(guò)上面的分析發(fā)現(xiàn)，其實(shí)瓶頸在于比較兩個(gè)數(shù)的大小，最起碼如果比較兩個(gè)數(shù)需要指數(shù)級(jí)的時(shí)間那么肯定是沒戲的。如果能O1)比較的話其實(shí)就用很普通的線段樹就行了。然后4,5號(hào)測(cè)試點(diǎn)中：數(shù)組中所有出現(xiàn)過(guò)的數(shù)中不同的數(shù)的個(gè)數(shù)≤1000那么如果我們已經(jīng)有10001000precmp[x][y]記錄了x個(gè)出現(xiàn)的數(shù)和y個(gè)我們仔細(xì)觀察一下比較兩個(gè)數(shù)的過(guò)程，如下面?zhèn)未a所示。按照慣例，numcmp(x,y)的返回值ret<0表示x<y，ret>0表示x>y，ret=0表示x=y。numcmp(xLyL)numcmp(xRyR)O(1)num-cmp(x,y)的值了。functionnumcmp(x,ifx=0andy=0thenreturn0endifx=0thenreturn-endify=0thenreturn1endc=numcmp(xL,ifc=0c=numcmp(xR,endifreturncend并且我們知道，每個(gè)非零數(shù)都是在已有的數(shù)的基礎(chǔ)上發(fā)展出來(lái)的。也就是說(shuō)，在數(shù)組 xxLxRx=(xLxR)xLxR(xLxR)xLxR所以我們把所有不同的數(shù)按出現(xiàn)的先后次序標(biāo)號(hào)，第1個(gè)出現(xiàn)的為1號(hào)，第2個(gè)出現(xiàn)號(hào)……以此類推。1000×1000map<pair<int,int>,(xL編號(hào)xR編號(hào))x每當(dāng)出現(xiàn)一個(gè)數(shù)時(shí)，如果已經(jīng)在map中有記錄，那么直接取用此標(biāo)號(hào)。如果沒有記錄說(shuō)明是一個(gè)新數(shù)，那么新產(chǎn)生一個(gè)標(biāo)號(hào)給它，在map中記錄，并計(jì)算出來(lái)此數(shù)與其它出現(xiàn)過(guò)的數(shù)之設(shè)不同的數(shù)的個(gè)數(shù)為u，還是用線段樹區(qū)間最大值，那么時(shí)間復(fù)雜度就是O(u2當(dāng)然你可以不用map改用一個(gè)二維數(shù)組，這樣的時(shí)間復(fù)雜度就是O(u2+mlogn)70分算法仔細(xì)想想50分算法其實(shí)還是比較值得吐槽的。你看：為了一些數(shù)之間的關(guān)系，我們開了一張那么大的表格出來(lái)。但是實(shí)際上這件事情可以做得更加簡(jiǎn)潔：把這些數(shù)從小到大的排好序的序列。于是我們可以用一棵平衡樹來(lái)這個(gè)序列時(shí)間里實(shí)現(xiàn) 與序列中任意數(shù)的大小比較，這樣就能在平衡樹中找到插入的位置考慮比較x,y，只用比較它們?cè)谛蛄兄械南群箜樞蚣纯?。還可以更加一點(diǎn)：比較它們的。這樣做時(shí)間復(fù)雜度是O(logu)由于比較一次是O(logu)的，所以添加一個(gè)新數(shù)的時(shí)間復(fù)雜度就是O(log2u)，而用線段樹查詢區(qū)間最大值也變?yōu)榱薕(lognlogu)。O(m(log2ulognlogu))。這樣就能通過(guò)前7個(gè)測(cè)試點(diǎn)獲得70分。一個(gè)用treap的實(shí)現(xiàn)版本，見number_treap_log2.cpp如果你是用sy寫的，但是每次獲取的時(shí)候忘記把獲取的結(jié)點(diǎn)sy到根，那100分算法上面的分析中有些思想隱隱約約地透出來(lái)了，其矛頭直接指向了一個(gè)東西：全序集的同構(gòu)。你看，50分算法里面我們定義了一個(gè)“數(shù)”到整數(shù)的映射φ使得x=y)=y。到70分算法里面的時(shí)候，我們加強(qiáng)了，我們定義了一個(gè)“數(shù)”到的映射。但是其實(shí)并不一定非要是，任意滿足下列性質(zhì)的映射即可：“數(shù)”到實(shí)數(shù)的映射φ，使得x≤y??φ(x)≤φ(y)。φ(xO(1)O(1)好，那么我們還是用平衡樹來(lái)把這些數(shù)從小到大的排好序的序列。對(duì)于每個(gè)x，我們還記錄它的φx)。我們需要φx)使其有序。一個(gè)簡(jiǎn)單的想法就是：每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)開區(qū)間(l,r)，根結(jié)點(diǎn)的區(qū)間為(0,1)（這里x(l,r)φ(x)=l+r2其左孩子對(duì)應(yīng)的區(qū)間為(l,l+r)，其右孩子對(duì)應(yīng)的區(qū)間為l+rr) xφ(x)是自己區(qū)間的中點(diǎn)，且其中所有數(shù)的φ都位于這個(gè)區(qū)間。既然x是根，那么左都比x小，分配到區(qū)間(l,φ(x));右都比x大，分配到區(qū)間(φ(x),r)。那么好像就解決了……嗎？計(jì)算機(jī)無(wú)法實(shí)數(shù)，只能精確到有限多位。只要你還是double來(lái)存，那么碰到神數(shù)據(jù)就會(huì)因?yàn)榫炔粔蚨褍蓚€(gè)不等的數(shù)判為相等。nlogn2logn=1。n105O(logn)φ(x的話，n好像這個(gè)問(wèn)題解決了？沒有。一般平衡樹都有個(gè)非常詭異的操作叫做旋轉(zhuǎn)。旋轉(zhuǎn)之后內(nèi)的(x)都必須重新計(jì)算。但是重量平衡樹不存在這個(gè)問(wèn)題，比如替罪羊樹，eap，樹等等。其插入后往上旋轉(zhuǎn)的次數(shù)分別是沒有旋轉(zhuǎn)操作，期望O1)，均攤O(1)。若旋轉(zhuǎn)是順帶重建，那么花在這上面的時(shí)間復(fù)雜度分別是沒有旋轉(zhuǎn)操作，期望Ologn)，均攤Ologn)。（喂喂那個(gè)替罪羊樹沒有旋轉(zhuǎn)操作是在逗我笑嗎……（替罪羊樹維持自己平衡的唯一方式是重建整棵，所以原生態(tài)支持重新計(jì)算φ）關(guān)于重量平衡樹的介紹請(qǐng)見2013年國(guó)家集訓(xùn)隊(duì)《重量平衡樹和后綴平衡樹所以這個(gè)問(wèn)題就解決了。插入O(logu)，單次比較O(1)。總時(shí)間復(fù)雜度O(m(logu+logn))。我當(dāng)然不會(huì)坑自己用double作為φ(x)的類型啦……longlong[1263?1]標(biāo)程是用替罪羊樹寫的，見number.cpp。當(dāng)然你也可以用Treap寫，見number_treap.cpp題目大意[P]P1,0[x=7]{[x=7]

ifx= 給定d,n，其中：求

n fd(n) [(n,k)=對(duì)于所有數(shù)據(jù)，1≤w10002≤pi1091αi109編d特殊限1≤n≤2=無(wú)3=4=5≤w=1,α1=∏67≤ (αi+1)≤8≤w≤9≤無(wú)10分算法對(duì)于1號(hào)測(cè)試點(diǎn)，枚舉k，可以獲得10分20分算法對(duì)于2號(hào)測(cè)試點(diǎn)，其實(shí)就是要求函數(shù)120

(piαi?一些簡(jiǎn)單的推導(dǎo)fd(n)

[(n,k)=1]k=∑d∑k ∑=g|n

[g|設(shè)Sd(n)= kd，則可以得到

∑ g|n fd(n)

ggddg關(guān)于Sd(n)的一些論述請(qǐng)看皓2013年WC營(yíng)員交流《多項(xiàng)式及求和（見 的各種數(shù)學(xué)推導(dǎo)還有數(shù)的話……我們來(lái)點(diǎn)搞笑推導(dǎo)?；豐0(n)=1S1(n)S2(n)

n(n+21n(n+1)(2n+2 2S 1n(n+3()2Sd(nnd1Sd(n)Sd(n) 的形由于d≤100，所以我們可以算出n=0,1,...,d,d+1時(shí)的值然后O3)消元ai用數(shù)求ai的一個(gè)O2)的算法見tester/calc/calc.cpp40分算法5,6Sd(n1)。再結(jié)合測(cè)試點(diǎn)1,2就能獲得40分。50分算法O3)，O(d)dg。通過(guò)枚舉約數(shù)g可以通過(guò)7號(hào)測(cè)試點(diǎn)。順便也干掉了1,5,625060分算法μ(g0，所以可以直接枚舉無(wú)完全平方因子的約數(shù)，這樣只用枚舉2w個(gè)約數(shù)，可以通過(guò)8號(hào)測(cè)試點(diǎn)。見tester/calc/calc_divisor.cpp。順便也干掉了1,5,6,7260進(jìn)一步的推導(dǎo) fd(n) ig∑

∑gdg∑令hi(n) g|nggdgi

gμ(g)gdgiDirichlethihi也nhi，再將其乘起來(lái)hi(n)?？紤]hi(pα)，其中p是素?cái)?shù)，α是正整數(shù)，則hi(pα)

jd μ(1)1d(pα)i+μ(p1)(p1)d(pα?1)i+μ(p2)(p2)d(pα?2)i+...+=(pα)i?=pαi(1?忽略快速冪的時(shí)間，所以我們就能在O(w)的時(shí)間求出hi(n)30分算法報(bào)告，我不會(huì)求ai怎么辦d0d1d2ai是多少吧……用上面的推導(dǎo)，就拿到了30分。80分算法aid=0d=1d=2時(shí)怎么弄，但是不知道怎么推廣到任意d。1234567880100分算法∑ 消元求ai，再

O+??題目大意地鐵2號(hào)線是一條直線，一共m個(gè)地鐵站，依次編號(hào)為1,...,m搭乘地鐵需要刷一種叫通的卡。進(jìn)站時(shí)刷一次，出站時(shí)刷一次，在出站時(shí)會(huì)根據(jù)起始站和終點(diǎn)站之間的距離給通扣費(fèi)。cost(ij)=|i?j|假設(shè)有n個(gè)人來(lái)搭地鐵，分別編號(hào)為1,n，第i人從第si站出發(fā)去第ei站(si?=ei)，沿最短路坐地鐵。那么假設(shè)他們足夠聰明，會(huì)在中途下車換票，那么他們乘車的最小總代價(jià)是多少？具體乘車方式說(shuō)明如isi0xy：讓編號(hào)為x的人乘地鐵到第y1xy：讓編號(hào)為x的人和編號(hào)為y的人交換通。此時(shí)在同一個(gè)地鐵站的兩人才可以所有操作結(jié)束后，所有人一起刷卡出站。要使得所有人出站后，通上扣費(fèi)總和最小。求一個(gè)最小的乘車方案。ss≤400000編nm1==2==3==4≤≤5≤≤6≤≤7≤≤8≤≤9≤≤≤≤10分算法2m2，也就是說(shuō)只有兩種人：1221的，那么數(shù)數(shù)他們的個(gè)數(shù)20分算法如果你是一個(gè)分類討論的狂熱者，那么你一定不會(huì)放過(guò)1 結(jié)合2號(hào)測(cè)試點(diǎn)就能獲得20分。30分算法如果你是一個(gè)搜索的狂熱者，那么你一定不會(huì)放過(guò)3 結(jié)合1,2號(hào)測(cè)試點(diǎn)就能獲得30分。分其實(shí)我覺得這個(gè)問(wèn)題直接去想不是很好由于通才是要掏錢的，我們來(lái)?yè)Q一個(gè)視角——通拿著人坐地鐵個(gè)通可以與它交換目的地。這樣子的話對(duì)于一張通來(lái)說(shuō)，它還可以這么理解：如那么我們可以這么想，現(xiàn)在有好多好多小段路，（可以由人的行走路線計(jì)算得到）每段都是形如i→i+1或i→i?1。現(xiàn)在我們要在滿足一定條件下，把給n個(gè)通。對(duì)于每個(gè)通來(lái)說(shuō)一小段路正著一次反著一次能免費(fèi)，求最小總代價(jià)。其實(shí)這個(gè)“一定條件”是非常不好表述的——首先對(duì)于每個(gè)通應(yīng)該是條路徑，然后還要不過(guò)這并不妨礙我們得到這個(gè)問(wèn)題的一個(gè)下界：考慮最理想的情況，對(duì)于每一小段統(tǒng)計(jì)正著走的次數(shù)n+和反著走的次數(shù)n?，假設(shè)正著走和反著走能一一配對(duì)供同一個(gè)通。當(dāng)然運(yùn)氣不好就會(huì)有剩下的，即使是最好情況，剩下的也至少是|n+?n?|。于是對(duì)于所有段求這個(gè)差的絕對(duì)值加起來(lái)就是這個(gè)問(wèn)題的下界。然后隨便畫了幾個(gè)圖就會(huì)發(fā)現(xiàn)居然我都可以找到達(dá)到下界的方案。沒錯(cuò)，其實(shí)這個(gè)下界總是可以被達(dá)到的。由于這個(gè)問(wèn)題的最優(yōu)解的取值實(shí)在太好猜了……所以就有了接下來(lái)的問(wèn)題：輸出一組方案。也就是對(duì)于“下界總是可以被達(dá)到的”的證明。如果我們稱通最后被 了的路徑為計(jì)費(fèi)路徑的話，我們現(xiàn)在的任務(wù)就是，構(gòu)造一組方案，使得最終所有方向相對(duì)的 通的計(jì)費(fèi)路徑互不相交。下面我來(lái)說(shuō)說(shuō)我的思60分算法n40方便思維獨(dú)特的選6個(gè)測(cè)試點(diǎn)，n≤100400000的操作數(shù)限制還遠(yuǎn)得很，所以我們只要想方設(shè)為了說(shuō)話方便，向右的我們稱為右卡，向左的我們稱為左卡。顯然，左卡和左卡換，右卡跟右卡換是毫無(wú)意義的。我們只用考慮左卡跟右卡換?，F(xiàn)在我們?nèi)稳蓮埛较蛳喾辞衣肪€相交的通，如圖所示。設(shè)其中右卡編號(hào)為i，左卡編j。我們來(lái)看情況1。然后立刻就發(fā)現(xiàn)右卡i如果向往前走，很有可能在到達(dá)ej之前與某個(gè)迷之左卡擦肩而過(guò)，而失去了這次換目的地的機(jī)會(huì)，情況下，那個(gè)迷之左卡就再也沒有機(jī)會(huì)與其它任何卡換目的地了。從而我們就得假定從si到j(luò)的這段路不在i的計(jì)費(fèi)路徑內(nèi)。這樣就使問(wèn)題越來(lái)越復(fù)雜了。那我們移動(dòng)左卡j唄？發(fā)現(xiàn)也不行。同樣有與迷之右卡擦肩而過(guò)的。再去看看情況2,3,4，基本上都是這樣窘迫的處境。iej。這樣我們就知道，如果是情況1，那么右卡i可以很安全地走到e去，中途不會(huì)碰到任何左卡。但是左卡j仍然很窘迫，往左走仍有碰到迷之右卡的。其實(shí)我們就是希望i是與j相交的右卡中，ei最大的那一個(gè)。這樣就撞不上迷之右卡了。eii于是我們來(lái)到了世界的最右端。首先我們注意到有一群e≥ei的左卡。那么顯然is≤sii直接乘地鐵到達(dá)ie12,3,41ijjj接著交換目的地，jjij（是原先的2jsijeiji怎么辦？我們可以視作i的目的地從一開始就是j這樣就又變成了原問(wèn)題。3jsijs4jjijjji。這樣就這樣持續(xù)地進(jìn)行操作，最后就能構(gòu)造出一個(gè)方案使得所有方向相對(duì)的通的計(jì)費(fèi)路徑互不相交?？紤]操作數(shù)s，由于我們每次調(diào)整都必然會(huì)讓相交的區(qū)間個(gè)數(shù)減少1個(gè)，如果記nL為左卡數(shù)目，nRnLnR4個(gè)操作，所以這部分≤4nLnR不過(guò)還可以算得更仔細(xì)一點(diǎn)。所有讓通到達(dá)目的地的移動(dòng)操作和其它操作我們分開統(tǒng)計(jì)。那么就可以得到：sn

≤n3n)22400000260O(n3)。見subway_n2.cpp80分算法603比較討厭，其它情況都伴隨著一張卡出je≤sis最大的那一個(gè)。不然，就還是按原計(jì)劃選擇j。實(shí)際效果很好。但是我不會(huì)分析s的上界。由于s變小了，所以能夠過(guò)掉前8個(gè)測(cè)試點(diǎn)。見subway_opt_n2.cpp90分算法9,10s4n的樣子。所以我關(guān)鍵還是情況3比較討厭，而我們又想不出什么好辦法避免。那么怎么辦？現(xiàn)在我們想想我們?cè)趺醋叩竭@一步的：不能冒著碰到迷之卡的。而要是我們自己手玩這道題的時(shí)候，其實(shí)倒沒怎么管迷之卡。所以我們丟掉對(duì)迷之卡的恐懼再來(lái)思考問(wèn)題。其實(shí)我們就是要讓正反的小段盡可能配對(duì)，而這兩小段配對(duì)了，干迷之卡什么事？看起來(lái)迷之卡只要處理得當(dāng)，是不會(huì)出問(wèn)題的。而且我們之前還是按時(shí)間順序構(gòu)造。能不能不按時(shí)間順序呢？好，我們從最左邊開始思考問(wèn)題。注意這次是在和右卡的左端點(diǎn)中取最左邊的假設(shè)左端點(diǎn)在最左的是一個(gè)右卡，那么我們可以知道它可以一直往右走直到碰到目的地或者某個(gè)的左端點(diǎn)。那么我們現(xiàn)在就要面對(duì)的是：最左端有一個(gè)右卡i和一個(gè)j。1ijij2，那么我們希望的是：iei，jei，交換目的地。但是略有麻煩，因?yàn)閖有可能碰到迷之。所以其實(shí)應(yīng)該在“最后時(shí)刻”完成這個(gè)操作。即其它所有操作執(zhí)行完成所以對(duì)于情況2，我們就先無(wú)視掉i，并認(rèn)為j的目的地為ei，然后遞歸下去產(chǎn)生一個(gè)操作方案，然后把“i走到ei，交換目的地”添加到操作方案末尾。這時(shí)我們發(fā)現(xiàn)正確性仍然一團(tuán)糟，所以我們換會(huì)原來(lái)的視角——人帶著通上地鐵。們發(fā)現(xiàn)這樣一來(lái)就舒對(duì)于情況1，我們可以讓i走到j(luò)與i,j交換通。也就是交換始發(fā)站，j走到j(luò)。對(duì)于情況2，我們就先無(wú)視掉i，并認(rèn)為j 的目的地為ei，然后遞歸下去產(chǎn)生一個(gè)操作方案。我們實(shí)施這個(gè)操然后會(huì)發(fā)現(xiàn)如果讓i走到ei，j走到j(luò)那么如果i，j的通的計(jì)費(fèi)路徑的方向相反，j的計(jì)費(fèi)路徑和i的計(jì)費(fèi)路徑仍然會(huì)有交。如果通的計(jì)費(fèi)路徑的方向相同，那么反正于是無(wú)論如何我們都可以在這個(gè)操作方案的基礎(chǔ)上加上“讓i走到ei，i與j交換通j走到j(luò)于是我們就可以把所有人按左端點(diǎn)排序，依次處理，把情況1產(chǎn)生的操作直接執(zhí)行，把況2產(chǎn)生的操作按順