11127 - Triple-Free Binary Strings(dfs+位运算)

Problem J

Triple-Free Binary Strings 

Input: Standard Input

Output: Standard Output

A binary string consists of ones and zeros. Given a binary string T, if  there is no binary string S such that SSS (concatenate three copies of S together) is a substring of T, we say T is triple-free.      

A pattern consists of ones, zeros and asterisks, where an asterisk(*) can be replaced by either one or zero. For example, the pattern 0**1 contains strings 0001, 0011, 0101, 0111, but not 1001 or 0000.      

Given a pattern P, how many triple-free binary strings does it contain?      

Input
Each line of the input represents a test case, which contains the length of pattern, n(0<n<31), and the pattern P. There can be maximum 35 test cases.       

The input terminates when n=0.      

Output
For each test case, print the case number and the answer, shown below.       

Sample Input                       Output for Sample Input

4 0**1 5 ***** 10 **01**01**

Case 1: 2 Case 2: 16 Case 3: 9

题意：给定一个串，*可以代表0,1有多少字串，没有3个连续相同的串。

思路：深搜加位运算，每次判断当前串如果有重复3个

#include <stdio.h>
#include <string.h>

const int N = 35;

int n;
char str[N];

bool judge(int state, int len) {
	int m = (1<<len) - 1;
	int s = (state&m);
	state = ((state&(~m))>>len);
	int ss = (state&m);
	state = ((state&(~m))>>len);
	if (s == ss && ss == state) return true;
	return false;
}

int dfs(int state, int len) {
	int ans = 0, s = state;
	for (int i = 0; i <= len - 3; i ++) {
		if ((len - i) % 3 == 0 && judge(s, (len - i) / 3)) return 0;
		s = ((s&(~1))>>1);
	}
	if (len == n) return 1;
	if (str[len] == '0')
		ans += dfs(state, len + 1);
	else if (str[len] == '1')
		ans += dfs(state^(1<<len), len + 1);
	else {
		ans += dfs(state, len + 1);
		ans += dfs(state^(1<<len), len + 1);
	}
	return ans;
}

int main() {
	int cas = 0;
	while (~scanf("%d",&n) && n) {
		scanf("%s", str);
		printf("Case %d: %d\n", ++cas, dfs(0, 0));
	}
	return 0;
}
           

字串就返回，然后数字可以用二进制数表示。

代码：