題目連結 題目大意給定一棵樹，樹上的每個節點有兩個數字 $A_i, B_i$。每經過節點時，可以從節點上的兩個數字任意拿走一個。對於 $v = 2, \dots N$，求從 $1$ 走到 $v$ 的最短路徑上，最多可以拿到幾種相異的數字？ $2 \leq N \leq 2 \cdot 10^5$ $1 \leq A_i, B_i \leq N$ 觀察這題是本題的簡單版本，也就是當樹是一條鏈的情

基本概念有些題目要求進行 $k$ 次操作的最大/最小值。我們開心的列出 $dp[i][j]$ 為前 $i$ 個東西進行 $j$ 次操作的最大值，答案就是 $dp[n][k]$，但很不幸的 $O(nk)$ 會超時，這時候我們或許能套用 Aliens 優化。 Definition. $f(k)$ 為進行 $k$ 次操作的最大值。 $f$ 必須是一個凹函數 (concave function) 才能套用

題目連結 題目大意給定一個長度為 $n$ 的數列 $a$，求： $$\sum_{i = 0}^{n - 1} \sum_{j = i + 1}^{n - 1} \sum_{k = j + 1}^{n - 1} [\gcd(\min(a_i, a_j, a_k), \max(a_i, a_j, a_k)) = 1]$$ 其中 $[P]$ 是艾佛森括號。 $3 \leq n \leq 3 \cdot

題目連結 題目大意給定一個長度為 $n$ 由 $\text{‘0’, ‘1’}$ 組成的字串 $S$，對於 $k = 1, \dots, n - 1$，求出有幾組 $i, j$ 滿足 $i - j = k$ 且 $S_i = S_j = \text{‘1’}$。 $2 \leq n \leq 2 \cdot 10^5$ 題解先將字串轉換成多項式的形式表示 ($\text{“10011”} \t

題目連結 前言NPSC 是我參加的第一場比賽，理所當然的被打爆，只解出最水的 pB。當時跟隊友花了很多時間在解這題，但是由於數學知識不足，都在原地打轉。最近剛好翻到這題，想說花點時間想一下，馬上就有了突破，也順利 AC，算是彌補了當時的遺憾。 題目敘述有 $n$ 個人要分組，一組 $x$ 個人，編號 $1$ 到 $x$ 的人會分到一組，$(x + 1)$ 到 $2x$ 會分到一組，依此類推。最後可

前言這次在賽後補完了 F、G、H，覺得題目不錯，所以來寫個題解吧 A - 2^N直接乘以 $n$ 次，或是使用 $<<$ 的位元運算。 時間複雜度：$O(n)$ 或 $O(1)$ Solution Code B - Batters從索引比較高的往回更新。 時間複雜度：$O(n)$ Solution Code C - Filling 3x3 array枚舉左上角四格的所有組合，並判斷剩下