第一階段作業(yè)試題泛做jcvbcn

1、2016 年集訓隊作業(yè) Codechef 試題泛做杭州學軍中學(比較有意思的題目會標上 )1數(shù)據(jù)結構題1.11.21試題MAY15 CBAL試題名稱Chef and Balanced Strings題目大意算法一個小寫字母組成的字符串。一個子串是平衡的當且僅當每種字符都出現(xiàn)偶數(shù)次。每次詢問一個區(qū)間內所有平衡子串的長度的 type 次方和。強制 ， (n 100000, type 0, 1, 2)給每種字母分配一個二進制位。求出數(shù)組的前綴異或和，那么子串 l, r 平衡當且僅當 prel 1 = prer。由于只涉及到相等關系，可以把這些數(shù)值離散化。然后用經典的 莫隊方法：分塊解決，預處理出第

2、i 塊到第 j 塊的 。詢問的時候先找出對應的大塊區(qū)間，然后把兩邊多出來的部分往里面暴力添加。添加時只需要 每種下標的 0 次方、1次方、2 次方和即可，這些值也需要在開頭預處理好，于是每添加一個數(shù)是 O(1) 的。時空復雜度空間 O(nn)，時間 O(nn)。試題AUG15 DISTNUM試題名稱Simple Queries題目大意算法一個正整數(shù)數(shù)組。現(xiàn)在有關于它的 Q 個詢問。詢問有 5 種：（1） 對于下標在 l, r 區(qū)間的所有元素去重后的集合， 求出xyz xyz（2）ax = y刪除 ax在 az 之后y 元素詢問下標在 l, r 區(qū)間內的有多少種不同的元素。(n, q 105)

3、可以離線。首先有 操作比較麻煩，但因為是離線的，可以事先預處理出每個 的位置。這一步可以用一個平衡樹來完成。這樣后面只要在靜態(tài)序列上搞就可以了。操作 (5) 是經典的數(shù)顏色問題，只要把每個點看成二維平面上的點 (last x, x)，這樣只要統(tǒng)計區(qū)間 l, r 內 last n 的情況，至多分成 n 段，因此可以貪心 。對于 d n 的情況，只要讓它每次跳過一個前面的關鍵點，這樣也只要跳 O(n) 次。為了實現(xiàn)跳躍，需要對于所有 d n 處理出每一個 u 跳到祖先的最近關鍵點所需要的步數(shù)，以及跳過后落在哪個位置。如果按照原題的描述，看起來還要實現(xiàn)從 LCA 往下面跑的過程，其實不必要，這個貪心

4、兩邊開始往中間分別貪也是沒關系的，所以只要分別從 u, v往上朝著 LCA 跑就可以了。要實現(xiàn)跳 d n 步，可以轉化為跳若干個大步，再用預處理的數(shù)組的結果跳一個小步。跳大步的總數(shù)是 O(n) 的，所以復雜度還是 O(n)。時空復雜度空間 O(nn)，時間 O(nn)。1.61.71.8JAN15 XRQRSXor Queries試題試題名稱題目大意算法用可持久化 01trie 來一個數(shù)列，支持以下操作：在末尾插一個數(shù)；求區(qū)間內的數(shù)與 x 異或的最大值；刪除末尾的 k 個數(shù)；求區(qū)間內一個數(shù)的排名；求區(qū)間內第 k 大。插一個數(shù)就直接在 last 版本上插，刪末尾幾個只要將 last 指針往前移就

5、行。然后 01trie出現(xiàn)次數(shù)時是可以相減的，用 r 的減去 l 1 的就得到l, r 的。所以（2）（4 ）（5）幾個經典操作也是能做的。(操作數(shù)目 m 500000， 權值x 500000)空間 O(m log x)，時間 O(m log x)。時空復雜度3試題APRIL15 BWGAME 試題名稱Black-whitGame題目大意算法考慮所有 n 排列 p，滿足 li pi ri，這些排列中奇排列和偶排列哪個數(shù)量 ？n 100000考慮一個 n n 矩陣，第 i 行的 li, ri 列填 1 ，其他填 0，問題就轉化為求這個矩陣的行列式?？紤]消元的過程，當前處理第 j 列，則把所有左端

6、點為 j 的區(qū)間拿出來，取其中右端點位置最靠左的 p，并用 p 去消其他左端點為 j 的區(qū)間，容易發(fā)現(xiàn)消元之后每一行的 1 仍然保持連續(xù)一段區(qū)間的形狀，而且被消的區(qū)間的左端點變?yōu)?p 的右端點 +1，而其各自的右端點不變。于是可以用可并堆來 這些詢問與操作。時空復雜度空間 O(n)，時間 O(n log n)。試題MARCH15T2試題名稱Counting on a Tree題目大意算法一棵 n 個點，帶整數(shù)邊權 ai 的樹，q 個操作，每次修改一條邊的權，并查詢有多少條簡單路徑上的權值 為 1。(n 100000, ai 1000000, q 100)容易想到容斥，那么需要枚舉所有 (x)

7、=0 的 x，并選出邊權為 x 的倍數(shù)的邊組成的子圖統(tǒng)計其路徑數(shù)量然后加到里去。如果每次都重復求一遍會很慢。注意到只有 100 個修改操作，也就是說大部分邊都是保持不變的，所以在用并查集做的時候，可以把那些不會被刪除的邊給加進去，然后對于每個操作，把需要的邊插到并查集，然后統(tǒng)計，之后再恢復到插之前的狀態(tài)，然后做下一個詢問。這樣復雜度是可以承受的。時空復雜度空間 O(nd(ai)，時間 O(nd(ai) + (qd(ai)2) log n)。1.91.101.114試題NOV13 MONOPLOY試題名稱Gangsters of Treeland題目大意算法一棵有根樹，每個結點有顏色，初始時都不

8、同。一條邊若兩端顏色不同則需要 1 的代價。支持兩種操作：將 u 到根路徑上的點染成一種沒出現(xiàn)過的顏色；詢問一個內每個點到根的代價的平均值。(n, q 100000)根據(jù)題意，修改操作實質就是 LCT 的 ac s 操作，所以只需要用 LCT 這棵樹，并在每次 ac s 時發(fā)生虛實邊替換的時候，對應的修改邊上的邊權。邊權和詢問可以轉化到 DFS 序上，然后用樹狀數(shù)組/線 來查詢。時空復雜度空間 O(n)，時間 O(n log2 n)。試題MAY14 ANUDTQ試題名稱Dynamic Trees and Queries題目大意算法一棵樹的點權，支持以下操作：（1）添葉子；（2）；刪除一棵；詢問

9、和。強制。(n, m 100000)如果只有 (2)(4) 操作，就是一個經典的 DFS 序題目，用線 即可?，F(xiàn)在問題在于樹形態(tài)會變化。可以用一棵 splay 來樹的 DFS 序。為了方便，采用括號序列。添葉子時，只要在父親結點對應的左括號后面加一對括號。子樹操作只要把一對括號之間的區(qū)間提取出來，然后進行操作。時空復雜度空間 O(n)，時間 O(n log n)。試題JUNE14 SEAARC試題名稱Sereja and Arcs題目大意算法長為 n 的序列 ai，有多少組 i j k l 滿足 ai = ak = aj =al。(n 100000, ai 100000)按出現(xiàn)次數(shù)多的（大于

10、S 次）顏色和出現(xiàn)少的 ( S次）分類計算。首先算 ai, aj 都是少數(shù)顏色的：注意到兩個顏色各選兩個有 AABB, ABAB, ABBA 三種情況，AABB 是很好統(tǒng)計的，所以只要算出 ABBA 的情況即可，這個只要從左到右掃，掃到 A 的時候就枚舉之前出現(xiàn)過的 A，于是只要查詢區(qū)間內有幾對 BB 就好，這可以用樹狀數(shù)組，每次掃到 B 的時候往前每一位 B 處增加 1 就行。這樣要做不超過 S2 n/S 次樹狀數(shù)組操作。接著算 ai 是多數(shù)色的?？偣仓挥胁怀^ n/S 種多數(shù)色，枚舉固定一個多數(shù)色 A 然后算。算出每個 B 左邊有多少個 A，兩兩乘起來，這樣算得的結果包括了 ABAB 和

11、AABB 和 ABB，把后兩類剔除即可。這樣一次是 O(n)的。 log時空復雜度空間 O(n)，時間 O(n nn) 。1.121.131.145試題MARCH14 STREETTA 試題名稱The Street題目大意算法兩個長為 n 的數(shù)組 a, b。支持三種操作：給 a 的區(qū)間 l, r 加上等差數(shù)列；給 b 的區(qū)間 l, rmax 上等差數(shù)列；詢問單點的值。(n 109, q 3 105)首先離散化然后用線 。第一個操作有經典的做法，對線 每個結點標記兩個值 k, b，表示這一個區(qū)間中的所有 x 都被加上了 kx + b。（ 化標記）第二個操作也有經典的做法，對線 每個區(qū)間一條（坐標

12、系中的）線段。每當一條新的線段覆蓋到這個區(qū)間上，先檢查這條線段是否永遠比原來的優(yōu)（或劣），如果是則替換（或扔掉），如果不是則有交點，那么在交點的另一側的兒子區(qū)間肯定是完 （或扔掉的），所以只要往交點這一側遞歸下去就行。時空復雜度空間 O(m)，時間 O(m log2 m)。試題MAY13 QTREE試題名稱Queries on tree again!題目大意算法一個 n 個點 n邊的連通圖，邊帶有邊權。支持兩種操作：將 u 到 v 路徑上的邊權乘 1；詢問 u 到 v 路徑上的邊權的最大連續(xù)子段和。路徑都指最小結點數(shù)目的路徑，保證唯一。(n 105, q 105)最大連續(xù)子段和的經典做法是 四

13、個信息sum, lmax, imax, rmax，這里需要變號所以還要三個 min。這樣就支持變號已經信息合并了。鏈詢問和操作只要樹鏈剖分并用線 即可。這里是一個基環(huán)外向樹。比較方便的處理方法是看成整棵樹加上一條多余邊。對于給出的兩點，只要算一下經過這條邊的路徑和不經過的哪個更短即可，如果走額外邊更短的話，所需要的路徑就拆成了兩條樹上路徑加這條額外邊。時空復雜度空間 O(n)，時間 O(n log2 n)。試題SEPT14 QRECT試題名稱Rectangle Query題目大意算法平面上的矩形（邊平行坐標軸），支持：矩形；刪除矩形；詢問與給定矩形相交的矩形有多少個。(q 100000)可以轉

14、化一下，統(tǒng)計與給定矩形不相交的有幾個。這只要判斷端點的關系就可以了。先看看一維情況，就是統(tǒng)計右端點右邊的左端點數(shù)和左端點左邊的右端點數(shù)。二維情況稍微推廣一下，就是右下端點的左下角的左上端點數(shù)目（以及其他三個方向，通過旋轉 90 度即 到）。這樣題目就變成了加點、刪點及二維區(qū)域點查詢。經典做法是用二維線，或者離線分治套一維樹狀數(shù)組。時空復雜度空間 O(n)，時間 O(n log2 n)。1.151.161.17 JULY12 DDynamic試題試題名稱題目大意樹上的點權，支持操作（1）鏈算法先樹鏈剖分轉化為鏈上問題。考慮鏈上的這個數(shù)上加 d，（2） 詢問鏈上點權的。(n, q 50000)列

15、a1, a2, , ak，對它做差分得到 a1, a2 a1, a3 a2, 。這樣修改操作就轉化成了單點修改。另外注意到(ai, ai+1, , aj) =(ai, ai+1 ai, , aj aj1)，于是只要查詢區(qū)間的以及ai 的值即可。ai 就是一個前綴和。所以只要用線和 sum 即可?？臻g O(n)，時間 O(n log2 n log d)。時空復雜度6試題SEPT14 FIBTREE試題名稱Fibonacci Numbers on Tree題目大意算法一棵樹上的點權。支持操作：鏈加 b 數(shù)列；詢問鏈和；定一個點為根后詢問某點的和；回到過去某一版本。模 109 + 9 輸出，強制。(

16、0 n, q 100000)樹剖后上線，線要可持久化。另外由于有詢問，還需要 DFS 序，這個 DFS 序要按照先走重鏈的順序，這樣既可以處理鏈又可以處理。換根不需要真的換根，只要檢查一下樹根和詢問點的祖先關系，看看詢問的 在原樹中也是 ，還是 的補集?，F(xiàn)在只需要考慮怎么用線 b 數(shù)。按照 b 數(shù)的通項公式，可以將它拆成兩個等比數(shù)列的和，而等比數(shù)列是可以 的，只要標記一個區(qū)間被加的等比數(shù)列的首項就可以了。計算的時候涉及到 5 的，它是 109 + 9 的二次剩余，所以直接用整數(shù)就可以完成計算。時空復雜度空間 O(n log2 n)，時間 O(n log2 n)。試題NOV14 FNCS試題名稱

17、Chef and Churu題目大意算法一個長為 n 的數(shù)列 a 和 n 個函數(shù)。第 i 個函數(shù)返回值為數(shù)列中第 li 到 ri 項的數(shù)字之和。支持兩種操作：將 ax 修改為 y;詢問第 p 個到第 q 個函數(shù)的返回值之和。( n 105 )首先對操作分塊。開始處理某一塊操作前，把目前的數(shù)組情況以及每個函數(shù)的返回值（及他們的前綴和）先預處理好。接下來只需要考慮塊內的修改操作對塊內且在它后面的詢問操作的貢獻就行了。枚舉塊內的每一對修改操作和詢問操作統(tǒng)計貢獻，這樣就變成了查詢對于某個點 x ，有多少個 p y q 滿足 ly x ry，這可以變成兩次詢問 1 y p 1 與 1 y q 。這樣對于

18、所有塊共有 O(n n) 個這樣的詢問。掃一遍n 個函數(shù)，并用區(qū)間加法 O(n)，詢問單點 O(1) 的分塊即可。時空復雜度空間和時間都是 O(nn)1.181.197試題OCT14 BTREE 試題名稱Union on Tree題目大意算法一棵邊權均為 1 的樹，每次詢問給定k 個點 ui 以及各自的控制距離 di，每個點能控制距離不超過 di 范圍內的點，問被控制的點總共有幾個。(n 50000, k 500000)首先對詢問點建出虛樹，虛樹上沒有控制能力的點的 d 可以設為 1?？?慮 兩 個 點 u, v， 可 以 把 dv 設 置 為max(dv, du dis(u, v)。 對所有

19、點按照這一規(guī)則更新它們的控制能力直到不能更新為止，這一步可以用一個類似 dijkstra 的過程來完成。對于虛樹上每條邊 (u, v)，容易看出 u, v 的控制范圍的交集是以 r 點為中心，(du + dv dis(u, v)/2為半徑的區(qū)域，其中 r 是路徑 (u, v) 上的某點（可以事先在每條邊上加虛點保證中點存在）。然后答案即為每個點的控制點數(shù)減去每條邊上 (u, v) 的控制范圍交集的點數(shù)。（由于 du 都已經被更新到最大，所以這可以證明是正確的）。為了統(tǒng)計離 u 距離不超過 d 的數(shù)目，可以用點分治。點分治的每層需要 各個高度的點的數(shù)量的前綴和。 loglog時空復雜度空間 O(

20、n log n + k)，時間 O(kk + nn)。試題FEB14 COT5 試題名稱Count on a Treap題目大意算法一個 treap。支持：一個關鍵字為 key，權重為 w 的結點；刪除一個關鍵字為 key 的結點；詢問結點 u, v 在 treap 上的距離。根結點權重最大。(n 2 105)按照 key 作為下標的順序， 一個 w 的序列。給定兩個位置 l, r，區(qū)間 l, r 中權值最大的即為 l, r 的 LCA。要詢問距離的話，只要知道這三個結點的高度即可。注意到 h(u) = u的祖先數(shù)目 = u的左邊的祖先數(shù)目 +u的右邊的祖先數(shù)目。于是可以左右分開統(tǒng)計。x 是

21、y 的祖先當且僅當 x 到 y 這段 沒有比 x 更大的點把它擋住，所以這是一個經典的“看到幾座樓房”問題。經典做法是用線，除了區(qū)間最大值之外，還要從 l 中最高的結點往兄弟結點 r 方向能看到幾個，以及從 r 中最高結點往 l 能看到幾個。查詢這個東西的復雜度是 O(log n)，因為利用的信息可以每次只往一邊遞歸。所以單點更新要做 O(log n) 次，復雜度是 O(log2 n)。回答一次高度詢問需要對拆分成的 O(log n)個區(qū)間分別查詢，所以總復雜度也是 O(log2 n)。時空復雜度空間 O(n)，時間 O(n log2 n)。1.201.211.228試題JAN12 CARDS

22、HUF試題名稱Card Shue題目大意算法一堆初始順序是 1 n 的牌。每次執(zhí)行下述操作：從牌堆頂端拿走 A。再從牌堆頂端拿走 B。將第一步拿走的 A放回到剩下的牌堆上面。從牌堆頂拿走 C。將第二步你拿起的 B一張一張放到牌堆頂。最后，將剩下的 C放回到牌堆頂。最后輸出操作完后的序列。(n, m 105)用數(shù)據(jù)結構模擬這些操作。需要支持的操作有區(qū)間裁剪并 ，以及區(qū)間翻轉。用 splay 來實現(xiàn)即可。時空復雜度空間 O(n)，時間 O(n log n)。試題FEB12 FINDSEQ試題名稱Find a Subsequence題目大意算法給一個整數(shù)列 a1.n，和一個 5 排列 p1.5。求出

23、一個 a 的長為 5 的子序列，使得它的大小順序和 p 一致。 (n 1000)枚 舉 p2, p4 分 別 對 應 哪 兩 個 位 置， 那 么 p1, p3, p5 各自屬于一段區(qū)間，這三個區(qū)間之間不相交，處理起來更方便。現(xiàn)在考慮這三個數(shù)怎么選，最大的那個肯定是越大越好，最小的那個也是越小越好。所以只要求出最大的和最小的，然后要找的是卡在中間的那個。這可以通過二分查找完成。為了二分的方便，可以預處理一個 f ij 數(shù)組，表示前 i 個數(shù)中不超過 j的有幾個。預處理之前需要先離散化。時空復雜度空間 O(n2)，時間 O(n2 log n)。試題DEC13 QTREE6試題名稱Query on

24、 a tree VI題目大意算法一棵樹，每個點有黑白兩色之一，支持以下操作：詢問一個點所在的同色連通塊的大??；翻轉一個點的顏色。(n, m 100000)對于每個點 以它為根結點的黑色連通塊和白色連通塊的大小 bi, wi。詢問時，只要找出詢問點所在的連通塊的根 i，再輸出bi 或 wi 就可以了。找出根可以用樹狀數(shù)組 + 二分在O(log2 n) 時間完成。翻轉一個點的顏色時，從它到它所在連通塊的根這段路徑上的結點 v 的 bv, wv 值會發(fā)生變化，所以 還需要實現(xiàn)一個鏈加操作。由于詢問都是單點的，所以這里可以變成單點改， 和查詢，更加方便。時空復雜度空間 O(n log n)，時間 O(

25、n log2 n)。2圖，匹配，網絡流2.12.2FEB14 DAGCHGraph Challenge試題試題名稱題目大意算法按照定義，superior vertex 即為半必經點 se-n 個點的有向圖按 DFS 序。x 是 y的 supreme vertex，當且僅當存在有向路mi。用 dominator tree 的算法計算即可。x = v0, v1, , vk = y ，且 x y vi。v 是 w 的 superior vertex，當 v 是 w 的所有 supreme vertex 中最小的。輸出每個結點有多少個結點將它作為 su- perior vertex。(n 100000

26、, m 200000)空間 O(n + m)，時間 O(n + m) log(n + m)。時空復雜度2.39試題MAY12 TICKETS試題名稱Selling Tickets題目大意算法一個無自環(huán)，可能有重邊的無向圖。求一個 k，使得不論怎樣選取其中 k條邊，都能讓這些邊各自選擇自己的一個端點，且每條邊選到的點不重復。 (n 200, m 500)根據(jù)題意，要選擇一個邊數(shù)最少的子圖，使得這個子圖的點數(shù) = 邊數(shù) 1。這樣的圖一共有三種情況：兩個點之間的三條路徑。這可以枚舉起點和終點，然后跑 BFS，并 下到達終點的三條距離。一條路徑連著兩個簡單環(huán)。這只要對于每個點求出經過它的最小簡單環(huán)就可

27、以了。這可以 BFS，如果一條非樹邊的兩端的 LCA 是根結點，則用它來更新。順便要一下環(huán)上是那些邊。因為最后合并時不能有兩個相同的環(huán)并起來。一個點連著兩個簡單環(huán)。只要順便記下通過每個點的次短環(huán)就好了。中間可能會有一些重復邊經過，但經過重復邊的一定不是最優(yōu)解，只要無視它們就行。時空復雜度空間 O(n + m)，時間 O(n2(n + m)。試題MAY15T試題名稱Counting on a directed graph題目大意算法n 個點的有向圖。有多少對結點 (x, y) 滿足存在 1 到 x 和 1 到 y 的路徑，且兩條路徑僅有公共點 1。(n 100000, m 500000)以 1

28、為根求出 dominator tree。這樣，樹上 LCA 為 1 的每一對結點都符合條件。時空復雜度空間 O(n + m)，時間 O(n + m) log(n + m)。2.42.52.610試題JULY15 HAMILG 試題名稱A game on a graph題目大意算法無向圖 G 上有一顆棋子，初始時放在結點 v 上。兩個人輪流移動棋子，可以將它沿著邊移到相鄰結點上，但不能移到它曾經走到過的結點。不能走的人輸。統(tǒng)計有多少個初始結點 v 能使得先手勝利。(n 2000, m 106)首先注意到一個結論：v 能使得先手勝當且僅當存在某個 G 的最大匹配不包含 v。（考慮不存在增廣路這一性

29、質即可證明）先用帶花樹算法跑一遍最大匹配。然后再從所有沒被匹配的結點開始做一遍尋找增廣路的過程，這個過程是找不到增廣路的，但是在途中入隊過的結點都可以不被最大匹配包含。輸出入隊過的結點數(shù)目即可。時空復雜度帶花樹的時間復雜度 O(nm)。試題JUNE11 MINESREV試題名稱Minesper Reversed題目大意算法一個 r c 的掃雷盤面。開始時所有格子都是開的，你要把它們關上，且用的步驟最少?？梢渣c擊一次關閉一個格子，同時關閉所有可以和它同時打開（按照正常規(guī)則）的格子。(r, c 50)這是一道閱讀理解題。首先雷是要一個個點的。然后考慮周圍有雷的數(shù)字格和周圍無雷的空白格?？瞻赘竦倪B通

30、塊可以打開，還順便打開了周圍的數(shù)字格。一個數(shù)字格旁邊至多有兩個不同的空白格連通塊，如果有兩個，就可以通過打開這個數(shù)字格然后把他倆都打開。所以可以在它們之間連一條邊。接下來求出這個圖的最大匹配數(shù)。對于所有匹配邊， 打開這兩個塊。剩下的塊都一個一個的開。由于這里的圖不一定是二分圖，所以求最大匹配要用帶花樹算法。時空復雜度空間 O(rc)，時間 O(rc)3)。試題JAN14 TAPAIR 試題名稱Counting The Important Pairs題目大意算法給一個簡單連通無向圖，有多少對邊，使得刪除這兩條邊后圖會不連通？(n 100000, m 300000)這題有一個經典的 hash 做法

31、：求一棵 dfs 生成樹，并給所有非樹邊（只能是返祖邊）分配一個隨機權值；所有樹邊的權值是覆蓋了它的非樹邊的權值的異或和。一個邊集被刪去后使得原圖不連通，則它存在一個邊的子集使得其權值的異或和為 0。 用這個做法，此題中只需考慮 2 元邊集，所以更加方便。時空復雜度空間 O(n + m)，時間 O(n + m log m)。2.72.82.911試題DEC14 RIN 試題名稱Course Selection題目大意算法有 n 個科目和 m 個學期。第 j 個學期上i 科目的得分是 xij。有 k 個條件 (a, b)表示 a 科目需要在 b 科目之前上。安排每門課在哪個學期上，獲得的最大總分

32、是多少？(n, m, k 100)最小割建模。對每門課建一排共 m + 1 個點，在第 i 個和第 i + 1 個點之間割斷，表示在第 i 個學期上這門課。割邊的權值設為這門課的最大可能得分減去這個學期的得分。源點向每門課的第一個點連邊，每門課的最后一個點連向匯點，權值為 。對于前置課程 (a, b)，只要從 a 的第 i 個點連向 b 的第 i + 1 個點，權值為 。時空復雜度網絡流復雜度，點數(shù) O(nm)，邊數(shù) O(n + k)m)。試題JULY14 GNUM試題名稱Game of Numbers題目大意算法整數(shù) a 序列和 b 序列， 每次挑出 i, j, p, q， 其中 (i, j

33、),(p, q) 分別不出現(xiàn)過， 且 ai bj, bp 1。最多能取幾次。(1 n 400, ai, bi 109)這是一個二分圖最大匹配模型，對所有 ai bj 的 (i, j) 建另一排點，若不為 1 則連邊。但 這 樣 構 圖 邊 數(shù) 太 多， 需 要 優(yōu) 化。 首 先 將(i, j) = 1 的點扔掉，再將相同的點合并。然后優(yōu)化邊，兩個數(shù)有邊當且僅當有公共質因子，那么就對所有質因子建一個點，然后把擁有這個質因子的數(shù)字連向它（或者由它連出）。然后跑 dinic 就可以了。時空復雜度網絡流點數(shù) O(n2)，邊數(shù) O(n2 log ai)。試題AUG12 GTHRONES試題名稱A Gam

34、e of Thrones題目大意算法一堆數(shù)字寫在紙上。兩人博弈。第一個人隨便擦一個數(shù)字。后一個人也要擦一個數(shù)字，但擦的數(shù)字必須和對方上次擦的數(shù)字只相差一個素因子。不能動的人就輸。求必勝方。如果先勝的話要輸出第一步操作的可行步驟。(1 n 500, 1 number 1018, 1 count 109)這題是 HAMILG 那題 (undirected vertexgeography) 的特殊化。這里的圖顯然是二分圖。但是由于一個數(shù)可以出現(xiàn)很多次，建多個點是無法承受的，所以要把匹配寫成最大流的形式。 刪一個點后判斷最大匹配數(shù)是否減少，如果重復跑最大流會太慢，比較好的辦法是利用退流。退流 (u,

35、v) 時只要讓 (u, v) 的流量減 1，然后從 t 到 v 增廣，從 u 到 s增廣。構圖時需要質數(shù)判定， 可以用 miller- rabin。時空復雜度空間 O(n)，時間 O(n2 log A + maxflow(n, n2)。2.102.112.1212試題SEP12 PARADE 試題名稱Annual Parade題目大意算法一個有向圖，邊有非負權值。求若干條路徑，使總代價最小。代價計算方式是：每條路徑的長度之和；如果一條路徑不是閉合的則對每條附加 C 的代價；如果一個頂點沒有被經過則每個點附加 C 的代價。多次詢問 C。(n 250)關鍵在于分析這個代價計算出來的到底表示什么。首

36、先對每一對點 (u, v) 都加上新邊，權值為 dis(u, v)。則這個新圖的 不變，而且可以使得存在一個最優(yōu)解中每個點都至多被 一次（因為如果有多條路徑擠在同個點上，可以把它移動到新邊上去）。這個條件滿足之后，可以發(fā)現(xiàn)每新加入一條邊，所花的總代價就會減少 C （要么成環(huán)，要么多經過一個點）。于是只要對于邊權二分圖求出所有 k 匹配的最小代價和就好?？梢杂?KM 或費用流。時空復雜度空間 O(n2)，時間 O(n3 + q log n)。試題JUNE14P試題名稱Two Companies題目大意算法一棵樹上有許多 A 路徑和 B 路徑，每個路徑 值。選出一些路徑，使得每個點都不會同時被 A

37、 路徑和 B路徑經過。求最大權值總和。(n 100000, 1 m1, m2 700)這是一個二分圖最大權獨立集模型，可以轉化為最小割。構圖時要對每一對 A, B 路徑判一下是否相交，這只要對 LCA一下就好了。時空復雜度預處理 O(n log n + m1m2)。網絡流點數(shù) O(m1 + m2)，邊數(shù) O(m1m2)。試題NOV12 MARTARTS 試題名稱Martial Arts題目大意算法一個完全二分圖，邊有兩個權值Aij, Bij。求一個完全匹配。令 H = A, G = B。對手目的是最大化 G H，其次最大化 G。你公布匹配方案之后，他可以刪（也可以不刪）一條匹配邊，達到他的目的

38、。你的目的是最大化 H G，其次最大化 H。求最優(yōu)策略下的比賽結果。(n 100)先不考慮第二關鍵字，只要最大化 V = A B。那么一個匹配的 實際上是總權值和減去最大的一條權值。 可以從小到大枚舉匹配中的最大邊，將這條邊強制選中，然后對比它小的邊所形成的圖做一次最大權匹配。一條邊強制選中可以通過將邊權改為，強制不選可以改成 。所以這個問題就變成了修改邊權并動態(tài) 最大完美匹配。用 KM 算法，每次修改一條邊 (u, v) 的邊權時，先將 u 原先的匹配邊斷掉，然后重置 u 的頂標為 Au = max(w(u, j) Bj)，這樣依然滿足頂標的條件。然后再從 u 出發(fā)尋一條增廣路。這樣一次修改

39、的代價只需要 O(n2)考慮第二關鍵字的話，只要把參與運算的全部改為二元組即可。時空復雜度空間 O(n2)，時間 O(n4)。3網絡流和線性規(guī)劃3.13.213試題FEB12 FLYDIST試題名稱Flight Distance題目大意算法給定圖的 n 個頂點和 m 對頂點間的距離。這些距離信息可能是有 的（不滿足三角不等式）。修改一個距離值需要 |d d| 的代價（有理數(shù)）。求最小的總代價可以將信息修改成沒有。(n 10, m 45)考慮線性規(guī)劃。對所有 1 i p, (a p)(b p)|ab。(p 1012)可以轉化成求有多少組 a 1, b 1 使得 ab|p(a + b + p)。當

40、 p|a, p|b 時可以證明有 5 組解。當 p - a, b = bp 時，令 k = ab/(a + pb + p), d = ka p，則有 d|a + p, a|d + p，且 a, d 均與 p 互質，此時有 ad|(a + p)(d + p)，和原題的式子相同，可以轉化成第三種情況。所以現(xiàn)在只要考慮 p - a, p - b，即有 a + b + p = kab。a = b 時有 a = b = 1，只要考慮 a b。那么 (a 1)(b 1) p + 1，則 a p + w，有 b = (a + p)/d (a + p)/p + w p + w，所以枚舉 b，此時也可以唯一的確

41、定 a 和 d。時空復雜度空間 O(1)，時間 O(p)。試題SEP11 SHORT試題名稱Short題目大意算法給定 n, k，求出有幾對整數(shù) (a, b) 滿足 n a k, n b k, (a n)(b n)|ab n。(0 n 100000, n k 1018)先特判掉 n = 0 的情況。 n(a1) 令 p(a n)(b n) = ab n，得 b = n + p(an)a ?？紤] a b 的情況并枚舉 a，根據(jù)題中關系可以化出一個二次不等式從而得到 a 的上界 a 3.42n，然后只要枚舉 n(a1) 的所有約數(shù) d = p(an)a，然后看 p 是否為整數(shù)即可。為了枚舉約數(shù)，可

42、以先篩出 3.42n 以內所有數(shù)的質因數(shù)分解，然后就能得到 n(a 1) 的質因數(shù)分解，于是 DFS 就可以了。對于 a 較大的情況，可以改成枚舉上式中的 p。由2一些不等關系可以得到 p a n ，這個范圍會比(an)2較小，于是可以加快速度。時空復雜度空間 O(n)，時間玄學。5.35.417試題AUG11 DIVISORS試題名稱Something About Divisors題目大意算法對于給定的正整數(shù) b 和 x，求滿足條件的正整數(shù) n 的個數(shù): 要求對于 n，至少存在一個數(shù) d(n d b) 能整除 nx。(testcases 40, b 1012, x 60)令 k = nx/d

43、，有 k x， 固定 k，然后統(tǒng)計 n的數(shù)量，為了去重， 只統(tǒng)計不存在 k j x且 j|nx 的 n。k|nx 可以寫成 k/ (k, x)|n，于是可以寫成 n = m k/ (k, x) 從而統(tǒng)計對應的 m 的數(shù)量。根據(jù)題目約束可以得到一個 m 的上界 L。然后要把存在 j|n 的 m 給去掉。j|n 等價于 D(j)|m，其中 D 是一個僅關于 j, k, x 的式子。我們對于 k j 1 (d)/ordd(2)。接下來只要對L, R 內的奇數(shù)快速求出這個即可。先篩出 R 以內的質數(shù)， 然后用篩法可以得到L, R 內的所有質因數(shù)分解， 于是可以 DFS 得到所有約數(shù)?，F(xiàn)在要求 ord，

44、首先由 p, q 互質時 ordpq(a) = lcm(ordp(a), ordq(a)，于是只需要考慮模 pk 即可。將 (pk) 分解質因數(shù)，然后由 X = (pk) 開始不斷除以某個質因數(shù)直到不滿足 2X 1時停止，然后再對下一種質因數(shù)繼續(xù)除。最后剩下的 X 就是所求的階。時空復雜度空間 O(RL+ R)，時間 O( R+RL) log logR log R+(RL) log P )。試題OCT13 FN試題名稱Fibonacci Number題目大意算法數(shù)列 fn，求出一個最小的 n使得 fn c(modp)。(p 2 109，保證 5 是 p 的二次剩余)數(shù)列的通項公 式 為 fn=

45、(n ()n)/5，其中 = (1 + 5)/2。首先枚舉 n 的奇偶性，然后得到一個關于 n 的二次方程，求出 n 再用小步大步求出 n 即可。這個過程中需要求模意義下的平方根，可以使用 Cipolla 算法。時空復雜度空間 O(p)，時間 O(p)。6代數(shù)，F(xiàn)FT6.1AUG15 CLOWAYFuture of draughts試題試題名稱題目大意算法給 T圖，每個點數(shù) ni。首先將每個圖表示成鄰接矩陣。題中要求若干步后回到出發(fā)點，它的方案數(shù)對應的是矩陣的 trail。每次詢問：只考慮在 L, R 內的Ak圖，一開始在每個圖選定一個出發(fā)點，于是第一步需要求出每個矩陣 A 的若干次冪的 tr

46、ail：然后每次選擇一些圖（不能不選），把里面的點沿著邊動一下。如果所有圖對于 k n，求。對于 k 較大的情況，可以遞推。根據(jù) Caylay-Hamilton 定理可知道遞推式是矩陣的特征多項式。因此只需要求出特征多項式即可，一個方便的做法是給 x 代入幾個值算出行列式，然后用 Lagrange 插值。然后按照題意容斥，容斥的式子是一個類似二項式反演的東西，把組合數(shù)的分子分母拆出來就可以化成卷積的形式，然后用 FFT 即可。這里的模數(shù)不太舒服，可以先用 3 個支持 FFT 的里的點都回到出發(fā)點那么束。求在 k 次之內結束數(shù)。對 109 + 7 取模?？梢越Y的方案(n, T 50, k 104

47、, Q 2 105)模求出，然后用中國剩余定理合并。用正確的合并可以不爆 long long 也不需要浮點數(shù)?？臻g O(T 2k)，時間 O(T 2k log k + Tn4)。時空復雜度6.2FEB15 CUSTPRIMPayton numbers試題試題名稱題目大意定義三元組 (a, b, c) 的乘法，其中 c = 11 或 24：算法用一些特殊段可以得到如下結論：定義 (a, b, c) = (332ac)+(ba)，def multiply(a1,b1,c1), (a2,b2,c2): s = (a1a2 + b1b2 + c1c2) +其中 = (1 +11)/2。定義 Nx =

48、N (a+b) = a2 +ab +3b2。(a1b2t A(a1c2B(c1b2+=+=+b1a2) + (c1 + c2) floors/2 + 16(c1 + c2) (t - 2(a1b2 + b1a2) - c1a2) + 33(a1 + a2)+ (b1b2 - a1a2)(t - 5(a1b2 + b1a2) - b1c2) + 33(b1 + b2)則當 x 不是整數(shù)時，x 是質數(shù)當且僅當 Nx 是質數(shù)。當 x 是整數(shù)時，x 是質數(shù)當且僅當 x-c1c2質數(shù)且要么 |x| = 2 要么 |x| =11 且11 mod x 沒有二次剩余。接下來只需要對普通的整數(shù)進行質數(shù)判定就可以

49、了，這可以用 miller-rabin算法。+ (2b1b2 + 4a1a2)if s is even:return (A-540,B-540,24)else:return (A-533,B-533,11)給定一個三元組，求它是否為素數(shù)。(a, b 107, T 104)空間 O(1)，時間 O(T log a)。時空復雜度196.36.4AUG14 SIGFIBTeam Sigma and Fibonacci試題試題名稱題目大意算法6xyzf f f mod m求是。f根據(jù)案為數(shù)列的生成函數(shù)，容易推出所求答x y zix+y+z=N數(shù)。6x3(1 + x2)3n 1018,m 106Nx(1

50、 x x2)6它的系數(shù)可以寫成一個 12 階線性遞推數(shù)列?？梢杂媒浀涞?O(k2 log n) 做法來求（這里 k = 12，只要用乘除法即可）。但這樣跑不出 5 105 組數(shù)據(jù)。解決方法是對 m 200 左右的預處理，因為循環(huán)節(jié)很短。空間 O(1)，時間 O(log n)。時空復雜度6.520試題MARCH13 CHANGE 試題名稱Making Change題目大意算法n 種硬幣， 第 i 種面值 di， 硬幣無限多。要湊出 C 的總和總共有幾種方法模 109 + 7。di 兩兩互質。(n 50, c 10100, di 500)較復雜的一題。首先將的生成函數(shù)部分分式分解得到 1 = A(

51、x) + Bd(x) 1 xd(1 x)n1 + + xd1為求出 Bd(x)，將兩邊同乘 (1 + + xd1)，并用 d 1 個根代入。一個結論是 1 可以寫成 i 的多項式。所以可以變成 n1dd個多項式的卷積，且這個卷積能根據(jù)它的特殊形狀快速計算。然后 xi A(x) 是 i 的 n 1 次多項式。只要前 n 項就可以用(1x)n日公式算出第 C 項。時空復雜度空間 O(nd)，時間為 O(n2d)試題MARCH15 RNG試題名稱Random Number Generator題目大意算法對于一個 k 階線性遞推數(shù)列，求出第 n 項的值。模數(shù)可以FFT。(k 30000, n 1018

52、)這是一個經典問題。設初始值向量 X，轉移矩陣為 A，要求 AnX 的最末一行的值?？梢宰C明特征方程 f (x) 滿足 f (A) = 0。于是可以用多項式除法將 An 表為 Ak1, A0 的線性表示。由于 n 較大需要一邊倍增一邊除。時空復雜度空間 O(n)，時間 O(k log k log n)。6.6DEC13 REALSET Petya and Sequence試題試題名稱題目大意算法1 aixi，由輸入數(shù)組 a0, , an1，判斷它不斷令 f (x) =循環(huán)矩陣的0in秩等于 n deg右移所形成的循環(huán)矩陣是否是非奇異矩陣。(n 30000)(f (x), xn 1)，所以只需判

53、斷f (x) 是否被某個分圓多項式 d(x) 整除。d(xd/p 1)，因可以證明這等價于 x 1|f (x)此只需要相乘并取模即可，由于乘和除的式子都只有兩項，所以一次操作復雜度是線性的。時空復雜度空間 O(n)，時間 O(nd(n)。6.76.821試題OCT11 PARSIN試題名稱Sine Partition Function題目大意算法求值：sin(k1x) sin(kmx)k1+k2+km=n(t 10, m 30, n 109)令 f (n, m) 表示 ，而 g(n, m) 表示將原題求和式中最后一個 sin 換成 cos 后的 。那么根據(jù)一些三角恒等關系可以得到 g(0, 1

54、) = 1, g(n, m) = f (n, m 1) + cos xg(n 1, m) sin xf (n1, m), f (n, m) = f (n1, m) cos x+g(n 1, m) sin x。然后用矩陣乘法優(yōu)化這個 dp 即可。時空復雜度空間 O(m2)，時間 O(m3 log n)。試題JAN13 CUCUMBER 試題名稱Cucumber Boy and Cucumber Girl題目大意算法有 B 個 n n 矩陣 Q1, , QB。 對于每對 (a, b), 1 a b B，新矩陣 Ca,b 滿足Ca,bij = QaikQbjk1kn若有奇數(shù)個 n 排列 p，使得 C

55、a,bipi中至少有一個奇元素，那么 (a, b) 是好數(shù)對。求好數(shù)對個數(shù)。(n 60, b 8000)首先在矩陣的最后一列添上一列 1， 得到 b 個 n (n + 1) 矩陣 Ai。所需要求行列式的矩陣就是 AaAT 。b按照 Cauchy-Binet 將它的行列式寫成 n + 1 個矩陣的積的行列式之和，每個矩陣都是原來的矩陣去掉對應的那一列（如果是轉置就是去掉那一行）。于是只要對每個矩陣預處理出去掉任一列后的行列式即可。求行列式的話需要用 消元。這里是模 2 意義下，所以等價于判斷是否滿秩。每去掉一列都重新消元的做法太慢，一個快的做法是先對整個大的 n (n + 1) 矩陣消元，這樣會

56、多出不存在主元的某一列，然后稍微判一下就能知道去掉某一列后是否滿秩了。因為是在模 2 意義下運算，可用位運算 。時空復雜度空間 O(Bn2)，時間 O( 1 (B2n + Bn3)。646.96.106.1122試題AUG13 PRIMEDST試題名稱Prime Distance On Tree題目大意算法從樹上均勻隨機選出兩個結點，它們之間的距離是質數(shù)的概率是多少。(n 50000)只要統(tǒng)計出樹上每種長度的路徑有多少條即可，這是一個經典問題。點分治，在合并的信息時，發(fā)現(xiàn)其實是卷積的形式，于是用 FFT 統(tǒng)計即可。為了保證復雜度，需要按的最大深度從小到大處理。時空復雜度空間 O(n)，時間 O

57、(n log2 n)。試題JUNE11 CLONES試題名稱Attack of the Clones題目大意算法考慮所有 f : 0, 1n 0, 1 的函數(shù)的集合。集合 Z 是 0-preserving 的，集合 P 是 1-preserving 的，集合 D 是 self-dual的，集合 A 是 ane 函數(shù)。給定一個包含 Z, P, D, A 和 , , , 的表達式。求出得到的集合的元素個數(shù)。(n, length 100)首先對于 24 種情況（Z, P, D, A 分別是包含它還是不包含），分別算出這個集合中有多少個元素。這需要根據(jù)定義略加分析就能算出。然后就相當于一個 16 位二

58、進制數(shù)之間的運算了。剩下的就是一個經典的表達式求值問題了。做法是開一個數(shù)棧和一個運算符棧，遇到括號的時候注意調整優(yōu)先級。還要注意一下取補集運算是單目右結合的。時空復雜度空間 O(length)，時間 O(length + log n)。試題JULY11 YALOP試題名稱Trial of Doom題目大意算法一個 n m 的網格，每個格子一盞燈。從 (1, 1) 走到 (n, m)，每走一步，目標格子的燈以及它的四周的燈會改變狀態(tài)?，F(xiàn)在有 k 個亮燈，問能否全部熄滅。(1 n 40, 1 m 109, 1 k 10000)首先當 n, m 2 時，注意到在一個 2 2 的方格中 可以從一個頂點

59、走到另一個而不改變燈的狀態(tài)。所以 可以忽略路徑的限制，隨意的按開關。假如第一行的方案以確定，就可以從上往下貪心的按燈，如果最后一行能消光則是合法的。 可以算出中間的每個亮燈對于最后一行的貢獻，因為每行的長度很小，所以這個東西是會很快循環(huán)的。而且每個燈對最后一行的貢獻都是獨立的，可以疊加。然后再考慮第一行的方案，使得最后一行消完，這就可以用 消元解方程判斷是否有解了。如果是 n = 1 的情況，則需要考慮路徑的限制。注意到可以以 2 為步長不改變狀態(tài)地隨意跳，所以稍微分析一下奇偶性就可以了。時空復雜度空間 O(n senum)，時間 O(n senum + k + n2)。6.126.136.1

60、423試題JULY15 EASYEX試題名稱Easy exam題目大意算法一個面上寫著 1 K 的 ，擲 N 次后，令 ai 為點數(shù) i 的出現(xiàn)次數(shù)。求出 aF aF 的期望。1L（模質數(shù)意義下）(0 N, K 109, 0 F 1000, 0 L F 50000)如果記 bi 為第 i 次擲 得到的點數(shù)。那相當于從 b 數(shù)組中任抽取出一個有序 L F 元組 (bi1 , , biLF )， 考慮它滿足 bi1 = = biF = 1, biF +1 = = bi2F = 2, 的概率是多少， 對每個有序 L F 元組將這個概率求和，就是 。顯然若 bi 不同則 i 不同，于是可以分成 L 個