托米没有完成上一个任务，准备施展黑魔法推倒 1317

黑魔法咒语被描述为一个 长为 n 的，仅包含小写英文字母 ‘a’…’i’ 的字符串，在托米所在的星球，魔法造成的每次有效伤害都是来自他的一个子序列，对于每一个 ‘a’… ‘i’ 的排列(共 9! 种)，若作为咒语的子序列出现, 就会造成 1 的伤害

而咒语的总伤害为所有 ‘a’… ‘i’ 的排列造成的伤害值之和，托米能打出多少点的伤害，是否能击败 1317 呢？
提交的代码
提交时间：2018-07-28 09:40:07 语言：C++ 代码长度：490 运行时间： 895 ms 占用内存：504K
运行结果：答案正确

暴力

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
//#define int long long
char s[5000];
signed main()
{
    int ans = 0;
    cin>>s;
    char a[10]="abcdefghi";
    do{

       int t =0 ;
       int i = 0;
       while(t<9&&s[i])
       {
            if(a[t]==s[i])
            {
                t++;
                i++;
            }
            else i++;
       }
       if(t==9)
       ans++;

    }while(next_permutation(a,a+9));
    cout<<ans<<endl;
    //return 0;
}

二分

#include<stdio.h>
#include<string.h>
#include<vector>
#include<stdlib.h>
#include<algorithm>
using namespace std;
char s[3005];
vector<int>v[10];
char a[]={'a','b','c','d','e','f','g','h','i'};
int main(){
    scanf(" %s",s);
    int len=strlen(s);
    for(int i=0;i<len;i++){
        v[s[i]-'a'].push_back(i);
    }
    for(int i=0;i<9;i++){
        v[i].push_back(len);
    }
    int ans=0;
    do{
        int leap=0,h=0;
        for(int i=0;i<9;i++){
            h=*lower_bound(v[a[i]-'a'].begin(),v[a[i]-'a'].end(),h);
            if(h==len){
                leap=1;
                break;
            }
        }
        if(!leap)
            ans++;
    }while(next_permutation(a,a+9));
    printf("%d\n",ans);
    return 0;
}

预处理出下一个位置

#include <bits/stdc++.h>

using namespace std;
const int maxn = 3000 + 7;
char s[maxn], p[10];
int nx[maxn][30], first[30];
int main(){
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    for(int i = 0; i < 9; i++) p[i + 1] = 'a' + i;
    for(int i = 0; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            if(nx[i][s[j] - 'a'] == 0) nx[i][s[j] - 'a'] = j;
        }
    }
    int ans = 0;
    do{
        bool flag = true;
        int now = 0;
        for(int i = 1; i <= 9; i++){
            if(nx[now][p[i] - 'a']) now = nx[now][p[i] - 'a'];
            else{
                flag = false;
                break;
            }
        }
        if(flag) ans++;
    }while(next_permutation(p + 1, p + 9 + 1));
    printf("%d\n", ans);
    return 0;
}

更快的预处理：

#include <bits/stdc++.h>

using namespace std;
const int maxn = 3000 + 7;
char s[maxn], p[10];
int nx[maxn][30], first[30], pos[30];
int main(){
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    for(int i = 0; i < 9; i++) p[i + 1] = 'a' + i;
    for(int i = n; i >= 0; i--){
        for(int j = 0; j < 9; j++) nx[i][j] = pos[j];
        if(i) pos[s[i] - 'a'] = i;
    }
    int ans = 0;
    do{
        bool flag = true;
        int now = 0;
        for(int i = 1; i <= 9; i++){
            if(nx[now][p[i] - 'a']) now = nx[now][p[i] - 'a'];
            else{
                flag = false;
                break;
            }
        }
        if(flag) ans++;
    }while(next_permutation(p + 1, p + 9 + 1));
    printf("%d\n", ans);
    return 0;
}