A. 威廉伯爵的農場

題目大意

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

題解

Keys :

  • 向量運算
  • 數值處理

高中數學有提到,兩向量 ab,圍成的平行四邊形面積是 |a×b|,所以這一題的答案就是 12×c×|a×b|,其中 |a×b|=|xaybyaxb|,此外要注意除以 2 的次序避免溢位的問題。

B. ⼤樓彩繪

題目大意

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

題解

Keys :

  • 排列組合
  • Burnside’s lemma
  • 快速冪

一個很顯然的事情是一個面有 cn2 種不同的塗法,這個數字姑且稱為 p ,那如何計算有多少的塗法呢?

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

1mi=1mpgcd(m,i)

C. 金坷垃運輸網

題目大意

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

題解

Keys :

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

D. 金金金坷垃

題目大意

排一個大小是 n 的「金」

題解

Keys :

  • IO

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

E. 農業基地的密碼

題目大意

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

題解

Keys :

  • 後綴數組 Suffix Array
BWT[i]={T[SA[i]1],if SA[i]>1$otherwise

F. 我們的金坷垃

題目大意

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

題解

Keys :

  • DP
  • 解答回朔