求助,60pts就是过不去
查看原帖
求助,60pts就是过不去
665933
__LZH__楼主2023/7/13 17:07
#include<bits/stdc++.h>
using namespace std;
struct trie{
    int c[105];
    bool x;
    int num;
}t[3111110];
int n,m,T,cnt,x[1000010],a[300010],ans,cnm[300010];
string s;
int g(char x){
    if(x>='A'&&x<='Z'){
    	return x-'A';
    }else if(x>='a'&&x<='z'){
    	return x-'a'+26;
    }else{
		return x-'0'+52;
    }
}
void ins(string s,int k){
    int root=0,len=s.size();
    for(int i=0;i<len;i++){
        int ch=g(s[i]);
        if(t[root].c[ch]==0){
            t[root].c[ch]=cnt++;
        }
        root=t[root].c[ch];
    }
    x[root]=k;
}
int wcnm(string s){
	int root=0;
	for(int i=0;i<s.size();i++){
		int ch=g(s[i]);
		root=t[root].c[ch];
		if(root==0){
			return 0;
		}
	}
	return x[root];
}
void merge(int l,int r){
    if(l>=r){
    	return;
    }
    int mid=(l+r)/2;
    merge(l,mid);
    merge(mid+1,r);
    int i=l,j=mid+1,k=l;
    for(int i=l;i<=r;i++){
    	cnm[i]=0;
    }
    while(i<=mid&&j<=r){
        if(a[i]>a[j]){
            cnm[k++]=a[j++];
            ans+=mid-i+1;
        }else{
        	cnm[k++]=a[i++];
        }
    }
    while(i<=mid){
    	cnm[k++]=a[i++];
    }
    while(j<=r){
    	cnm[k++]=a[j++];
    }
    for(int i=l;i<=r;i++){
    	a[i]=cnm[i];
    }
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s;
		ins(s,i);
	}
	for(int i=1;i<=n;i++){
		cin>>s;
		a[i]=wcnm(s);
	}
	merge(1,n);
	cout<<ans;
	return 0;
}
2023/7/13 17:07
加载中...