小屋創作

巴哈姆特 APP

專屬 ACG 勇者的廣闊世界

以 APP 瀏覽

日誌2020-08-02 00:00

ZeroJudge - f164: 萬球同心移位之章 解題心得

作者:Not In My Back Yard

題目連結:
f164: 萬球同心移位之章


題目大意:
輸入第一列給定三正整數 n 、 m 、 q (3 < n < 5 × 10 ^ 5 , 2 < m < 10 ^ 3 , q < 30),代表一開始有 0 ~ n - 1 標有這 n 個數字的球順時針依序圍成一圈,並有 m 個操作以及 q 筆詢問。

接著有 m 列,每列給定給定一個字元(只會是 F 或是 R)以及兩整數 A 、 B (0 ≦ A 、 B < n),代表要把編號 A 的球移到編號 B 的隔壁(注意,當 A = B 時,此時不需要移動)。 F 代表要移到 B 的順時針方向的旁邊(順鄰); R 則代表 B 的逆時針的旁邊(逆鄰)。

最後一列給定 q 個整數 C (0 ≦ C < n),代表要詢問編號 C 的球之逆鄰與順鄰的球之編號為何?



範例輸入:
範例輸入一:
4 3 3
R 3 2
F 3 0
F 1 2
0 1 2

範例輸入二:
5 6 2
F 2 1
R 1 3
F 2 4
F 1 4
R 0 2
R 3 4
0 4


範例輸出:
範例輸出一:
1 3 2 0 3 1

範例輸出二:
1 2 3 1


解題思維:
可以使用雙向連結串列(Linked List)達成要求。

首先就是初始化一開始 0 ~ n 的情況,也就是 0 是 1 的逆鄰 、 1 是 0 的順鄰 、 1 是 2 的逆鄰 、 2 是 1 的順鄰 、 …… 、 n - 1 是 0 的逆鄰 、 0 是 n - 1 的順鄰。

接著對於每個移動的操作 F A B (或是 R A B),先將 A 從原本的位置移開。這會導致原本 A 的逆鄰,其順鄰從 A 變為 A 原本的順鄰、原本的 A 的順鄰,其逆鄰從 A 變為 A 原本的逆鄰。如下圖所示(紅線代表更動後):

再來就是看操作的種類(F 或是 R)。如果是 F ,先將 B 設為 A 的逆鄰 、 B 的順鄰設為 A 的順鄰。然後再把 B 的順鄰,其逆鄰從 B 變成 A ;最後將 B 的順鄰變更為 A 。如下圖:

如果是 R ,就跟上面類似,只是順逆相反。

把 m 個操作如上述的方式做完之後,對於每個詢問輸出逆鄰與順鄰的球之編號即可。



本人的程式碼(放在CodePile)

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

0

0

LINE 分享

相關創作

ZeroJudge - b674: Is It A Tree 解題心得

MSFS 2020 我的飛行日記

LeetCode - 258. Add Digits 解題心得

留言

face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】