本地ac提交wa36求助

P8306 【模板】字典树

zhengrunzhe @ 2022-09-13 01:38:47

#include<cctype>
#include<cstdio>
#include<cstring>
const int N(3e6+50);
char s[N];
int n,q;
inline const char change(const char &c)
{
    if (isdigit(c))return c-48;
    if (isalpha(c)==1)return c-55;
    if (isalpha(c)==2)return c-61;
}
namespace trie
{
    struct tree
    {
        int cnt;
        tree *son[62];
        static tree *null;
        void *operator new(size_t size);
        inline tree():cnt(0)
        {
            static bool init(0);
            if (!init)
            {
                init=1;
                null=new tree;
                for (int i(0);i<62;i++)null->son[i]=null;
            }
            for (int i(0);i<62;i++)son[i]=null;
        }
    }*root,*tree::null;
    char memory_pool[N*sizeof(tree)],*tail(memory_pool+sizeof memory_pool);
    #define null tree::null
    inline void *tree::operator new(size_t size){return tail-=size;}
    inline const void insert(char *s)
    {
        tree *p(root);
        const int n(strlen(s+1));
        for (int i(1);i<=n;i++)
        {
            const char k(change(s[i]));
            if (p->son[k]==null)p->son[k]=new tree;
            (p=p->son[k])->cnt++;
        }
    }
    inline const int query(char *s)
    {
        tree *p(root);
        const int n(strlen(s+1));
        for (int i(1);i<=n;i++)
        {
            const char k(change(s[i]));
            if (p->son[k]==null)return 0;
            p=p->son[k];
        }
        return p->cnt;
    }
}
inline const void work()
{
    trie::root=new trie::tree;
    scanf("%d%d",&n,&q);
    while (n--)scanf(" %s",s+1),trie::insert(s);
    while (q--)scanf(" %s",s+1),printf("%d\n",trie::query(s));
}
int main()
{
    //freopen("P8306_1.in","r",stdin);freopen("P8306_1.out","w",stdout);
    int t;
    scanf("%d",&t);
    while (t--)work();
    return 0;
}

by zhengrunzhe @ 2022-09-13 19:56:41

已解决 是isalpha函数的问题 要用islower/upper


|