題意:給定平面上 n 個人座標,每人開一槍,求所有人聽到槍聲次數的可能不同值個數。
解法:O(n^2) 枚舉所有點對,計算距離平方,存入陣列,排序去重,輸出唯一值個數。n ≤ 1000 可行。
題意:給定兩個日期,求其間閏日 (2月29日) 的個數。
解法:利用除法計算閏年數。將起始日期調整:若在 1/1~2/29 之前則年份不變,否則年份+1;結束日期若在 2/29 之前則年份-1。然後用 y/4 - y/100 + y/400 計算區間閏年數。O(1) 每查詢。
題意:n 個人,每人恰好轉發郵件給另一人(形成函數圖)。求從誰開始轉發能到達最多人(鏈長最長),輸出該起始人編號(最小)。
解法:DFS + 記憶化。對每個未訪問節點 DFS,檢測環並計算路徑長度。利用 vis[] 標記全局訪問,dp[u] 存從 u 出發能到達的人數。環上節點 dp 值為環大小;樹枝節點 dp = 1 + dp[next]。最後掃描最大 dp 值對應的最小編號。
int dfs(int u) {
if (vis[u]) return dp[u];
vis[u] = 1;
int v = nxt[u];
if (!vis[v]) dp[u] = dfs(v) + 1;
else dp[u] = 1; // 環內處理需額外邏輯
return dp[u];
}
// 完整代碼需處理環檢測與環長度計算