Subscribed unsubscribe Subscribe Subscribe

0w1

Hi everyone, please feel free to have discussions with me!

CFR 767 C. Garland ( Tree DP )

Problem - C - Codeforces題意: 給一棵節點帶權的樹。問是否存在一種分割方法,使得可以分成三個非空子樹,使得權重總和相同。輸出方案。資料規模: The first line contains single integer n (3 ≤ n ≤ 1e6) — the number of lamps in the garland. Then n…

CFR 781 C. Underground Lab ( Ad hoc, Time Stamp, DFS )

Problem - C - Codeforces題意: 給一個圖,要求放 K 個機器人並給出每個機器人的路徑,路徑長至多為 ceil( 2 * N / K ),使得所有節點都被至少一個機器人拜訪過。資料規模: N, M ≤ 2e5解法: 首先把圖轉換成任意一個生成樹。接著進行類似時間戳記的 DFS,…

CFR 781 A. Andryusha and Colored Balloons ( Greedy, DFS )

Problem - A - Codeforces題意: 給一棵 N 個節點的樹,要求給每個節點著色,滿足所有長度為 2 的路徑裡的三個節點都異色。問最少顏色數量。資料規模: N ≤ 2e5解法: 隨便找一個節點當作根,轉為有根樹上的問題。遞迴拜訪一個節點之前先為該節點著色。在當…

POI 2 Stage 3 Step Traversing a Tree ( DFS )

http://main.edu.pl/en/archive/oi/2/obc題意: 給一棵樹,求一個序列,可以不重複拜訪所有節點,而且相鄰節點距離不超過 3。資料規模: In the first line of the standard input there is a positive integer n, not greater than 5000 - it is the number…

POI 2 Stage 1 Trees ( DFS )

http://main.edu.pl/en/archive/oi/2/drz題意: 這裡限制樹的每個節點的兒節點必須是 0 或者 2,否則不稱做樹。 給編號由小到大的葉節點的深度,求樹是否存在,存在的話輸出每個節點的父節點編號,以及樹的括號序列表示。資料規模: In the first line of th…

IOICJ 77 Lowest Common Ancestor ( DFS )

Problem Description: Node 1 denotes the root of the tree. You are given the parent nodes of 2 ~ N. Count for all v the number of ordered pairs such that their LCA is v. Constraints: 1≤T≤100 2≤n≤100000 1≤pi vvi G; vl ans; vi size; void dfs(…