UVA 11127 - Triple-Free Binary Strings (DFS + 位運算)

問題描述

給定模式串 P（含 0,1,*），* 可替換為 0/1。求符合模式的二進制串中，不含任何子串形如 SSS（三個相同串連接） 的串的數量。|P| < 31。

位運算 DFS

• 用整數 state 存儲已生成的二進制串（低位在前）。
• 遞歸生成：對每個位置，若 P[i]='0' 填 0，'1' 填 1，'*' 分支填 0/1。
• 每一步檢查新添加的字符是否導致後綴出現 SSS：枚舉長度 L=1..len/3，檢查後 3L 位是否為三個相同的 L 位塊。
• 位運算提取：mask = (1<>L) & mask; block2 = (state>>2L) & mask; 若三塊相等則非法。

完整代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 35;
int n; char pat[MAXN];

bool hasTriple(int state, int len) {
    for(int L=1; 3*L<=len; L++) {
        int mask = (1<>L) & mask;
        int b2 = (state>>2*L) & mask;
        if(b0==b1 && b1==b2) return true;
    }
    return false;
}

int dfs(int state, int len) {
    if(hasTriple(state, len)) return 0;
    if(len == n) return 1;
    int ans = 0;
    if(pat[len]=='0') ans += dfs(state, len+1);
    else if(pat[len]=='1') ans += dfs(state | (1<>n && n) {
        cin>>pat;
        cout << "Case " << cas++ << ": " << dfs(0,0) << endl;
    }
    return 0;
}

複雜度

最多 2³⁰ ≈ 10⁹ 分支，但 Triple-Free 條件極強，實際搜索樹極小。n≤30 瞬間通過。