解題區/解題區 - UVa

UVa 11104 - Cousins

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

first cousin ：如果兩個字串可以藉由移除不多於一半的字符，可以變成相同的字串。

ex. abcdef、axcyd 分別移除 (b, e, f)、(x, y)，就可以變成 acd。

然而如果它們 string (A, B)要稱為 (n+1)th cousin，則存在一個媒介 C，A 和 C 是 first cousin 以及 B 和 C 是 nth cousin。

Sample Input

1
2
3
4
5
6
7
8
a
b
abb
baa
abcdef
axcyd
0
0

Sample Output

1
2
3
2
2
1

Solution

這題看題看得很痛苦，也就是說找兩個字串最短的關係 (請無視長的)。

然而要如何找到最短的，思考一下絕對跟 LCS 有點關係，想了一整個早上仍然沒有結果，後來看了大神代碼回溯想法：

1
2
3
4
5
6
7
8
9
10
11
12
condition of first cousin for string a, b
* LCS(a, b) = maximum length LCS.
=> check if LCS(a, b) * 2 > a.len && LCS(a, b) * 2 > b.len, then output first cousin.
=> if not, we know string a and string xa which length is LCS(a, b) + a.len.
xa : __LCS(a, b)__ + a.str
    ^^^^^^^^^^^^^ // any letters., LCS(a, xa) = a.len, LCS(a, b) <= a.len, so xa and a are first cousins.
and so on, make string x2a which length is LCS(a, b) + 3 * a.len
x2a : __LCS(a, b)__ + a.str + a.str + a.str
    ^^^^^^^^^^^^^^^^^^^^^ // any letters., LCS(a, xa) = 2 * a.len, so xa and x2a are first cousisn.
above xa, x2a shown by letter consist, not order.
when x?a can become string b first cousin ? => __LCS(a, b)__ + (? * a.str) = half of b.

仔細想想，這解法類似於貪心？而 LCS 存在的關係是起手用。增倍貪心，把不需要的地方直接填跟目標的內容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
    char a[128], b[128];
    while (scanf("%s %s", a, b) == 2 && a[0] != '0') {
        int dp[128][128] = {};
        int la = strlen(a), lb = strlen(b);
        for (int i = 0; i < la; i++)
            for (int j = 0; j < lb; j++)
                if (a[i] == b[j])
                    dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1);
                else
                    dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
        int lcs = dp[la][lb];
        int ret = 1, len = lcs;
        if (la > lb)	swap(la, lb);
        while (len + len < lb) {
            len += la, la <<= 1;
            ret++;
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
condition of first cousin for string a, b
* LCS(a, b) = maximum length LCS.
=> check if LCS(a, b) * 2 > a.len && LCS(a, b) * 2 > b.len, then output first cousin.
=> if not, we know string a and string xa which length is LCS(a, b) + a.len.
xa : __LCS(a, b)__ + a.str
	 ^^^^^^^^^^^^^ // any letters., LCS(a, xa) = a.len, LCS(a, b) <= a.len, so xa and a are first cousins.
and so on, make string x2a which length is LCS(a, b) + 3 * a.len
x2a : __LCS(a, b)__ + a.str + a.str + a.str
	  ^^^^^^^^^^^^^^^^^^^^^ // any letters., LCS(a, xa) = 2 * a.len, so xa and x2a are first cousisn.
above xa, x2a shown by letter consist, not order.
when x?a can become string b first cousin ? => __LCS(a, b)__ + (? * a.str) = half of b.
*/