c218: kevin 愛旅行
標籤 :
通過比率 : 100% (1 人 / 1 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2017-07-12 10:26

內容 :

kevin 很喜歡旅行,而且喜歡用一個劇酷的方式旅行
這次他挑了一個由 n 個城市組成的國家,並將其編號為(1 ~ n)
而旅行社大方地表示 kevin 可以任意決定旅遊起點並給了他一個序列 A 來表示旅遊的順序
其中的 Ai (1 <= i <= n)代表著到了 i 城市後下個要到的城市
但卻被 kevin 大師一眼看出序列中一個嚴重的邊緣現象:

1.裡面沒有任何地方會到城市 1
2.經過城市 1 後的下一個城市還是城市 1 (即 A1 = 1)

再看到這種安排後,kevin 覺得太奇怪了,為了想要一窺城市 1 的神秘
他跟旅行社提出了兩個要求:
1.不管 kevin 從哪個城市出發都會到達城市 1 
2.為了長期觀察城市 1 的邊緣指數,在離開城市 1 後的 k 天後他將要回到城市 1

看到 kevin 這樣毫無頭緒的的要求,要重新訂製一個序列需要太高成本
不過現在你可以每次透過修改序列中的一個數字當作一個操作
身為一個其實跟kevin沒甚麼關係的你
你能幫 kevin 算算需要多少操作才可以達到 kevin 的要求嗎?

輸入說明

第一行有兩個數字 n , k ( 0 < n , m <= 5 * 10 ^ 5 )
分別代表城市的數量和kevin的要求天數
第二行是序列 A 
其中 Ai 為到 i 城市後下個會到的城市
保證 A1 = 1
Ai (2 <= i <= n) ,則 2 <= Ai <= n

輸出說明

輸出一個數字代表要達到kevin要求的最少操作

範例輸入
範例輸入 1 :
9 1
1 4 2 3 5 5 5 7 7


範例輸入 2 :
11 4
1 3 4 10 4 4 6 11 11 2 3
範例輸出
範例輸出 1 :
2


範例輸出 2 :
2
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1M
公開 測資點#6 (5%): 1.0s , <1K
公開 測資點#7 (5%): 1.0s , <1M
公開 測資點#8 (5%): 1.0s , <1M
公開 測資點#9 (5%): 1.0s , <1M
公開 測資點#10 (5%): 1.0s , <1M
公開 測資點#11 (5%): 1.0s , <1M
公開 測資點#12 (5%): 1.0s , <1M
公開 測資點#13 (5%): 1.0s , <1M
公開 測資點#14 (6%): 1.0s , <10M
公開 測資點#15 (6%): 1.0s , <10M
公開 測資點#16 (6%): 1.0s , <10M
公開 測資點#17 (6%): 1.0s , <10M
公開 測資點#18 (6%): 1.0s , <10M
提示 :

範測 1 中

若把 序列改為 1 1 2 3 1 5 5 7 7 

則可以使得從任意位置出發皆可到達城市1

而從城市1出發後經過1天即可回到城市1

 

範測 2 中

若把 序列改為 6 3 4 10 4 4 6 11 11 1 3

則可以使得從任意位置出發皆可到達城市1

而從城市1出發後經過4天即可回到城市1 (1 -> 6 -> 4 -> 10 -> 1)

標籤:
出處:
[編輯: boook (boook) ]
編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」