[solution] 2021-2022 ACM-ICPC Brazil Subregional Programming Contest

• [solution] 2021-2022 ACM-ICPC Brazil Subregional Programming Contest
  • pA
    • 題意
    • 測資範圍限制
    • 解法
    • 重新建模
    • 引入多項式
    • 選擇取樣點
  • pB
    • 題意
    • 題目範圍限制
  • 解法

pA

https://codeforces.com/gym/103388/problem/A

題意

給定有兩個正整數

$n$、

$R$，以及

$n$ 個數值

$p_i$。

代表有

$n$ 個人，第

$i$ 個人排名第

$i$（排名約低代表越好），要給所有人禮物，但是第

$i$ 個人至少要給

$p_i$ 個，而且排名比較好的人不能拿的比排名較差的人還要少的禮物，最多給

$R$ 個。

問有多少種分配的方法數，

$mod{10}^9+7$。

測資範圍限制

• $1\le n\le 5000$
• $1\le R\le {10}^9$
• $1\le p_i\le {10}^9$

解法

顯然的，若有

$p_i>R$，則答案為

$0$。

「因為排名比好的人不能拿的比排名較差的人還要少的禮物」，首先我們對

$p$ 反轉，再取前綴

$max$，最後補上

$R$，這方便我們之後的操作。

範例

舉例來說：

$$\begin{array}{rl}p& =[4,8,7,6,3]\\ & \Rightarrow [3,6,7,8,4]& \text{反轉整個陣列}\\ & \Rightarrow [3,6,7,8,8]& \text{取前綴 }max\\ & \Rightarrow [3,6,7,8,8,10]& \text{補上 }R\end{array}$$

待會都會用這個陣列舉例。

重新建模

我們現在將整道題目建模成另外一道題目：

從起點開始，只能往右邊或往上走，且不能走到灰色區域，問走到終點的方法數。

也就是說第

$i$ 的行，必須最少要走道

$p_i$。

我懶得寫灰色區域的定義，可以自己感受一下，反正跟上面的

$p$ 是相關的。

巧妙的是，因為有了灰色區域的限制，因此每一個走法中，對於每個

$x=i$，他最高的

$y$ 就是

$i$ 被分配到的禮物。

現在最大的問題就是要怎麼算這道問題的方法數，雖然可以用 dp 計算，舉體的轉移類似

$dp[i][j]=dp[i-1][j]+dp[i][j-1]$ 的算法算，但是可以發現

$p_i$ 跟

$R$ 都很大，根本無法這樣做。

---

引入多項式

實際上，上面的這個 dp 想法是好的，讓我們看看在上面的圖做 dp 的效果。

若我們從左到右一行一行看 dp 值，可以發現到後一行就是前一行的前綴和（要把跑到灰色區域的 dp 值刪除）。

現在要引入一些多項式的操作，我們讓每一行都可以用一個多項式表達，第

$i$ 行得到的多項式

$f_i(x)$，代入

$j$ 就會得到第

$i$ 行第

$j$ 列的值。

顯然的第 1 行是一個零次多項式，因為後面的行都是前面一行的前綴和，所以會是前面一行的最高項

$+1$ 次多項式（也就是說從左到右依序是

$0,1,2,\dots n$）次多項式。

拉格朗日差值法讓我們知道，給定

$N$ 個取樣點，就可以計算代表這些取樣點的多項式代入

$k$ 的值。現在我們的目標就是從我們知道的初始多項式，推到最後的

$n$ 次多項式，並計算

$f_n(R)$ 的值，就是答案了！

拉格朗日插值法

若給定

$n+1$ 個連續的

$x$ 的取樣點，則可以在

$O(n)$ 的時間計算

$k$ 在這

$n+1$ 個取樣點代表的

$n$ 次多項式代入的值。

這個的作法可以請讀者自己去搜尋。

我們不妨直接在最一開始就取

$n+1$ 個取樣點，但這

$n+1$ 個取樣點要怎麼取比較好呢？會不會跑到灰色區域？下一章節將對這些問題做補充。

---

選擇取樣點

首先我們會將第 1 行的取樣點推到第 2 行，並重複直到第 n 行。

並且選哪些數當取樣點根本不會影響答案（但是要是連續的，因為複雜度要求）！因此我們可以挑一些

$x$ 很大的點當取樣點，這樣它們就不會跑到灰色區域。假設我們一開始取的點

$x$ 座標在

$[{10}^9,{10}^9+n]$。

但是選擇那麼大的

$x$ 座標就會讓我們很難從第

$i$ 行推到第

$i+1$ 行，因為要計算第

$i+1$ 座標那麼高的取樣點，就要對整行做前綴和，這樣的時間複雜度無法接受。

用一張圖代表我們現在有的資訊：

其實不只這樣，我們還知道第

$i+1$ 行第

$p_i$ 列的值，因為他根本就跟第

$i$ 行第

$p_i$ 列的值一樣。

---

---

---

---

---

---

---

---

---

pB

https://codeforces.com/gym/103388/problem/B

題意

給定一個字串長度為

$N$ 的字串

$S$，跟

$M$ 個字串

$T_i$。

對於

$S$ 的每一種旋轉

$R_1,R_2,\dots ,R_N$，設

$V_i$ 為

$\underset{j\in [1,M]}{max}lcs(R_i,T_j)$，其中 lcs 是 longest common substring 的意思。

目標求

$\underset{i\in [1,N]}{min}{V}_i$。

題目範圍限制

• $1\le N\le {10}^5$
• $1\le M\le {10}^4$
• $\sum _{j\in [1,M]}|T_j|\le {10}^5$

防爆雷

防爆雷

防爆雷

防爆雷

防爆雷

防爆雷

防爆雷

防爆雷

防爆雷

防爆雷

防爆雷

防爆雷

防爆雷

防爆雷

解法

先來想想要如何算出一個

$va{l}_i$，我們可以令

$S=R_i{+}^{\prime }{\mathrm{\%}}^{\prime }+T_1{+}^{\prime }{\mathrm{\%}}^{\prime }+T_2+\dots +T_M$ 塞入 Suffix Array，用 這題 的作法。

但這樣就需要

$O(N|S|\log |S|)$，顯然不夠快。

---

題目要求旋轉字串，不難想到將字串串成兩份相接的技巧，令

$P=S+S$。我們會希望可以一次計算所有

$V_i$。

首先，答案的值是否小於等於某個值

$x$ 具有單調性，觀察到這點之後不難想到二分搜。暫且讓我們定義 check(mid) 代表「是否存在一種旋轉

$R_i$，使得

$V_i$ 至多為

$mid$」

接著我們想要一次處理所有旋轉，因此可以設

$P=S+S$，這樣

$P$ 的每個長度為

$N$ 的字串都代表其中一個

$R_i$。這樣 check(mid) 就變成「在

$P$ 中找到一個長度為

$N$ 的子字串，使得他對應到的

$V_i$ 至多為

$mid$」。接下來的說明都會圍繞在這個問題上。

因為 check(mid) 有「至多」這個限制，因此對於所有

$1\le i\le 2N$，我們會想知道

$P[i\dots |P|-1]$，與所有

$T_j$ 的 LCS 最長是多少，並且這個 LCS 必須是從

$P[i]$ 作為開頭，這樣我們在選取長度為

$N$ 的子字串時，就可以避開一些不可選的字元，讓我們看下面的範例：

承上文，我們要選擇一個長度為

$N$ 的子字串，那麼：

• 我們知道從
  $P[1...8]$ 可以找的最大 LCS 且從
  $P[1]$ 開始的長度為
  $4$，但是因為
  $mid=3$，因此可知如果要選
  $P[1]$ 這個字元，則不則選到
  $P[4]$ 之後的字元。
• 我們知道從
  $P[4...8]$ 可以找到的最大 LCS 且從
  $P[4]$ 開始的長度為
  $2$，也就是說如果選到
  $P[6]$，那麼選到
  $P[8]$ 以後的字元都是沒關係的，因為不會違反 LCS 至多是
  $mid$ 的限制。

根據上面的推論，我們知道對於

$P$ 中的每個字元，我們都可以找到一個右界

$boun{d}_i$，代表如果選了

$P[i]$ 這個字元，則只能選到

$boun{d}_i$ 這個字元以內。

現在，我們希望找到一個長度為

$N$ 的區間

$[i,i+N-1]$，

$\underset{j\in [i,i+N-1]}{min}boun{d}_j\ge i+N-1$。這件事情可以輕鬆用

$O(n)$ 找到，就留給讀者自行思考了。

整個作為為

$O(\log n)$ 的二分搜乘上，

---

---

---

---

---

---

---

---

---