$$\newcommand{\Ord}{\mathcal{O}}$$

2018 臺南一中上學期資訊學科能力競賽校內複選題解

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_ay_b-y_ax_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^{\operatorname{gcd}(m,i)}$$

C. 金坷垃運輸網

題目大意

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

題解

Keys :

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

D. 金金金坷垃

題目大意

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

題解

Keys :

  • IO

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

E. 農業基地的密碼

題目大意

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

題解

Keys :

  • 後綴數組 Suffix Array

$BWT[i]=\begin{cases}T[SA[i]-1], & \text{if }SA[i]>1\\\$&\text{otherwise}\end{cases}$

F. 我們的金坷垃

題目大意

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

題解

Keys :

  • DP
  • 解答回朔