1214. 樹論 之 樹同構測試
連結:https://tioj.ck.tp.edu.tw/problems/1214
題目大意
判斷兩棵樹是否同構
題解
如果兩棵樹是一樣的,那可以先將樹上唯二的重心、或直徑中點找出來,那就可以一個相同的點,然後再比對樹的最小括號表示法即可完成題目要求。
AC Code
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495#include<bits/stdc++.h>using namespace std;vector<int> V[100];int far,far2;int dist=0;void dfs(int v, int fa, int d){ if( d > dist ){ far=v; ...
1210. 圖論 之 簡單圖測試
連結:https://tioj.ck.tp.edu.tw/problems/1210
題目大意
給定一個度序列,問這個度序列是否能構成一張簡單圖?
題解
最近恰好讀了圖論的書,若一個度序列可以構造出一個簡單圖,該序列又可稱為圖序列,利用度序列判定是否為簡單圖(無自環、重邊)在這本書【演算法觀點的圖論】第一章就有提到了,有兩個定理可以使用:
Erdős–Gallai theorem
若度序列 d:d1≥d2≥…dn 是圖序列 ⟺ ∑d 是偶數,且對於 1≤k≤n 都有
∑i=1kdi≤k(k−1)+∑j=k+1nmin{k,dj}
Havel–Hakimi algorithm
對於 n≥2,若度序列 d:d1≥d2≥…dn 是圖序列 ⟺
d′:d2−1,d3−1,…,d1+d1−1,d2+d1,d2+d1,…,dn也是圖序列
可以發現第二個方法比較好實作,就是把度數最大的點,都接一條邊到度數較多的邊上。由於數字都是整數,可以利用 Counting Sort 或是一些技巧,就能在 O(V) 的時間判定是否為簡單圖了。
AC Code
1234567891011121314151617 ...
1201. 消逝於黃昏中的風
連結:https://tioj.ck.tp.edu.tw/problems/1201
題目大意
直線上有 K 個房間,每個房間要不就是社團的人,要不就是怪人(沒社團的人),任兩怪人之間要相隔 $M個房間,已知有 N 種不同的社團,總共有幾種,問有幾種合法的人員放置方法,取除以 P 的餘數。
題解
一開始想到數學解,由枚舉怪人的數量,再把方法數加起來,如果現在有 S 位怪人,顯然要滿足:
K≥(S+(S−1)×M)
K≥S+N
可以先讓所有人以最緊密的方法排列進去,第一個是怪人,再下 M 個空房間,然後再一個怪人,以此類推。最後會剩下 K−(S+(S−1)×M) 間自由擺放的房間,數量用 L 表示。根據排列組合,L 個相同物有 S+1 個相異位置可放入,共有 (L+SL) 種方法,故總方法數是 ∑(L+SL)×NK−S,因為不能保證 P 是質數,硬幹 Cmn 複雜度過高,化簡 C 找通項DP化很麻煩,因此該方法不太合適。
如果是排組問題,可以考慮回到DP的基本想法,因為怪人的數量是任意多的,前面的怪人數量不影響答案,因此狀態可以如無限背包問題一樣,設 dp[i]= 有 i 個房間時, ...
Educational Codeforces Round 46
心得
平日練習隨意寫的
A
水題,略
B
水題,略
C. Covered Points Count
AC code
利用掃描線的概念,按照 x 軸順序排序,將事件排好記數即可。
D. Yet Another Problem On a Subsequence
AC code
可以利用動態規劃(DP)來計算答案,若子序列 p 是合法的,則將 p 的第一個 good array 去掉後剩餘的部分也是合法的,假定 dp[i] 表示子序列開頭在第 i 項時,有多少數列滿足題目的條件,若 ai≤0,則答案為 0,否則,可以在第 i 項後的 j 個數字任意挑 ai 個數字,挑完後在乘上 d[j+1],為剩下的部分有多少合法序列。最後的答案即為 dp 陣列的總和。
dp[i]={1i=N+1∑j=i+ain(ji)dp[j+1]otherwiseE. We Need More Bosses
F
G