信息學(xué)集訓(xùn)隊(duì)作業(yè)acm07nanjing-report

1、ACM07 南京地區(qū)簡(jiǎn)明解題報(bào)告Problem A. Painting the sticks題目大意：一串長(zhǎng)度為n的顏色序列，把連續(xù)的相同顏色的段稱作塊，每次最多染3個(gè)連續(xù)的塊最少要染幾次？n 30。算法：題意理解題，直接模擬題意。復(fù)雜度：O(n)。Problem B. “Ray, Pass me the dishes!”題目大意：給出一段長(zhǎng)度為N的序列，有Q個(gè)詢問(wèn)，詢問(wèn)a,b表示從a到b這段序列中和最大的連續(xù)子序列。其中N，Q 500000。算法：求和最大的子序列有O(N)的算法，然而若對(duì)所有序列都這樣求，復(fù)雜度要到O(NQ)，鑒于詢問(wèn)太多，可以一開(kāi)始建顆線段樹(shù)，線段樹(shù)的節(jié)點(diǎn)存儲(chǔ)該線段的最大

2、連續(xù)子序列，該線段最大前綴，該電斷的最小前綴，然后可以把詢問(wèn)區(qū)間劃分為最多l(xiāng)og N * 2塊，這樣就可以把求最大子序列的復(fù)雜度降為O(logN)。復(fù)雜度: 建樹(shù)的復(fù)雜度O(N)，總復(fù)雜度O(QlogN+N)。Problem C. Plucking fruits題目大意：有一張無(wú)向有權(quán)圖，N個(gè)點(diǎn)，M條邊，權(quán)為1, 100000中的整數(shù)，有R個(gè)詢問(wèn)，詢問(wèn)(a,b,c)表示每次可以通過(guò)權(quán)值c的邊，能否可以從a到達(dá)b。其中N 1000, M,R N*N。算法：用計(jì)數(shù)排序把邊從大到小排序，同樣把詢問(wèn)也從大到小排序，從大到小枚舉當(dāng)前長(zhǎng)度d，加入d的邊，維護(hù)連通集合，計(jì)算長(zhǎng)度最小限制為d的詢問(wèn)，由于n很小

3、，可以用并查集來(lái)實(shí)現(xiàn)集合。復(fù)雜度：并查集復(fù)雜度最多O(N2)，其余復(fù)雜度為O(M + Q)，總復(fù)雜度為O(N2+M+Q)。Problem D. Punish Jiejie題目大意：有兩個(gè)長(zhǎng)度不超過(guò)9的數(shù)字串，不斷寫(xiě)出隨機(jī)數(shù)字，直到出現(xiàn)前面的兩個(gè)串之一為止，問(wèn)期望寫(xiě)多少數(shù)字會(huì)停止，以及出現(xiàn)第一個(gè)串而停止的概率和出現(xiàn)第二個(gè)串而停止的概率。算法：本題較為推薦。這題很容易讓人聯(lián)想到某次CTSC的singland那題，而不同于singland的是這里有兩個(gè)串，不能用singland那樣的算法了，而由于這里的長(zhǎng)度也比較小，只有9，可以用其他一些算法。若兩個(gè)串的長(zhǎng)度分別是len1,len2，那么我們把它們的

4、前綴全部拿出來(lái)，共有l(wèi)en1+len2個(gè)串，再加上一個(gè)空串，共len1+len2+1個(gè)串，這里假定沒(méi)有相同的前綴，有的話直接去掉，我們對(duì)每個(gè)串設(shè)定一個(gè)未知數(shù)，表示目前該串是寫(xiě)出串的后綴，而沒(méi)有更長(zhǎng)的串是它后綴的時(shí)候，還需要寫(xiě)出的期望長(zhǎng)度。那么共有最多19個(gè)未知數(shù)，而對(duì)于每個(gè)串，都能寫(xiě)出一個(gè)等式，如Xi=0.1X(加0后變成的后綴串序號(hào))0.1X(加1后變成的后綴串序號(hào))0.1X(加9后變成的后綴串序號(hào)1，這里求加某個(gè)數(shù)后變成的后綴串可以暴力匹配，那么得到與未知數(shù)個(gè)數(shù)相等的方程個(gè)數(shù)，解方程即可，其概率也可用同樣方法求出。實(shí)現(xiàn)過(guò)程中要注意精度的問(wèn)題。復(fù)雜度：所有暴力匹配的復(fù)雜度之和為O(Len3*

5、10)，解方程復(fù)雜度為O(Len*2)3，總復(fù)雜度為O(Len3*18)。Problem F. Remember the Word題目大意：給出一長(zhǎng)度L最大為300000的串，再給出一個(gè)有S個(gè)串的字典，字典中串的長(zhǎng)度Len最多為100，S 4000，問(wèn)把原串用字典中的串組成有多少種方法，字典中的串可以重復(fù)使用。算法：trie應(yīng)用的經(jīng)典問(wèn)題，利用字典建trie，fi表示截至原串的第i位，有多少種分法，從fi往后推，從第i+1位開(kāi)始從trie的根節(jié)點(diǎn)往下找，找到一個(gè)單詞就把fi加到fj上(j是原串中目前尋找字符的位置)，直到找不到下一個(gè)字符或原串結(jié)束為止。復(fù)雜度：建trie的復(fù)雜度O(S*Len)

6、，求f的復(fù)雜度O(Len * L)，總復(fù)雜度為O(S+L)*Len)，空間復(fù)雜度為O(S*Len*26)。Problem G. Likings Letter題目大意：給出長(zhǎng)度為L(zhǎng)的一字符串，求最長(zhǎng)重復(fù)出現(xiàn)的子串。其中L 200000。算法：suffix array應(yīng)用的經(jīng)典問(wèn)題，求出suffix,rank,height后，height的最大值即為答案。復(fù)雜度：求suffix的復(fù)雜度最好能到O(L)，然而這里用O(L log L)的倍增算法便已足夠。Problem H. Present for 119題目大意：一個(gè)N*M實(shí)數(shù)矩陣，能否對(duì)每個(gè)數(shù)取上整或下整使得滿足，其每列的和為原矩陣該列和取上整或

7、下整，行也如此。若行，給出方案。N,M1000。算法：該題即為去年CTST中某題較簡(jiǎn)單的一小問(wèn)。該問(wèn)題顯然可以轉(zhuǎn)化為矩陣只有0,1)區(qū)間的實(shí)數(shù)，而此時(shí)給每行每列求和，要求給出一個(gè)01矩陣，其每行的和為相應(yīng)和取整或取整加1，列也一樣。這個(gè)一定是有解的，并且可以用網(wǎng)絡(luò)流求，但速度不快，略顯麻煩。事實(shí)上貪心即可。把實(shí)數(shù)求和以后先全取整，然后若行的和比列的和大的話，隨意取一部分列的和加一，否則取一部分行的和加一，使得平衡。然后對(duì)于每一列的和i，取出當(dāng)前最大的i個(gè)行和，把這i行這一列的格子全填1，其余為0，把這i個(gè)行和-1，可以證明，到最后肯定能剛好使所有行和變?yōu)?，想想是對(duì)的，但證明比較復(fù)雜，這里就不

8、贅述了。復(fù)雜度：利用計(jì)數(shù)排序?qū)崿F(xiàn)貪心，總復(fù)雜度為O(N,M)。Problem 題目大意：求平面上N個(gè)點(diǎn)的最小外接圓。其中N 500000。算法：本題較為推薦?？催@個(gè)規(guī)模O(N log N)都危險(xiǎn)，而剛好求最小外接圓有O(N)的期望算法，而其常數(shù)非常大，剛好這里O(N)非常寬裕。黑書(shū)計(jì)算幾何章節(jié)中有對(duì)此問(wèn)題的討論，用的是隨機(jī)增量的思想，其方法是這樣的，維護(hù)當(dāng)前所有點(diǎn)的最小外接圓，每次隨機(jī)加一個(gè)點(diǎn)，若該點(diǎn)在圓內(nèi)或圓上，那沒(méi)話說(shuō)，若在圓外，可以證明此點(diǎn)一定是新的外接圓的邊界，此時(shí)枚舉另一個(gè)點(diǎn)，再用張角法，可以用O(N2)求出新的外接圓，此時(shí)，復(fù)雜度為O(N) + O(i2)*3/i=O(N2)，這里

9、的3/i其實(shí)就是說(shuō)，當(dāng)前有i個(gè)點(diǎn)時(shí)，新的點(diǎn)有3/i的幾率在邊界上，然而由于這里求新外接圓的復(fù)雜度太高，導(dǎo)致總復(fù)雜度還是有O(N2)。事實(shí)上，我們可以再用隨機(jī)增量的方法來(lái)求這個(gè)新的外接圓。一個(gè)固定點(diǎn)，再加上其他i個(gè)點(diǎn)，要求圓，怎么求？同樣的道理，每次隨機(jī)加入一個(gè)點(diǎn)，若該點(diǎn)在圓外，那此點(diǎn)一定在新圓邊界上，那么用該點(diǎn)和固定點(diǎn)當(dāng)邊用張角法O(i)求出第三個(gè)點(diǎn)，這里要注意：中間過(guò)程中得到的圓不一定是最小外接圓，而是過(guò)固定點(diǎn)的最小外接圓。然而到最后求出的圓就一定是最小外接圓了。復(fù)雜度：我們的求新外接圓的新算法復(fù)雜度為O(N) + O(i)*2/i = O(N)，因此，原題算法的復(fù)雜度即為O(N) + O(i)*3/i = O(N)。Problem J. Cake slicing題目大意：N*M的蛋糕上有一些櫻桃，每次可以一刀沿邊線把蛋糕切成兩塊，并且只能夠直切，不能拐彎，問(wèn)最少切過(guò)的邊線長(zhǎng)度為多少，能使蛋糕的每一塊上剛好有一個(gè)櫻桃。N, M 20。算法：也是一道陳題了。四維DP，fx1y1x2y2就表示蛋糕中(x1,