思路：二进制枚举

数据范围$n\le 20$，因此可以考虑暴力枚举每一个子序列，判断枚举的子序列是否满足条件

我们可以使用DFS枚举，也可以使用二进制枚举，枚举选/不选第$i$个字符，最终构成最终的字符串即可。

首先，我们遍历所有可能的删除方案。由于不能删除两个连续的字符，我们可以使用位运算来表示删除方案。对于字符串中的每个字符，我们都有两种选择：删除它或保留它。因此，总共有2^n种可能的删除方案，其中n是字符串的长度。

然后，对于每一种删除方案，我们检查删除后的字符串是否是好串。我们使用一个标志变量来表示当前的删除方案是否有效。如果删除后的字符串中存在两个连续的字符被删除，我们就将标志变量设置为false。

最后，如果当前的删除方案有效，并且删除后的字符串是好串，我们就将答案加一。

时间复杂度

$O(n\times 2^n)$

代码

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int len = s.size();
    long long ans = 0;
    for (int i = 0; i < (1 << len); i++) {
        bool flag = true;
        for (int j = 0; j < len - 1; j++) {
            if ((i & (1 << j)) > 0 && (i & (1 << (j + 1))) > 0) flag = false;
        }
        if (!flag) continue;
        string sb = "";
        for (int j = 0; j < len; j++) {
            if ((i & (1<<j)) == 0){
                sb += s[j];
            }
        }
        if (sb.find("tazi") != string::npos) ans ++;
    }
    cout << ans << endl;
    return 0;
}

python代码

s = input().strip()
len_s = len(s)
ans = 0
for i in range(1 << len_s):
    flag = True
    for j in range(len_s - 1):
        if (i & (1 << j)) > 0 and (i & (1 << (j + 1))) > 0:
            flag = False
    if not flag:
        continue
    sb = ""
    for j in range(len_s):
        if (i & (1<<j)) == 0:
            sb += s[j]
    if "tazi" in sb:
        ans += 1
print(ans)

Java代码

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        int len = s.length();
        long ans = 0;
        for (int i = 0; i < 1 << len; i++) {
            boolean flag = true;
            for (int j = 0; j < len - 1; j++) {
                if ((i & (1 << j)) > 0 && (i & (1 << (j + 1))) > 0) flag = false;
            }
            if (!flag) continue;
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < len; j++) {
                if ((i & (1<<j)) == 0){
                    sb.append(s.charAt(j));
                }
            }
            if (sb.toString().contains("tazi")) ans ++;
        }
        System.out.println(ans);
    }
}

题目描述

一个好串定义为，当且仅当这个串中包含"tazi"连续子串。例如"tazige","shuaitazi"都是好串，而taxxxzi不是好串。

现在你可以删除一些字符使给定的串变成好串，但不能删除两个连续的字符，求有多少种方案可以使原串变成好串。

输入描述

输入一行，表示原字符串。长度不超过20。

输出描述

输出一个整数，表示方案数。

样例

输入

tazixx

输出

3

说明

第一种什么都不删，第二种删除第一个'x'，第三种删除第二个'x'。