trie树0pts 求调教
查看原帖
trie树0pts 求调教
754502
_AyachiNene楼主2023/8/19 17:33
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[114514];
int cnt,sum[1145141],trie[1145141][3];
int sum1[1145141];
void insert(int len)
{
	int root=0;
	for(int i=1;i<=len;i++)
	{
		if(!trie[root][a[i]])
			trie[root][a[i]]=++cnt;
		root=trie[root][a[i]];
		sum[root]++;
	}
	sum1[root]++;
}
int query(int len)
{
	int root=0;
	int ans=0;
	int flag=0;
	for(int i=1;i<=len;i++)
	{
		if(!trie[root][a[i]])
		{
			flag=1;
			break;
		}
		else
			root=trie[root][a[i]];
		ans+=sum1[root];
	}
	if(flag)
		ans+=sum[root]-sum1[root];
	return ans;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		for(int j=1;j<=x;j++)
			cin>>a[j];
		insert(x);
	}
	while(m--)
	{
		int x;
		cin>>x;
		for(int i=1;i<=x;i++)
			cin>>a[i];
		cout<<query(x)<<endl;
	}
}
2023/8/19 17:33
加载中...