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
  

   
 

   
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**
 
0
 
 
 
 
      
 
Case 1: 2
 
Case 2: 16
 
Case 3: 9
 
 
 
 
 
     
 
    
 
   

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

   
思路：深搜加位运算，每次判断当前串如果有重复3个
   
#include 
    
     
#include 
     
       const int N = 35; int n; char str[N]; bool judge(int state, int len) { int m = (1<
      
       >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<
       
        
 字串就返回，然后数字可以用二进制数表示。
        
 
        
代码：