求条 玄关
查看原帖
求条 玄关
830990
roumeideclown楼主2024/12/6 21:31

样例没过,但想不通为什么没过,感觉自己写得很对

有没有大佬帮忙看一下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
vector<int> s[50005];
int trie[500005][2],word[500005],tot,num[500005]; //num[i] 存经过该节点的字符串个数
void trie_insert(vector<int> str) {
	int u=0;
	for(int i=0;i<str.size();i++) {
		int c=str[i];
		if(!trie[u][c]) trie[u][c]=++tot;
		u=trie[u][c];
		num[u]++;
	}
	word[u]++;
}
int find(vector<int> str) {
	int u=0,res=0;
	for(int i=0;i<str.size();i++) {
		int c=str[i];
		if(!trie[u][c]) return 0;
		u=trie[u][c];
		res+=word[u];
	}
	return res-word[u]+num[u];
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>m>>n;
	for(int i=1,len;i<=m;i++) {
		cin>>len;
		for(int j=1,x;j<=len;j++) {
			cin>>x;
			s[i].push_back(x);
		}
		trie_insert(s[i]);
	}
	// for(int i=0;i<=tot;i++) cout<<word[i]<<' ';
	// cout<<'\n';
	// dfs(0);
	// for(int i=0;i<=tot;i++) cout<<num[i]<<' ';
	// cout<<'\n';
	for(int i=1,len;i<=n;i++) {
		cin>>len;
		vector<int> str(len);
		for(int j=0;j<len;j++) cin>>str[j];
		cout<<find(str)<<'\n';
	}
	return 0;
}

2024/12/6 21:31
加载中...