NC7509B

NC7509B

求含有子序列的最短子串长度为多少

Solution 1

时间复杂度：
思路：由于是唯一的，没有重复的字符，所以可以用十个指针维护十个位置，使得满足题目要求，每个指针指向中的字符，然后遍历一边，记录满足要求的最小值即可。

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 1e6 + 5;

void solve(){
    string s;cin>>s;
    int nn=s.size();
    vector<int> V[30];
    for(int i=0;i<nn;i++) V[s[i]-'a'].emplace_back(i);
    int ans=INF;
    int p=0,u=0,l=0,e=0,y=0,a=0,k=0,n=0,o=0,i=0;
    for(;p<V['p'-'a'].size();p++){
        for(;u<V['u'-'a'].size();){
            if(V['u'-'a'][u]<V['p'-'a'][p]) {u++;continue;}
            for(;l<V['l'-'a'].size();){
                if(V['l'-'a'][l]<V['u'-'a'][u]) {l++;continue;}
                for(;e<V['e'-'a'].size();){
                    if(V['e'-'a'][e]<V['l'-'a'][l]) {e++;continue;}
                    for(;y<V['y'-'a'].size();){
                        if(V['y'-'a'][y]<V['e'-'a'][e]) {y++;continue;}
                        for(;a<V['a'-'a'].size();){
                            if(V['a'-'a'][a]<V['y'-'a'][y]) {a++;continue;}
                            for(;k<V['k'-'a'].size();){
                                if(V['k'-'a'][k]<V['a'-'a'][a]) {k++;continue;}
                                for(;n<V['n'-'a'].size();){
                                    if(V['n'-'a'][n]<V['k'-'a'][k]) {n++;continue;}
                                    for(;o<V['o'-'a'].size();){
                                        if(V['o'-'a'][o]<V['n'-'a'][n]) {o++;continue;}
                                        for(;i<V['i'-'a'].size();){
                                            if(V['i'-'a'][i]<V['o'-'a'][o]) {i++;continue;}
                                            else {
                                                ans=min(ans,V['i'-'a'][i]-V['p'-'a'][p]+1);
                                                goto X;
                                            }
                                        }
                                        goto X;
                                    }
                                    goto X;
                                }
                                goto X;
                            }
                            goto X;
                        }
                        goto X;
                    }
                    goto X;
                }
                goto X;
            }
            goto X;
        }
        X:;
    }
    if(ans==INF) ans=-1;
    cout<<ans<<'\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

Update

博主当时觉得这样个比较有趣，但是实际上这样的思想用dfs写起来会更优雅一些？
于是乎在上课的时候脑补了一个dfs版本的上述思想解法。

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF = 0x3f3f3f3f;
const ll mod  = 1e9 + 7;
const ll N = 1e6 + 5;

string s,t="puleyaknoi";
int ans,p[15];
vector<int> V[30];

void dfs(int x){
    if(x==10){
        ans=min(ans,V[t[9]-'a'][p[9]]-V[t[0]-'a'][p[0]]+1);
        return;
    }
    while(p[x]<V[t[x]-'a'].size()){
        if(x){
            if(V[t[x]-'a'][p[x]]>V[t[x-1]-'a'][p[x-1]]) {dfs(x+1);return;}
        }else dfs(x+1);
        p[x]++;
    }
    return;
}

void solve(){
    ans=INF;
    for(int i=0;i<10;i++) p[i]=0;
    for(int i=0;i<26;i++) V[i].clear();
    cin>>s;
    int sz=s.size();
    for(int i=0;i<sz;i++) V[s[i]-'a'].push_back(i);
    dfs(0);
    if(ans==INF) ans=-1;
    cout<<ans<<'\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;cin>>T;
    while(T--) solve();
    return 0;
}

Solution 2

DP记录离当前字符最近的上一个字符的位置。

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF = 0x3f3f3f3f;
const ll mod  = 1e9 + 7;
const ll N = 1e5 + 5;

string s,t="puleyaknoi";
unordered_map<char,int> M;
int f[N][10],n,ans;

void init(){
    for(int i=0;i<10;i++) M[t[i]]=i;
}

void solve(){
    cin>>s;
    n=s.size();
    s=" "+s;
    ans=INF;
    for(int i=1;i<=n;i++){
        for(int j=0;j<10;j++) f[i][j]=f[i-1][j];
        if(!M.count(s[i])) continue;
        int id=M[s[i]];
        if(!id) f[i][id]=i;
        else f[i][id]=f[i-1][id-1];
        if(id==9 && f[i][id]) ans=min(ans, i-f[i][id]+1);
    }
    if(ans==INF) ans=-1;
    cout<<ans<<'\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int T;cin>>T;
    while(T--) solve();
    return 0;
}