a210. Q_5_8 完美彩帶(同 Q-3-12,分治版)(APCS201906)
Tags : ch5
Accepted rate : 9人/10人 ( 90% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-06-01 15:00

Content

有一條細長的彩帶,總共有 $m$ 種不同的顏色,彩帶區分成 $n$ 格,每一格的長度都是 $1$,每一格都有一個顏色,相鄰可能同色。

長度為 $m$ 的連續區段且各種顏色都各出現 一次,則稱為「完美彩帶」。請找出總共有多少段可能的完美彩帶。請注意,兩段完美彩帶之間可能重疊。

Input

 第一行為整數 $m$ 和 $n$,滿足 $2 \leq m \leq n \leq 2 \times 10^5$;第二行有 $n$ 個以 空白間隔的數字,依序代表彩帶從左到右每一格的顏色編號,顏色編號是不超過 $10^9$ 的非負整數,每一筆測試資料的顏色數量必定恰好為 $m$。

Output

 有多少段完美彩帶。

Sample Input #1
4 10
1 4 1 7 6 4 4 6 1 7
Sample Output #1
3
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 1.0s , <10M
公開 測資點#1 (20%): 1.0s , <10M
公開 測資點#2 (20%): 1.0s , <10M
公開 測資點#3 (20%): 1.0s , <10M
公開 測資點#4 (20%): 1.0s , <10M
Hint :
Tags:
ch5
出處:
Prof.Wu [管理者: zero(管理員) ]


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