LFsWang's World

連結：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; ...

連結：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 ...

連結：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 個房間時， ...

心得 平日練習隨意寫的 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