接龙游戏求思路

问题讨论区 提高段
1

image

2

@CZF2919 救我！！！

3

来了

4

看了

5

不会了

emmm,好像跟哈希有点关系，偶不对，是字典树

6

这是字典树

7

字典树我没学过

8

@金杭东 帮帮孩子

9

@吴梓峤 这是下节课的内容吧？

10

每个单词结尾做个标记，然后字典树上 dfs 取标记数量的最大值就行了啊

11 
#include <bits/stdc++.h>
using namespace std;
const int N=50+5,maxn=5e5+10;

int n;
char s[N];

struct trie{
    int end[maxn],ch[maxn][26],idx=0;
    vector<int> son[maxn];//记录孩子节点

    void insert(char *s){
        int p=0;//树根
        for(int i=0;s[i];i++){
            int now_cnt=s[i]-'a';
            if(!ch[p][now_cnt]){//若当前节点不存在
                ch[p][now_cnt]=++idx;//创建新节点
                son[p].push_back(now_cnt);//添加孩子
            }
            
            p=ch[p][now_cnt];//往下延伸
        }
        end[p]++;
    }

    int query(int u){
        //利用dfs便利字典树，取单词结尾数的最大值
        
        int ans=0,add=end[u];
        if(son[u].size()==0) return ans+add;
        
        for(auto v:son[u])
            //寻找孩子
            ans=max(ans,query(ch[u][v])+add);
        return ans;
    }
}tree;

int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>s,tree.insert(s);

    cout<<tree.query(0);
    return 0;
}

为什么c++编译器上样例能过，信友队上却RE呢？

12

@stringdp100005 快来啊

13

@CZF2919 也来帮我，你看看上面的思路就知道了

14

@俞天行

15

@椰子糕

16

快来助我

17

这个空间分配不出来吧可能

18

那该怎么改？

19

用指针写法吗？

20

哦，A了，但严老师，帮我看看，我这份代码到底是卡过的，还是真的能过

#include <bits/stdc++.h>
using namespace std;
const int N=50+5,maxn=5e5+10;

int n;
char s[N];

struct trie{
    int end[maxn],ch[maxn][26],idx=0;

    void insert(const char *s){
        int p=0;//树根
        for(int i=0;s[i];i++){
            int now_cnt=s[i]-'a';
            if(!ch[p][now_cnt])//若当前节点不存在
                ch[p][now_cnt]=++idx;//创建新节点
            
            p=ch[p][now_cnt];//往下延伸
        }
        end[p]++;
    }

    int query(int u){
        //利用dfs便利字典树，取单词结尾数的最大值
        
        int ans=0,add=end[u];
        for(int v=0;v<26;v++)
            if(ch[u][v])
                ans=max(ans,query(ch[u][v]));
        return ans+add;
    }
}tree;

int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>s,tree.insert(s);

    cout<<tree.query(0);
    return 0;
}