题目连结： 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)