回分類題庫
e027: 3.框架區間
關鍵字: 104學年度全國決賽

測資點 : 6 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 35 Times / 29 Users | Submit : 93 Times / 34 Users | Accepted rate : 85%
題目加入時間 : 2016-11-17 13:46

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 (1 <= T <= 20),代表有 T 組測試資料。

接下來每兩行用來描述一組基因序列,第一行有一整數 n (1 <= n <= 5000),第二行有 n 個整數 s1, s2, …, sn (數字之間以一個空白隔開),代表基因序列 S = (s1, s2, …, sn),任兩個數字都不相同且 1 <= s1, s2, …, sn <= n。 

Output:

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

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
5
4
3 1 4 2
4
3 2 1 4
5
2 1 5 4 3
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 :

0
3
4
4
9

Hint :

Author :

104學年度全國決賽 (管理員:sagit)

  Solve it!   Status Forum