uva 11127(暴力)

左手的ㄟ右手 2022-03-30 13:35 218阅读 0赞

题意：给出一个字符串，包含0、1、\*，当中×是能够替换成0或者1的，假设字符串的某个子串S有SSS这种连续反复3次出现，不是Triple-free串，问给出的字符串能够形成多少个非Triple-free串。  
题解：由于串长度最多31，所以能够暴力枚举每一位，边枚举边推断。

#include <stdio.h>
    #include <string.h>
    const int N = 35;
    char str[N], str2[N];
    int n;
    long long res;
    
    bool judge(int cur) {
        for (int i = 1; i * 3 <= (cur + 1); i++) {
            int e = cur - i * 3, cnt2 = 0;
            for (int j = cur; j > cur - i; j--) {
                int cnt = 0;
                for (int k = j; k > e; k -= i)
                    if (str2[j] != str2[k])
                        break;
                    else
                        cnt++;  
                if (cnt == 3)
                    cnt2++; 
                else
                    break;
            }
            if (cnt2 == i)
                return false;
        }
        return true;
    }
    
    void dfs(int cur) {
        if (cur == n) {
            res++;
            return;
        }
        if (cur == 0 || cur == 1) {
            if (str[cur] == '0' || str[cur] == '1') {
                str2[cur] = str[cur];
                dfs(cur + 1);
            }
            else {
                str2[cur] = '0';
                dfs(cur + 1);
                str2[cur] = '1';
                dfs(cur + 1);
            }
            return;
        }
        str2[cur] = '0';
        if (judge(cur)) {
            if (str[cur] == '0' || str[cur] == '*')
                dfs(cur + 1);
        }
        str2[cur] = '1';
        if (judge(cur)) {
            if (str[cur] == '1' || str[cur] == '*')
                dfs(cur + 1);
        }
    }
    
    int main() {
        int cas = 1;
        while (scanf("%d", &n) == 1 && n) {
            scanf("%s", str);
            res = 0;
            dfs(0);
            printf("Case %d: %lld\n", cas++, res);
        }
        return 0;
    }