PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] CF R162 Div.1 Problem D

看板Prob_Solve (計算數學 Problem Solving)作者paae0226 (paae0226)時間11年前 (2013/04/12 16:56)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串1/1

題目連結： http://ppt.cc/avSY 題意：給予兩個由 R, G, B 所組成的字串 s (|s| <= 10^6) 和 t (|t| <= 10^6) 一開始有兩個人分別位在 s[1] 和 t[1] 上 (index 為 1-base) 現在可以對這兩個人下指令，比如「站在 R 上的人前進一格」此時如果 s[1] = R，則第一個人必須走到 s[2]，站在 t 上的人亦同所以如果兩個人所站的 s[i] 和 t[j] 顏色一樣，則下達該顏色會讓兩個人同時前進如果有某一個人已經站在 sequence 的尾巴 (s[length(s)] 或 t[length(t)]) 則不能下 s[length(s)] 或 t[length(t)] 那格的顏色也就是不能下會讓某一個人走出自己所處 sequence 的命令現在定義一個狀態 (i, j) 是 reachable 為存在一個命令 sequence I，使從 s[1] 和 t[1] 出發，按照 I 的命令走完之後可以使兩人最後分別停在 s[i] 和 t[j] 否則為 unreachable 問 reachable 的狀態總數 -------------------- 這題雖然出題者有寫 tutorial，不過想了一些時間還是沒有看懂 ( tutorial 位址： http://ppt.cc/NNlw ) 目前看完為止的心得是，首先給出一個觀察假設 A = s[1 .. i - 1], B = s[1 .. i], C = t[1 .. j - 1], D = t[1 .. j] 若要判斷 (i, j) 是否 reachable，如果發現 D 是 A 的 subsequence 或者 B 是 C 的 subsequence，則為了讓 s 可以走到 i 已經足以讓 t 超過 j，反過來也一樣但是這樣並不夠，進一步可以發現如果 s[1] != t[1] 下了一個指令讓其中一個人前進，比如說 s，則縮短後的 B' = [2 .. i] 有可能就變成 C 的 subsequence 了如果分別讓 s 或 t 前進都發生這種情況的話可以發現此時 A 和 C 等長並且 A 和 C 會分別是 xyxy... 和 yxyx... 的 format 再來得到形如 ...xy, ...yx 的狀態會是 unreachable 的上面黃色的是無法理解的部份我自己的想法是的確如果狀態最後長得像 ...xy 和 ...yx 那麼因為 s[i - 1] != t[j - 1]，要進入 (i, j) 狀態勢必要通過 (i - 1, j) 或 (i, j - 1) 但因為 s[i] = t[j - 1] 且 s[i - 1] = t[j] 所以無論如何，都沒有辦法停留在 (i, j) 但是目前困惑的是，單純這樣就足以找出所有不合法的狀態了嗎會不會因為 (i, j) 這個狀態走不到，連帶影響到後面使得某些不是以 ...xy 和 ...yx 做結尾的狀態也變成 unreachable 一點小結是目標似乎是要證明 (i, j) 是 unreachable iff (1) s[1 .. i] 是 t[1 .. j - 1] 的 subsequence (或反過來) OR (2) s[i - 1] = t[j] AND s[i] = t[j - 1] AND s[i - 1] != t[j - 1] 不過自己推不出來也不知道怎麼樣從 tutorial 裏的過程得到這個結論想請問大家是否有些提示謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.114.86.67 ※ 編輯: paae0226 來自: 61.230.225.20 (04/12 21:42) ※ 編輯: paae0226 來自: 61.230.225.20 (04/12 22:59)