#23311: 我的思路想法


a31185367 (Jeffrey)

School : 淡江大學
ID : 104338
IP address : [101.10.1.95]
Last Login :
2023-11-07 14:52:33
f339. 3.下雪的日子(Snow) -- TOI2020年8月新手同好會 | From: [61.230.171.8] | Post Date : 2020-11-06 19:58

可以設定一個陣列road[n],n為道路長度

其中0代表為0~1的道路,1代表1~2的道路,以此類推,起始值設成一個數像0代表全部道路為封閉狀態

然後每一次輸入道路暢通的時候,

設定一個迴圈,變數i起始值為道路起點,判斷式為小於終點

每個迴圈都把陣列的"i"格設成另一個數像1代表為暢通狀態

全部輸入完畢後再設一個迴圈變數k設為0

判斷陣列k格是否為非原始設定初始值(0),

如果是,則先輸入k值代表起點,再設定一個變數y初始值為k+1

設一個while迴圈判斷式:

如果road[y]非暢通狀態(road[y]不等於1),就把k+1,y+1;

while迴圈跑完就輸出y值代表暢通道路的終點

我的思路為這樣,歡迎其他想法告訴我讓我多學一點^^

 
#23365: Re:我的思路想法


SUNGOD (黑龍炎使.煞氣ㄟSUNGOD)

School : 國立交通大學
ID : 95834
IP address : [1.169.219.170]
Last Login :
2024-05-31 14:37:13
f339. 3.下雪的日子(Snow) -- TOI2020年8月新手同好會 | From: [118.166.198.226] | Post Date : 2020-11-10 21:05

令A[100001]為從該點連通至最遠路段,每次更新A[i]的值(應為max(A[i],input))

EX n=5,m=2的話初始化大概長這樣:

A     0 1 2 3 4 5

A[i]  0 1 2 3 4 5

輸入3 5

A     0 1 2 3 4 5

A[i]  0 1 2 5 4 5

m筆輸入結束後注意以下情況

A    0 1 2 3 4 5

A[i] 2 5 2 3 4 5

雖然0可以一路通到2,但很明顯1已經通道5了那麼0應該也要通道5=>對A[i]再做一次更新

最後用A[i]跑一遍做輸出

時間複雜度 :建表O(m+n)[更新要n],查詢O(n)

樓主的方法建表要O(m*n),查詢O(n),測資如果嚴一點可能tle

 
#24687: Re:我的思路想法


p3a_owhj (阿普二信)

School : No School
ID : 39897
IP address : [210.71.40.1]
Last Login :
2024-12-11 14:36:20
f339. 3.下雪的日子(Snow) -- TOI2020年8月新手同好會 | From: [36.225.32.163] | Post Date : 2021-03-14 18:44

有空應該加強一下測資

 
ZeroJudge Forum