求助关于TLE
查看原帖
求助关于TLE
389955
WillW_Chen楼主2023/11/21 15:46
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<vector>
#include<bitset>
#include<list>
#include<set>
#include<queue>
#include<map>
#include<stack>
#include<ctime>
#include<random>
#include<functional>
#include<iostream>
#include<istream>
#include<streambuf>
#include<fstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define endl "\n"
const ll MAXN=5e5+10;
int n;
string tt;
int pre[MAXN];
int suf[MAXN];
inline int match(string s,string t){
    int ind=0;
    for(int i=0;i<(int)s.size();i++){
        if(ind<(int)t.size()&&s[i]==t[ind]){
            ind++;
        }
    }
    return ind;
}
inline int match2(string s,string t){
    int ind=t.size()-1;
    int cnt=0;
    for(int i=s.size()-1;i>=0;i--){
        if(ind>=0&&s[i]==t[ind]){
            ind--;
            cnt++;
        }
    }
    return cnt;
}
ll ans;
void solve(){
    cin>>n;
    cin>>tt;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        pre[i]=match(s,tt);
        suf[i]=match2(s,tt);
        suf[i]=tt.size()-suf[i];
    }
    sort(suf+1,suf+n+1);
    sort(pre+1,pre+n+1);
    int ind=n;
    for(int i=n;i>=1;i--){
        while(ind&&pre[i]<suf[ind]){
            ind--;
        }
        ans+=ind;
    }
    cout<<ans<<endl;
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    srand(time(NULL));
    int T=1;
    while(T--){
        solve();
    }
    return 0;
}

我这样写,把求前缀和后缀写成函数,然后Atcoder上T了3个点

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<vector>
#include<bitset>
#include<list>
#include<set>
#include<queue>
#include<map>
#include<stack>
#include<ctime>
#include<random>
#include<functional>
#include<iostream>
#include<istream>
#include<streambuf>
#include<fstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define endl "\n"
const ll MAXN=5e5+10;
int n;
string t;
int pre[MAXN];
int suf[MAXN];
inline int match2(string s,string t){
    int ind=t.size()-1;
    int cnt=0;
    for(int i=s.size()-1;i>=0;i--){
        if(ind>=0&&s[i]==t[ind]){
            ind--;
            cnt++;
        }
    }
    return cnt;
}
ll ans;
void solve(){
    cin>>n;
    cin>>t;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        int ind=0;
        for(int i=0;i<(int)s.size();i++){
            if(ind<(int)t.size()&&s[i]==t[ind]){
                ind++;
            }
        }
        pre[i]=ind;
        ind=t.size()-1;
        int cnt=0;
        for(int i=s.size()-1;i>=0;i--){
            if(ind>=0&&s[i]==t[ind]){
                ind--;
                cnt++;
            }
        }
        suf[i]=t.size()-cnt;
    }
    sort(suf+1,suf+n+1);
    sort(pre+1,pre+n+1);
    int ind=n;
    for(int i=n;i>=1;i--){
        while(ind&&pre[i]<suf[ind]){
            ind--;
        }
        ans+=ind;
    }
    cout<<ans<<endl;
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    srand(time(NULL));
    int T=1;
    while(T--){
        solve();
    }
    return 0;
}

但这样写就A了,是函数调用时间的问题吗,求助各位大佬

2023/11/21 15:46
加载中...