这个题暴力展开的复杂度不对吗?
查看原帖
这个题暴力展开的复杂度不对吗?
131591
蒟蒻君HJT泽渡透香楼主2022/4/16 23:51

场外选手乱写了一个,被 hack 数据搞了

#include <bits/stdc++.h>
using namespace std;
int my_map[10007];
const int mod=10007,base=97;
string nb[105];
inline int check(string s,int p){
	if(s[p]>='0'&&s[p]<='9') return 1;
	if(s[p]>='A'&&s[p]<='Z') return 1;
	if(s[p]>='a'&&s[p]<='z') return 1;
	if(s[p]=='_') return 1;
	return 0;
}
inline int get_hash(string s,int lb,int rb){
	int p=0;
	for(int i=lb;i<=rb;++i) p=p*base+(s[i]-32),p%=mod;
	return p;
}
string work(string s,int lb,int rb){
	string res;
	int ha=get_hash(s,lb,rb);
	if(!my_map[ha]){
		for(int i=lb;i<=rb;++i)
			res+=s[i];
		return res;
	}
	int pre=my_map[ha],l=nb[my_map[ha]].size();
	string ans;my_map[ha]=0;
	for(int i=0;i<l;++i){
		if(!check(nb[pre],i)){
			res+=nb[pre][i];
		}
		else {
			int k=i;
			while(k+1<l && check(nb[pre],k+1)) ++k;
			ans=work(nb[pre],i,k); 
			res=res+ans;
			i=k;
		}
	}
	my_map[ha]=pre;
	return res;
}
int main(){
	int n,l;
	string line,ans;
	scanf("%d",&n);getline(cin,line);
	for(int i=1;i<=n;++i){
		getline(cin,line);
		l=line.size();
		if(line[0]=='#'){
			if(line[1]=='d'){
				int k=8;
				while(line[k+1]!=' ') ++k;
				my_map[get_hash(line,8,k)]=i;
				for(int j=k+2;j<l;++j) nb[i]+=line[j];
			}
			else {
				my_map[get_hash(line,7,l-1)]=0;
			}
			cout<<endl; 
			continue;
		}
		for(int j=0;j<l;++j){
			if(!check(line,j)){
				cout<<line[j];
			}
			else {
				int k=j;
				while(k+1<l && check(line,k+1)) ++k;
				ans=work(line,j,k); 
				cout<<ans;
				j=k;
			}
		}
		cout<<endl;
	}
	return 0;
}
2022/4/16 23:51
加载中...