Problem - 566D - Codeforces題意： 給你 N 個人，初始時他們自己一個組。 Q 筆詢問，三種形式： 1 x y：merge( x, y ) 2 x y：merge( x, x + 1, ..., y ) 3 x y：print "YES" if group( x ) == group( y ) else "NO"制約： 1 ≤ N ≤ 2e5 1 ≤ Q ≤ 5e5解法： …

Problem - 609E - Codeforces題意： 給一張圖，分別問每一條邊必須被選擇時的最小生成樹花費是多少。制約： N, M ≤ 2e5解法： 找出原圖的最小生成樹後，做倍增 LCA，同時紀錄向上的瓶頸( 最大 )權值。指定的邊若在原本的生成樹，直接輸出當前最小花費，否則…

Round #23 (Div. 2 only)題意： 給一個長度 M 的排列 P，現在要做一個 N * M 的矩陣，第 i 行是 P^i( P )。 問 M 個列分別的數值總和為何。限制： 1 ≤ N, M ≤ 1e5解法： 顯然會形成一些循環，用 dfs 找出這些循環並記錄每個節點在每個循環中哪個位置，預處理…

Problem Description: You are given a string S. You want to find minimum length of string A, such that you could print S with A stamped on a paper arbitrary times. When making a new stamp, it is allowed to cover part of the string on the pa…

Problem - C - Codeforces題意： 給你一個數值矩陣。要你將數值塗改，使得最大的數字最小，但在：所有行，或所有列裡，原本數值的大小關係皆不改變。資料規模： The first line of the input contains two integers n and m (, the number of rows and the n…

No.416 旅行会社 - yukicoder題意： 給一個圖，和破壞邊的順序 ( 不一定會將所有橋破壞 )。對於所有大於 0 的節點，求哪一次破壞後無法從 0 達到。若一開始就不能到達，輸出 0，若破壞完依然能到達，輸出 -1。資料規模： 節點數 2≤N≤1e5 初始橋的數量 1≤M≤2e…

Problem - D - Codeforces題意： 給每個人的重量和權值。再給每對朋友的關係。x 和 y 屬於同個朋友圈，若存在一個序列 a[ 0 ], a[ 1 ], .. a[ i ]，滿足所有相鄰的人都是朋友。對於每個朋友圈，可以選一個人，或選所有的人，或都不選，邀請到派對。但是派對…

Problem - C - Codeforces題意： 給一個無向圖，保證任兩點之間至多存在一個路徑。接著若干比詢問，第一種詢問求某個點所在的連通塊裡的最遠距離( 直徑 )，第二種詢問須將兩個點所在的連通塊用最優方法，將一條邊兩端點分別連上兩連通塊中各一個點，使連接後…

Problem - 547b - Codeforces 題意： 給一組數列。對於 x for each 1 to N，輸出數列中，屬於連續 x 個元素構成的區間裡最小值的最大值。 解法： 由大的數字至小，每次將大的數字和左右的數字於並查集結構中，以位置為單位並在一起，若且為若左右的數比它本…

Problem - 277A - Codeforces 很顯然可以將每個人分別看成點，兩個不同分量若各自有一個人能說共同語言，就能把兩個分量所有點合併。假設所有人都會說至少一種語言，答案就是分量的數量減一。如果有人不會任何語言，那麼他們都必須學一種語言，所以得另外加…

Problem - D - Codeforces 顯然如果要從一個點到另一個點的路徑中最小權值最大，一定要沿著瓶頸生成樹走。圖裡的邊以兩端的最小值描述。很容易發現，越大的邊越有機會帶來影響，而某個邊有影響若且為若它是能將兩個無法相互到達的塊連通的邊裡邊權最大，並且…

Problem - 500B - Codeforces 如果某兩個數可以交換，那麼可以和那兩個數的任意一個交換的數同樣能和另一個交換，所以我們可以維護一個集合代表當前的位子可以用的數字有哪些。欲處理完就能貪心的由左到右依次選取集合中最小的。 #include <bits/stdc++.h> using namespace </bits/stdc++.h>…

1456 -- Supermarket 很顯然要從最貴的開始放，而且是放到離他期限最近的時間點。我們需要快速查詢 lastDay[ i ]，代表第 i天( 含 )之前最晚的還沒有賣東西的時間，又因為這件事可以指來指去 i.e. lastDay[ 5 ] = 3 AND lastDay[ 3 ] = 1 -> lastDay[ 5 ] = …

Problem - 371D - Codeforces 細節需要想一下下，怎麼快速存取下一個非滿的盤子的下標。 #include <bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 5; const int MAXA = 1e9 + 9; const int MAXM = 2e5 + 5; int n; int a[ MAXN ], f[ MAXN ]; int m; struct </bits/stdc++.h>…

1182 -- 食物链 這題解法我覺得很特別，是要維護哪些情報有相互證明的關係，哪些情報有相互排斥的關係，哪些情報沒有關係。這些都可以透過並查集的一些小技巧解決。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e6 + 4; const int MAXK = 1e5 + 5; in</bits/stdc++.h>…

1671. Anansi's Cobweb @ Timus Online Judge If we simulate it from the back instead, thinking the original edge destroying operation as adding, it will be possible to solve using elementary union find. #include <bits/stdc++.h> using namespace std; const i</bits/stdc++.h>…

C: オレンジグラフ / Orange Graph - MUJIN プログラミングチャレンジ Programming Challenge | AtCoder It is already a well known fact that not to include any odd cycle is equivalent to having the graph bipartite. Since N is small ( ≤ 16 ), we …

UVa Online Judge 用前綴和去想，若矩陣某個 ( i, j ) 為 +, 代表 pa( j ) - pa( i - 1 ) > 0, 同時意味著 pa( i - 1 ) ( j ) 建有向邊，最後的拓撲序就能是他們合法的大小關係。比較特別的是當pa( j ) - pa( i - 1 ) == 0 的時候，因為這代表 pa( j ) == pa…