Problem Solving►UVa

UVa 11127 - Triple-Free Binary Strings

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

中文網址

Solution

利用位運算和 DFS 去放入不同的數字，每次放完就去檢查是否可用三個 S 組成，可以就不繼續做(不是 triple-free)，剪枝。

檢查時因為舊的字串已經檢查過，所以只需要檢查跟新加入那個有關的，例如:

cba => 通過
dcba => 檢查 dcb => 通過
edcba => 檢查 edc => 通過
fedcba => 檢查 fed 和 fedcba (S 長度為 2) => 通過
...

作法則是檢查時移掉後面已檢查過的位元:

check(str >> (len - 3 * i), i)  //i = 子字串長度

Code

UVa 11127
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
43
44
45
46
#include<cstdio>

char pattern[32];
int n;
int dfs(int str, int len);
inline bool check(int sub_str, int sub_len);
int main()
{
	int Case = 1;
	while (scanf("%d", &n) && n)
	{
		scanf("%s", pattern);
		printf("Case %d: %d\n", Case++, dfs(0, 0));
	}

	return 0;
}
inline bool check(int sub_str, int sub_len)
{
	int mask = (1 << sub_len) - 1;
	int s1 = sub_str&mask;
	sub_str >>= sub_len;
	int s2 = sub_str&mask;
	sub_str >>= sub_len;
	int s3 = sub_str&mask;

	return (s1 == s2&&s2 == s3);
}
int dfs(int str, int len)
{
	int sub_len = len / 3;
	//剪枝，排除已可以用SSS組成的
	for (int i = 1; i <= sub_len; i++)
		if (check(str >> (len - 3 * i), i))
			return 0;

	if (len == n)
		return 1;
	else if (pattern[len] == '0')
		return dfs(str, len + 1);
	else if (pattern[len] == '1')
		return dfs(str | (1 << len), len + 1);
	else//'*'
		return dfs(str, len + 1) + dfs(str | (1 << len), len + 1);//放 0 + 放 1
}