Graph
Problem - 794D - Codeforces題意: 有 N 個城市,M 條路。如果存在,輸出一個方案,為每個城市 u 分配一個數字 X[ u ],使得 abs( X[ u ] - X[ v ] ) ≤ 1 若且唯若 u, v 相鄰。制約: N, M ≤ 3e5解法: 首先考慮這樣的一對城市 ( u, v ):它們的鄰接陣列,…
Problem - D - Codeforces題意: 有 N 個城市,每對城市之間存在一個雙向路徑,每一條邊有一個死亡值 P。 一個路徑的死亡值是整條路徑上的邊的死亡值中的最小值。 對於每個城市 x,問一種方法,使得每個點對外都只留下一個有向邊,使得所有城市都會到達城市 …
Round #25 (Div. 2 only)題意: 給一個 01 矩陣 A[ N ][ M ]。你可以選擇一個 0 轉為 1,轉換後,所有不和任意一個邊界的 0 屬於同一個連通塊 ( 上下左右,且兩者皆 0 視為相鄰 ) 的所有 0 都會轉為 1。問最多可以有多少 1。制約: 1 ≤ N, M ≤ 1000解法: 將…
Problem - C - Codeforces題意: 給一個圖,要求放 K 個機器人並給出每個機器人的路徑,路徑長至多為 ceil( 2 * N / K ),使得所有節點都被至少一個機器人拜訪過。資料規模: N, M ≤ 2e5解法: 首先把圖轉換成任意一個生成樹。接著進行類似時間戳記的 DFS,…
Problem - 228E - Codeforces題意: 給 N 個點 M 條邊,邊有邊權 0 或 1。每次操作選取一個點,將和此點連接的所有邊的權值反轉。問存不存在一種反轉方式可以讓所有邊的邊權變為 1,若有則輸出方案。資料規模: N ≤ 100 解法: 考慮每個邊,其實只能被兩端點…
Problem - 11D - Codeforces題意: 給一個無向圖。問有多少個簡單環 ( 無重複經過的點的環 )。資料規模: N ≤ 19 TL: 2000 ms解法: 考慮一個環,選定一個點 ( 這裡用編號最小的點 ) 切開之後變成一條鍊,假設原本是 abcd 這樣的環,那其實可以用點的集合和…
Problem - D - Codeforces題意: 給 K,求一個無向圖鄰接矩陣,使得節點 1 到節點 2 的最短路徑恰有 K 個。資料規模: 1 ≤ K ≤ 1e9 輸出的圖的節點數 ≤ 1000解法: 考慮二進制枚舉,需要 *2 就往右連一個菱形,需要 +1 就從節點 1 連到當前的終點。 #include <bits/stdc++.h></bits/stdc++.h>…
3866 -- Exclusive Access 2題意: 給一個 N 個無向邊的圖。求一種方案使所有邊定向,並有最短的最長路徑 ( 即不存在環 )。無法到達的點對之間的路徑長不須考慮。資料規模: N ≤ 100 節點為 [ L, Z ] 間的大寫英文字母,數量不超過 15。 TL: 5000 ms ML: 655…
Problem - 645D - Codeforces題意: 有 N 個機器人打鬥,機器人之間勝負是依戰鬥力的大小關係定的,而所有機器人的戰鬥力相異。依順序給機器人編號 u[ i ], v[ i ],表示編號 u[ i ] 的機器人戰鬥力比 v[ i ] 的機器人高。求第幾個資訊開始能確定所有機器人…
D: 連結 / Connectivity - AtCoder Regular Contest 065 | AtCoder題意: 給相同節點數的兩個圖,對於每個點,求有多少點和它在兩個圖上都屬於相同的連通分量。資料規模: 節點數 2≦N≦2e5 兩個圖分別邊數 1≦K,L≦1e5 保證同一個圖不存在重邊 時限 2000 ms 記…
Problem - E - Codeforces題意: 在一個圓桌上吃飯,有兩種飯,希望每連續三個人,都一定有一個人吃不一樣的東西。每個人都有一個唯一對應的伴侶,而伴侶之間也規定不能吃一樣的東西。求合法分配的結果。若無法分配,輸出 -1。資料規模: 情侶對數 1 ≤ n ≤ 1…
Problem - B - Codeforces題意: 給一個圖,邊用四個值表示,( x, y, Cxy, Cyx ),代表 x 至 y 長度是 Cxy,y 至 x 長度是 Cyx。求是否存在一個正環,若存在則輸出最小環的長度。資料規模: 節點數 1 ≤ N ≤ 300 邊數 0 ≤ M ≤ N * ( N - 1 ) / 2 權值 -1e4 ≤ …
Problem - E - Codeforces題意: 給一張帶權有向圖。求最長路徑長度,路徑滿足邊權嚴格遞增。數據範圍: 節點 2 ≤ N ≤ 3e5 邊數 1 ≤ M ≤ min( N * ( N - 1 ) / 2, 3e5 ) 邊權 1 ≤ W[ i ] ≤ 1e5 保證無自環,無重邊。解法: 先考慮將邊權小至大排序。此時發現…
Problem - D - Codeforces Edges are all weighted 1, so we can apply BFS for single source shortest path, for each node as source. This allows us to get all pairwise distances in O( n ^ 2 ). Since we are to find the maximum distance of path …
Dashboard - Round 1A 2016 - Google Code Jam There are two possible ways to form a maximum cycle: 1. Sum up for each pair ( u, v ) that share bidirectional edges, length of chain that starts with u, and v, such like f[ f[ .. f[ v ] ] ] u ->…
Problem - D - Codeforces First we will have to take away apparently wrong cases, where dis[ i ][ i ] != 0 or dis[ i ][ j ] == 0 for i != j, or if dis[ i ][ j ] != dis[ j ][ i ]. We will find that we are willing to make a tree, so the short…
Problem - 25C - Codeforces 先做完一次MSSP之後,對於每個動態操作可以直接詢問每個兩端,是否用了這條邊之後會更好。 注意題目是說額外新增路,所以是不一定要取的。 #include <bits/stdc++.h> using namespace std; const int MAXN = 300 + 3; const int MAXK = 300 + 3;</bits/stdc++.h>…
Problem - B - Codeforces 如果順著做,逐一破壞。。嗯,看到逐一破壞就可以開始想反著觀察就是逐一增加了。 因為問題是Multiple Source Shortest Path,所以可以馬上想到Floyd Warshall演算法了。 想起以前學長和我提過,為什麼三層迴圈的中繼點要在最外圈…
Problem - 20C - Codeforces 根本裸題。。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int MAXM = 1e5 + 5; const int MAXW = 1e6 + 6; typedef long long ll; typedef pair< int, int > pii; typedef pair< ll, int > pli; int n, m;</bits/stdc++.h>…
Problem - C - Codeforces 基本上和這道題是相同的概念 CFR 219 D. Choosing Capital for Treeland ( Tree DP ) - 0w1 不過這題的要點在於意識到樹的唯一路徑性質使得選擇任一條邊後兩端一定可以各自形成一顆子樹。因此只要枚舉所有邊,再各自處理所有情況就…
Problem - D - Codeforces 搞了很久才弄出來。。首先要分成兩種邊,一種是順向邊,輸入給定的邊,一種是逆向邊,就是要經過反轉才能用的邊。這麼一來,我們可以先透過一次深搜得到隨便一個點當根的時候的花費。顯然我們不能暴力對所有根重新計算,但我們可以…
Problem - 429A - Codeforces It is obvious that if all nodes above are cleared and the current node is not the target, it has to be flipped. It is never better to flip its ancestors, for it will cost extra for nothing. We don't have to go d…
Dashboard - Round 1A 2014 - Google Code Jam 題目中一個合法的完全樹的定義是,所有節點的子節點數為0或2。要求的是移除最少點使得給定的樹成為完全樹。因為數據範圍小,可以考慮枚舉每個節點作為根,再做一次線性的深搜處理。根據定義可以得到遞迴函數,…
Problem - C - Codeforces WA了一次,以為只會原地待著,或往上或往右或往右上移動。仔細想想,這全部方向都得考慮。 #include <bits/stdc++.h> using namespace std; const int MAXH = 8 + 2; const int MAXW = 8 + 2; typedef pair< int, int > pii; char G[ MAXH ][ MAXW</bits/stdc++.h>…
Problem - B - Codeforces 把度數和邊的變量維護好就很簡單。 #include <bits/stdc++.h> using namespace std; const int MAXN = 100 + 2; const int MAXM = MAXN * MAXN / 2; int n, m; vector< int > G[ MAXN ]; int deg[ MAXN ], d_deg[ MAXN ]; void solve(){ int cnt =</bits/stdc++.h>…
Problem - 131D - Codeforces n個點 n條邊保證聯通,俗稱的水母圖。題目求的是每個點與環的距離,所以用一次 dfs求環,利用 next數組就能夠紀錄並判環。最後再把所有環裡的點拿去做bfs求距離。 #include <bits/stdc++.h> using namespace std; const int MAXN = 3e3 + 3; in</bits/stdc++.h>…
Problem - E - Codeforces 点が全て連結する場合を考えて、辺の数だけ degree = 1の点の数ができるとわかる。つまり、連結成分それぞれについてそれを求めればいい。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int MAXM = 1e5 + 5; t</bits/stdc++.h>…
Problem - 404C - Codeforces The vertex i with dis[ i ] = 0 will be the origin, and if it doesn't exist, or multiple 0 distance vertices exist, there will be no solution. Otherwise iterate through all distances from smaller to larger and ex…
Problem - E - Codeforces The deterministic solution for this problem is quite difficult. However, it is easy to come up with a randomised algorithm. There are primarily 2 types of randomised algorithms, Monte Carlo that runs in a certain t…
Problem - 330B - Codeforces There are n vertices and at most n / 2 - 1 edges. Easy to see that there will be at least one vertex with 0 degree. #include <bits/stdc++.h> using namespace std; const int MAXN = 1e3 + 3; const int MAXM = MAXN / 2; int n, m; i</bits/stdc++.h>…