基因是含有特定遺傳信息的結構,用來決定生物的種性特徵。
生物學家發現,與特定功能相關的一群基因在基因序列上的位置通常十分靠近, 因此在基因序列中的連續片段被認為是有意義的。
一個包含 n 個基因的序列可以用 {1, 2, ..., n} 所組成的排列 S= (s1, s2, ..., sn) 來表示。
為了預測基因序列 S 上可能有意義的片段,一位生物學家遭遇了下列問題。
令 F(a, b) 代表在基因序列 S 上位置落在基因 a 和基因 b 之間的所有整數所構成的集合 (含 a 和 b)。
例如,令 S = (2, 7, 6, 4, 14, 13, 5, 8, 1, 9, 11, 10, 12, 3),
則 F(6, 8) = F(8, 6) = {6, 4, 14, 13, 5, 8}。
令 I(a, b) 代表數線上 a 和 b 這兩個整數間所有整數所構成的集合 (含 a 和 b)。
例如,I(6, 8) = I(8, 6) = {6, 7, 8}。在基因序列 S上如果兩個整數 a 和 b , 1 <= a < b <= n,
滿足 F(a, b) = I(a, b) 則稱 (a, b) 構成一個「框架區間」 (framed interval)。
舉例來說, 考慮基因序列 S = (2, 7, 6, 4, 14, 13, 5, 8, 1, 9,11, 10, 12, 3), 以 (a, b) = (9, 12) 為例,
因為 F(9, 12) = {9, 11, 10, 12} = {9, 10, 11, 12}= I(9, 12),所以 (9, 12) 是一個框架區間。
相同的 (6, 7)、(10, 11) 和 (13, 14) 也是框架區間。
這位生物學家想知道給定一個基因序列 S,有多少數對 (a, b) , 1 <= a < b <= n, 是一個框架區間?
例如,在基因序列 S = (2, 1, 5, 4, 3) 上,是框架區間的數對 (a, b) ,1 <= a < b <= 5,
有 (1, 2)、(3, 4)、(3, 5) 和 (4, 5), 共四個。
第一行有一整數 T,代表有 T 組測試資料。
接下來每兩行用來描述一組基因序列,
第一行有一整數 n, 第二行有 n 個整數 s1, s2, ..., sn (數字之間以一個空白隔開),
代表基因序列 S = (s1, s2, ..., sn), 任兩個數字都不相同且1 <= s1, s2, ..., sn <= n。
針對所輸入的基因序列 S,輸出一個數字,代表有多少數對 (a, b), 1 <= a < b <= n, 是一個框架區間?
輸入範例 1: 3 4 3 1 4 2 4 3 2 1 4 5 2 1 5 4 3 輸入範例 2: 2 14 2 7 6 4 14 13 5 8 1 9 11 10 12 3 11 3 10 4 5 6 8 7 9 11 2 1
輸出範例 1: 0 3 4 輸出範例 2: 4 9
本題共有三組測試資料。每組可有多個輸入檔案,全部答對該組才得分。
第一組 30 分,所有的測資 T <= 20、1 <= n <= 100。
第二組 30 分,所有的測資 T <= 6、1 <= n <= 3000。
第三組 40 分,所有的測資 T <= 20、1 <= n <= 5000。
ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」
|