c424. pC 框架區間
Tags :
Accepted rate : 83人/117人 ( 71% ) [非即時]
評分方式:
Tolerant

最近更新 : 2017-12-06 23:56

Content

基因是含有特定遺傳信息的結構,用來決定生物的種性特徵。

生物學家發現,與特定功能相關的一群基因在基因序列上的位置通常十分靠近, 因此在基因序列中的連續片段被認為是有意義的。

一個包含 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), 共四個。

Input

第一行有一整數 T,代表有 T 組測試資料。

接下來每兩行用來描述一組基因序列,
第一行有一整數 n, 第二行有 n 個整數 s1, s2, ..., sn (數字之間以一個空白隔開),

代表基因序列 S = (s1, s2, ..., sn), 任兩個數字都不相同且1 <= s1, s2, ..., sn <= n。

Output

針對所輸入的基因序列 S,輸出一個數字,代表有多少數對 (a, b), 1 <= a < b <= n, 是一個框架區間?

Sample Input #1
輸入範例 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
Sample Output #1
輸出範例 1:
0
3
4

輸出範例 2:
4
9
測資資訊:
記憶體限制: 128 MB
不公開 測資點#0 (30%): 10.0s , <1M
不公開 測資點#1 (10%): 10.0s , <1M
不公開 測資點#2 (10%): 10.0s , <1M
不公開 測資點#3 (10%): 10.0s , <1M
不公開 測資點#4 (40%): 10.0s , <1M
Hint :
本題共有三組測試資料。每組可有多個輸入檔案,全部答對該組才得分。
第一組 30 分,所有的測資 T <= 20、1 <= n <= 100。
第二組 30 分,所有的測資 T <= 6、1 <= n <= 3000。
第三組 40 分,所有的測資 T <= 20、1 <= n <= 5000。
Tags:
出處:
104學年度全國資訊學科能力競賽 [管理者: andy89923 (CTFang) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」