请问为什么10pts呢?
查看原帖
请问为什么10pts呢?
300078
pengyule楼主2020/6/27 10:36
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vei;
#define pb push_back
int cnt=1;
int trie[500005][60];
int vis[500005];
inline void Insert(string s,int idx){
    int root=1,len=s.length(),x;
    for(int i=0;i<len;i++){
        x=s[i]-'a'+1;
        if(!trie[root][x]) trie[root][x]=++cnt;
        root=trie[root][x];
    }
    vis[root]=idx;
}
inline int Find(string s){
    int root=1,len=s.length(),x;
    for(int i=0;i<len;i++){
        x=s[i]-'a'+1;
        root=trie[root][x];
    }
    return vis[root];
}
long long ans=0;
vei Merge(vei al,vei ar){
    int i=0,j=0,x=al.size(),y=ar.size();
    vei res; res.clear();
    while(i<x && j<y){
        if(al[i]>ar[j]) ans++;
        if(al[i]<ar[j]) res.pb(al[i++]);
        else res.pb(ar[j++]);
    }
    while(i<x) res.pb(al[i++]);
    while(j<y) res.pb(ar[j++]);
    return res;
}
vei Sort(vei a){
    if(a.size()==1) return a;
    vei al,ar; al.clear(),ar.clear();
    int mid=a.size()/2;
    for(int i=0;i<mid;i++) al.pb(a[i]);
    for(int i=mid;i<a.size();i++) ar.pb(a[i]);
    al=Sort(al),ar=Sort(ar);
    return Merge(al,ar);
}
vei a; string str;
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>str,Insert(str,i);
    for(int i=1;i<=n;i++) cin>>str,a.pb(Find(str));
	a=Sort(a);
	cout<<ans<<endl;
	return 0;
}

以上是代码,望好心人留步帮我看一看哪里出错行吗,谢谢您付出宝贵的时间。

代码简洁易懂(代码稍微长点但是可读性极强)。

2020/6/27 10:36
加载中...