Tutorial

Let's Learn Japnaese

首先，我們判斷結尾使否為 suru，如果是的話，則為サ行變格動詞。

否則的話，我們繼續判斷，如果結尾是 kuru，則為カ行變格動詞。

要注意，在判斷這兩項時，需確保字串長度是否 \(\geq 4\)。

接著，如果結尾是 eru 或 iru，則為上一段動詞或下一段動詞，兩者的變化方式是一樣的。

最後，若結尾是 u，則為五段動詞。

我們只須以相對應的方式對動詞進行變化即可。

Stonk in Stock Market

根據題目要求，用 for 迴圈讀進每天的股價後，在根據持有股息和當前股價決定是否能買股票，最後計算股票總價值加上股息是否大於起始金額即可。

Oshi no String

假設題目所要求的子字串長度為 \(l\)，我們可以利用雙指標找出對於每個 \(i\)，以第 \(i\) 個字母作為起點，則可以提取出的符合規則的子字串長度最長為多少。藉此來計算出 \(l\)。

同時，我們也能在藉此找到所有長度為 \(l\)，並且可能是題目所求子字串的子字串。

接著，我們只需要在這些候補子字串中找出字典序最小的即可。要做到這件事主要有兩種解法:

解法一：

令 \(T = SS\)， 接著對 \(T\) 建 suffix array，這樣便可以知道 \(s\) 的所有循環同構的字典序大小，從而找出候補子字串中字典序最小的一個。時間複雜度會是 suffix array 的建構，也就是 \(O(|S| log|S|)\)

解法二：

對 \(S\) 建構 hash 表格， 接著一一比較候補的子字串。比較的方式是 hash 加上二分搜來找出前綴相同的部份，再比較第一個不同的字母的大小。每次比較會是 \(O(log|S|)\)，需要被比較的子字串最多有 \(O(|S|)\)，因此時間複雜度同樣是 \(O(|S| log|S|)\)

Kessoku Band at Enoshima

Subtask 1

在沒有加入景點操作的情況下，我們可以考慮離線處理詢問。

先將詢問照 \(x\) 軸排序，接著考慮曼哈頓距離 \(|x_i - x_j| + |y_i - y_j|\) 有可能是以下 \(4\) 種狀況：

  • 狀況一： \((x_i + y_i) - (x_j + y_j)\) 若 \(x_i \geq x_j\), \(y_i \geq y_j\)
  • 狀況二： \((x_i - y_i) - (x_j - y_j)\) 若 \(x_i \geq x_j\), \(y_i \leq y_j\)
  • 狀況三： \((- x_i + y_i) - (- x_j + y_j)\) 若 \(x_i \leq x_j\), \(y_i \geq y_j\)
  • 狀況四： \((- x_i - y_i) - (- x_j - y_j)\) 若 \(x_i \leq x_j\), \(y_i \leq y_j\)

我們可以用四棵線段樹來分別維護這四種狀況的最短距離。我們對 \(y\) 的值域開線段樹，每個節點維護，對於所有 \(y\) 值落在這個區間的點，距離權值的最小值是多少。這邊的距離權值指的是在各個狀況中用來計算距離的值。舉例而言，在狀況一中，每個點的距離權值會是 \(x + y\)。

接著先只考慮狀況一，如果對於每個詢問 \((x_i, y_i)\)，找出狀況一下最近的點。我們只需要在狀況一的線段樹上詢問 \((-\infty, y_i]\) 區間中距離權值的最小值，在加上自己的距離權值 \(x_i + y_i\) 便可以達到答案。另外，可以發現到，如果我們以 \(x\) 座標的順序由小到大處理詢問，我們便可以好好地在正確的時間點把點加入狀況一的線段樹，從而維護其正確性。

既然我們可以好好處理狀況一的答案，那我們只需要重複同樣的演算法來計算另外三種狀況便可對於每個詢問都計算出正確的答案。時間複雜度會是所有排序以及線段樹操作所需的時間，也就是 \(O((n + m) log n + m log m)\)

Subtask 2

現在考慮加入景點的操作，我們沒辦法再任意改變詢問的順序。因此需要在線處理問題。

同樣考慮四個狀況分開處理，不過我們需要對 \(x\) 值域開線段樹，對於每個節點再使用資料結構維護對應的 \(y\) 值域資訊，不過這邊我們可以試著不要使用線段樹。

從上一個子題我們觀察到，與 \(y\) 值域有關的區間詢問都會是詢問某個前綴或後綴。因此我們能透過維護單調隊列來處理對 \(y\) 值域的詢問，可以使用 std::set 來完成。

時間複雜度會是所有在資料結構上的操作，也就是 \(O((n + m) log^2X)\)，其中 \(X\) 是值域範圍，可以發現 std::set 的點的數量都不超過 \(X\) 個。由於對 \(x\) 值域的詢問也會是某個前綴或後綴，我們可以用 fenwick tree 來取代線段樹，從而降低演算法的常數。

Select a repo