A. 威廉伯爵的農場

題目大意

給平面座標的三個點，問圍成的三角形面積乘以一個常數 $c$ ，所有數字都是 int 範圍的整數， $c$ 是 2 的倍數，保證答案可以用 long long 表示

題解

Keys :

向量運算
數值處理

高中數學有提到，兩向量 $\vec{a}$ 、 $\vec{b}$ ，圍成的平行四邊形面積是 $| \vec{a} \times \vec{b} |$ ，所以這一題的答案就是 $\frac{1}{2} \times c \times | \vec{a} \times \vec{b} |$ ，其中 $| \vec{a} \times \vec{b} | = | x_{a} y_{b} - y_{a} x_{b} |$ ，此外要注意除以 2 的次序避免溢位的問題。

B. ⼤樓彩繪

題目大意

有 $m$ 角柱，角柱的側邊每個面都有 $n \times n$ 的網格，每個網格有 $c$ 種顏色可以選擇，問有幾種著色方法

題解

Keys :

排列組合
Burnside’s lemma
快速冪

一個很顯然的事情是一個面有 $c^{n^{2}}$ 種不同的塗法，這個數字姑且稱為 $p$ ，那如何計算有多少的塗法呢？

如果知道 Burnside’s lemma 的話就有

\frac{1}{m} \sum_{i = 1}^{m} p^{\gcd (m, i)}

C. 金坷垃運輸網

題目大意

給一張無向圖，問 $a$ 、 $b$ 兩點之間是否存在兩個獨立的路徑，即如果任意地把圖中的一條邊移除， $a$ 、 $b$ 依舊連通

題解

Keys :

Tarjan’s algorithm for Bridge
橋連通分量 BCC

D. 金金金坷垃

題目大意

排一個大小是 $n$ 的「金」

題解

Keys :

會寫星星樹就會這題了吧？

E. 農業基地的密碼

題目大意

請輸出一個字串的 Burrows-Wheeler 變換。

題解

Keys :

後綴數組 Suffix Array

B W T [i] = {\begin{cases} T [S A [i] - 1], & if S A [i] > 1 \\ $ & otherwise \end{cases}

F. 我們的金坷垃

題目大意

請輸出一個字串最短補成回文的字串中，第 $k$ 大的解

題解

Keys :

DP
解答回朔