这两种写法我感觉没区别但一个100一个0
查看原帖
这两种写法我感觉没区别但一个100一个0
546246
E_huanJX泛舟客楼主2022/9/14 21:54

rt 100分:


#include<bits/stdc++.h>
using namespace std;
const int N=500010;
int tr[N][28];
set<int> id[N];//有在这个位置结尾的单词的文章的编号
int n,m,tot;
char s[25];
inline void insert(int ID)
{
    int p=0;
    for(int i=1;s[i];i++)
    {
        int x=s[i]-'a';
        if(!tr[p][x]) tr[p][x]=++tot;
        p=tr[p][x];
    }
    id[p].insert(ID);
}
inline void Query()
{
    int p=0;
    for(int i=1;s[i];i++)
    {
        int x=s[i]-'a';
        if(!tr[p][x]) return;
        p=tr[p][x];
    }
    for(int a:id[p]) printf("%d ",a);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int l; scanf("%d",&l);
        for(int j=1;j<=l;j++)
            scanf("%s",s+1),insert(i);
    }
    scanf("%d",&m);
    while(m--)
    {
        scanf("%s",s+1);
        Query();
        puts("");
    }
    return 0;
}

0分

/*
trie裸题
*/
#include<bits/stdc++.h>
using namespace std;
const int N=500010;
int tr[N][28];
vector<int> id[N];//有在这个位置结尾的单词的文章的编号
int n,m,tot;
char s[25];
inline void insert(int ID)
{
    int p=0;
    for(int i=1;s[i];i++)
    {
        int x=s[i]-'a';
        if(!tr[p][x]) tr[p][x]=++tot;
        p=tr[p][x];
    }
    id[p].push_back(ID);
}
inline void Query()
{
    int p=0;
    for(int i=1;s[i];i++)
    {
        int x=s[i]-'a';
        if(!tr[p][x]) return;
        p=tr[p][x];
    }
    sort(id[p].begin(),id[p].end());
    unique(id[p].begin(),id[p].end());
    for(int a:id[p]) printf("%d ",a);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int l; scanf("%d",&l);
        for(int j=1;j<=l;j++)
            scanf("%s",s+1),insert(i);
    }
    scanf("%d",&m);
    while(m--)
    {
        scanf("%s",s+1);
        Query();
        puts("");
    }
    return 0;
}

0分(2)

/*
trie裸题
*/
#include<bits/stdc++.h>
using namespace std;
const int N=500010;
int tr[N][28];
vector<int> id[N];//有在这个位置结尾的单词的文章的编号
int n,m,tot;
char s[25];
inline void insert(int ID)
{
    int p=0;
    for(int i=1;s[i];i++)
    {
        int x=s[i]-'a';
        if(!tr[p][x]) tr[p][x]=++tot;
        p=tr[p][x];
    }
    id[p].push_back(ID);
}
inline void Query()
{
    int p=0;
    for(int i=1;s[i];i++)
    {
        int x=s[i]-'a';
        if(!tr[p][x]) return;
        p=tr[p][x];
    }
    sort(id[p].begin(),id[p].end());
    unique(id[p].begin(),id[p].end());
    for(int i=0;i<id[p].size();i++) printf("%d ",id[p][i]);

}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int l; scanf("%d",&l);
        for(int j=1;j<=l;j++)
            scanf("%s",s+1),insert(i);
    }
    scanf("%d",&m);
    while(m--)
    {
        scanf("%s",s+1);
        Query();
        puts("");
    }
    return 0;
}
2022/9/14 21:54
加载中...