我正在嘗試解決codeforces 上的問題761 B “Dasha and Friends”，我已經被困了一段時間了。這似乎是一個簡單的問題，但我就是想不通。這是 codeforces 教程頁面上給出的問題的官方提示：
讓我們在陣列中添加兩條軌道的相鄰障礙對之間的距離，并檢查是否可以使用元素的回圈移位從另一個獲取它們中的一個。
我無法理解上述宣告在說什么或為什么會成立。另外，我在這里找到了解決方案，但我不明白他們在做什么。誰能幫我這個？我不需要完整的解決方案，只需要了解這里的基本概念是什么。任何幫助表示贊賞，謝謝！
uj5u.com熱心網友回復：
跑步者有不同的起點，因此您無法比較相對于起點的位置。
但是障礙物之間的距離是相同的，所以比較這些距離的序列是有效的。
第一個問題是圍繞起始位置的分段 - 但由于回圈運行的回圈性質，我們可以通過減去last_barrierfrom來獲得它的長度L first_barrier。
第二個問題 - 我們有兩個距離串列/陣列，并且應該檢查一個串列的回圈移位是否給出類似于第二個串列的串列。鏈接解決方案只生成所有回圈移位并比較身份。這是一種簡單的方法，對于給定的限制（n=50）效果很好。
如果你需要對大 n 做同樣的事情，二次復雜度變得不合適，你需要更好的方法 - 例如，將第一個串列 ( 4,1,2=>4,1,2,4,1,2) 加倍并搜索第二個的出現加倍（如子字串搜索）
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/382607.html
下一篇：最少斷線次數