为何不同的写法,不同的结果?
查看原帖
为何不同的写法,不同的结果?
705343
cbkxx楼主2024/8/15 22:43

这是我原来WA36pts的代码:

#include<bits/stdc++.h>
using namespace std;
struct node{
	int son[70];
}tree[3000005];
int T,n,q,cnt,ans[3000005],len,pos;
char tmp[3000005];
int f(char x){
	if(x>='0'&&x<='9')return x-'0';
	if(x>='A'&&x<='Z')return x-'A'+10;
	return x-'a'+36;
}
void ins(int x,int wei){
	ans[x]++;
	if(wei==len-1){
		return;
	}
	int y=f(tmp[wei]);
	if(!tree[x].son[y]){
		tree[x].son[y]=++cnt;
	}
	ins(tree[x].son[y],wei+1);
}
int ask(int x,int wei){
	if(wei==len-1)return ans[x];
	int y=f(tmp[wei]);
	if(tree[x].son[y]){
		return ask(tree[x].son[y],wei+1);
	}
	return 0;
}
int main(){
	cin>>T;
	while(T--){
		cnt=pos+1;
		scanf("%d%d",&n,&q);
		for(int i=1;i<=n;i++){
			scanf("%s",tmp);
			len=strlen(tmp);
			ins(pos+1,0);
		}
		for(int i=1;i<=q;i++){
			scanf("%s",tmp);
			len=strlen(tmp);
			printf("%d\n",ask(pos+1,0));
		}
		pos=cnt;
	}
	return 0;
}

我是在调不出来,就换了一种写法,却就A了

#include<bits/stdc++.h>
using namespace std;
struct node{
	int son[70];
}tree[3000005];
int T,n,q,cnt,ans[3000005],pos;
char tmp[3000005];
int f(char x){
	if(x>='0'&&x<='9')return x-'0';
	if(x>='A'&&x<='Z')return x-'A'+10;
	return x-'a'+36;
}
void ins(char tmp[]){
	int len=strlen(tmp),now=pos+1;
	for(int i=0;i<len;i++){
		ans[now]++;
		int x=f(tmp[i]);
		if(!tree[now].son[x]){
			tree[now].son[x]=++cnt;
		}
		now=tree[now].son[x];
	}
	ans[now]++;
}
int ask(char tmp[]){
	int len=strlen(tmp),now=pos+1;
	for(int i=0;i<len;i++){
		int x=f(tmp[i]);
		if(!tree[now].son[x]){
			return 0;
		}
		now=tree[now].son[x];
	}
	return ans[now];
}
int main(){
	cin>>T;
	while(T--){
		cnt=pos+1;
		scanf("%d%d",&n,&q);
		for(int i=1;i<=n;i++){
			scanf("%s",tmp);
			ins(tmp);
		}
		for(int i=1;i<=q;i++){
			scanf("%s",tmp);
			printf("%d\n",ask(tmp));
		}
		pos=cnt;
	}
	return 0;
}
2024/8/15 22:43
加载中...