为什么哈希没有题解啊
查看原帖
为什么哈希没有题解啊
591179
huangyuxaing楼主2023/9/8 11:56

感觉这道题就是哈希乱搞可以过掉,题解区好像翻不到这个做法(

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int M=1e6+7,inf=0x3f3f3f3f,k=1e9+7,mxl=M/10;
int n,m,l,x,po[M],ha[M],ans1[M],ans2[M];
vector<int> a[M],len,b[M],pre[M],q[M];
unordered_map<int,int> cnt,inq,flag,fff;
bool ff;
void init(){
	po[0]=1LL;
	for(int i=1;i<=mxl;i++)po[i]=po[i-1]*k;
	//cout<<po[mxl]<<endl;
}
void inpdata(int i){
	scanf("%llu",&l);
	for(int j=1;j<=l;j++){
		scanf("%llu",&x);
		if(x==0)x=114514;
		a[i].push_back(x); 
	}
}
void inpdata2(int i){
	scanf("%llu",&l);
	for(int j=1;j<=l;j++){
		//cout<<x<<endl;
		scanf("%llu",&x);
		if(x==0)x=114514;
		b[i].push_back(x); 
	}
}
void to_cal_hash(int i){
	int tmp=0LL;
	for(int j=0;j<a[i].size();j++){
		int x=a[i][j];
		tmp+=x*po[j];
		pre[i].push_back(tmp);
	}
}
void to_cal_hash2(int i){
	for(int j=0;j<b[i].size();j++)ha[i]+=b[i][j]*po[j];
}
int change(int sum,int r){
	//cout<<sum<<" "<<mxl<<" "<<r<<" "<<po[mxl-r]<<endl;
	return sum*po[mxl-r];
}
void solve(int ql){
	for(int i=1;i<=n;i++){
		flag.clear();
		for(int l=0;l+ql-1<a[i].size();l++){
			int r=l+ql-1,tmp;
			//cout<<l<<" "<<ql<<" "<<a[i].size()<<endl;
			if(l)tmp=change(pre[i][r]-pre[i][l-1],r+1);
			else tmp=change(pre[i][r],r+1);
			//if(i==2&&l==3)cout<<tmp<<endl;
			//if(i==2&&l==3)cout<<change(ha[2],b[2].size())<<endl;
			if(flag[tmp]||(!inq[tmp]))continue;
			flag[tmp]=1;
			cnt[tmp]++;
			ans2[i]+=inq[tmp];
			//cout<<i<<" "<<l<<" "<<r<<" "<<inq[tmp]<<endl;
			//cout<<l<<" "<<r<<" "<<i<<endl;
		}
	}
}
signed main(){
	scanf("%llu%llu",&n,&m);
	init();
	for(int i=1;i<=n;i++){
		inpdata(i);
		a[i].push_back(inf-i);
		inpdata(i);
		to_cal_hash(i); 
		//cout<<a[i].size()<<endl;
	}
	for(int i=1;i<=m;i++){
		inpdata2(i);
		if(!fff[l]){
			len.push_back(l);
			fff[l]=1;
		}
		q[l].push_back(i);
		to_cal_hash2(i);
		inq[change(ha[i],b[i].size())]++;
	}
	//cout<<pre[1][4]-pre[1][0]<<endl;
	//cout<<ha[1]<<endl;
	//cout<<change(ha[2],ll)<<endl;
	int sum=0;
	for(int i=0;i<len.size();i++){
		cnt.clear();
		solve(len[i]);
		//ff=0;
		for(int j=0;j<q[len[i]].size();j++){
			int x=q[len[i]][j];
			ans1[x]=cnt[change(ha[x],b[x].size())];
		}
	}
	for(int i=1;i<=m;i++)sum+=ans1[i];
	for(int i=1;i<=n;i++)sum-=ans2[i];
	if(sum)printf("No\n");
	//cout<<sum<<endl;
	for(int i=1;i<=m;i++)printf("%llu\n",ans1[i]);
	for(int i=1;i<=n;i++)printf("%llu ",ans2[i]);
	return 0;
} 
```cpp
2023/9/8 11:56
加载中...