换scanf试试吧,数据比较奇怪。
by white_ice @ 2024-03-21 11:02:44
@[white_ice](/user/1035256)
```
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
//trie tree
const int N=1e4+10;
int tree[N][26],cnt[N],idx;
int m,n;
//建树
void build(string s){
int p=0;
for(int i=0;s[i];i++){
int j=s[i]-'a';
if(!tree[p][j]) tree[p][j]=++idx;
p=tree[p][j];
}
cnt[p]++;
}
int query(string s){
int p=0;
for(int i=0;s[i];i++){
int j=s[i]-'a';
if(!tree[p][j]) return 0;
p=tree[p][j];
}
if(cnt[p]==1){
cnt[p]++;
return 1;
}else if(cnt[p]==0){
return 0;
}else{
return 2;
}
}
int main(){
cin>>n;
while(n--){
char name[50];
scanf("%s",name);
build(name);
}
cin>>m;
while(m--){
char namex[50];
scanf("%s",namex);
int x=query(namex);
if(x==0) cout<<"WRONG"<<endl;
else if(x==1) cout<<"OK"<<endl;
else cout<<"REPEAT"<<endl;
}
return 0;
}
```
还是超时
by Celestinefly @ 2024-04-04 18:48:14
@[Celestinefly](/user/1250563)
1.把N调成800005,我用这个过的,应该开的比较小
2.把query和build中string s换成char *s
```cpp
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
//trie tree
const int N=800004;
int tree[N][30],cnt[N],idx;
int m,n;
//建树
void build(char *s){
int p=0;
//int len = s.length();
for(int i=0;s[i];i++){
int j=s[i]-'a';
if(!tree[p][j]) tree[p][j]=++idx;
p=tree[p][j];
}
cnt[p]++;
}
int query(char *s){
int p=0;
//int len = s.length();
for(int i=0;s[i];i++){
int j=s[i]-'a';
if(!tree[p][j]) return 0;
p=tree[p][j];
}
if(cnt[p]==1){
cnt[p]++;
return 1;
}else if(cnt[p]==0){
return 0;
}else{
return 2;
}
}
int main(){
//freopen("P2580_5.in","r",stdin);
//freopen("out.txt","w",stdout);
cin>>n;
while(n--){
char name[50];
scanf("%s",name);
build(name);
}
cin>>m;
while(m--){
char namex[50];
scanf("%s",namex);
int x=query(namex);
if(x==0) cout<<"WRONG"<<endl;
else if(x==1) cout<<"OK"<<endl;
else cout<<"REPEAT"<<endl;
}
return 0;
}
```
~~至于为什么换我也不太清楚,可能是string最后读入了其他东西吧~~
by white_ice @ 2024-04-05 21:43:33
@[white_ice](/user/1035256)
好的,谢谢你
by Celestinefly @ 2024-04-06 09:22:31