全RE,求助
查看原帖
全RE,求助
631544
li_cat楼主2024/4/13 10:47

思路是把单词转换成哈希值,然后二分去找

#include <bits/stdc++.h>
#define ull unsigned long long
#define str string
#define K 456
using namespace std;
ull n,l,m;
ull st[1005][5005],lo[2005];

//读入 
void read(ull &x){
	ull awa,w=0;char ch=getchar();
	awa=ch=='-'?-1:1;
	if(ch=='-') ch=getchar();
	while(ch>='0'&&ch<='9'){
		w=w*10+(ch-'0');
		ch=getchar();
	}
	x=awa*w;
}
ull readst(){
	ull awa=0;char ch=getchar();
	while(ch!=' '&&ch!='\n'){
		awa=awa*K+int(ch);
		ch=getchar();
	}
		
	return awa;
}
//排序
bool cmp(ull x,ull y){return x<y;}
//二分
bool er(ull x,ull r,ull list[]){
	ull l=0,mid;
	while(l<r){
		mid=(l+r)/2;
		if(list[mid]==x) return true;
		if(list[mid]<x) l=mid+1;
		else r=mid-1;
	}
	if(list[l]==x) return true;
	return false;
}
int main(){
	read(n);
	
	for(int i=1;i<=n;++i){
		//读入
		read(l);
		for(int j=0;j<l;++j) st[i][j]=readst();
		
		//去重
		sort(st[i],st[i]+l,cmp);
		lo[i]=unique(st[i],st[i]+l)-st[i];
	}
	
	//处理询问
	read(m);
	for(int i=1;i<=m;++i){
		ull s=readst();
		for(int j=1;j<=n;++j) if(er(s,lo[j],st[j])) cout<<j<<' ';
		cout<<'\n';
	}
	return 0;
} 
2024/4/13 10:47
加载中...