7分求调教
查看原帖
7分求调教
754673
Jackson_Miller楼主2023/8/11 08:09
#include<bits/stdc++.h>
using namespace std;
int trie[4*1000005][66],sum[4*1000005],tot1[1000001],tot;
string s;
int getchar(char x) {
	return x-'0';
}
void insert() {
	int len=s.size();
	int root=0;
	for(int i=0; i<len; i++) {
		int id=getchar(s[i]);
		if(!trie[root][id]) {
			trie[root][id]=++tot;
		}
		root=trie[root][id];
		sum[root]++;
	}
	tot1[root]++;
}
int sch() {
	int len=s.size();
	int root=0,res=0;
	for(int i=0; i<len; i++) {
		int id=getchar(s[i]);
		if(!trie[root][id]) {
			return sum[root];
		}
		root=trie[root][id];
		res+=tot1[root];
	}
	return res-tot1[root]+sum[root];
}
int main() {
	int n,q;
	cin>>n>>q;
	char a;
	for(int i=1; i<=n; i++) {
		int k;
		cin>>k;
		s.clear();
		for(int i=1; i<=k; i++) {
			cin>>a;
			if(a=='1') {
				s+='1';
			} else if(a=='0') {
				s+='0';
			}
		}
		insert();
	}
	for(int i=1; i<=q; i++) {
		int k;
		cin>>k;
		s.clear();
		for(int i=1; i<=k; i++) {
			cin>>a;
			if(a=='1') {
				s+='1';
			} else if(a=='0') {
				s+='0';
			}
		}
		cout<<sch()<<endl;
	}
}
2023/8/11 08:09
加载中...