UVa 11104 - Cousins

contents

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

Problem

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

ex. abcdefaxcyd 分別移除 (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.
*/