成语接龙(深搜模板) | 您所在的位置:网站首页 › 成语接龙ppt模板下载 › 成语接龙(深搜模板) |
成语接龙(深搜模板)
描述
开门见山 山高水长 长夜难明 明争暗斗 斗志昂扬 扬眉吐气 气象万千 千载难逢 逢凶化吉…… 成语接龙,顾名思义,成语一个接着一个,每一个成语的第一个字要和前一个成语的最后一个字相同。两个人玩成语接龙可以比谁先接不上,而一个人玩成语接龙也可以努力把龙接得尽量长。 现在给你若干“成语”(由小写英文字母组成的字符串),你可以利用这些给定的成语进行接龙游戏。对于每一个成语,你需要回答:如果以它开头,一条成语接龙中最多可以包含多少个成语(它自身也算一个)? 注意:每个成语都可以重复使用任意次。 输入首先在一行中输入一个正整数 n (n≤10⁵) 表示成语的数量。 随后是 n 行,每行一个由小写字母组成的字符串 s 代表一个成语 (1≤ |s|≤10⁵)。 保证所有字符串长度之和不超过10⁵。 输出对于每一个成语,在一行中输出以它开头形成的所有成语接龙序列当中成语的最大数量 x 。 如果接龙可以无限进行,输出 “inf”(不包括双引号)。 输入样例 1 3 axab bjac qaq 输出样例 1 2 1 inf 提示 axab bjac bjac qaq qaq qaq qaq qaq ... 代码: #include #include #include #include #include #define ll long long using namespace std; const ll maxn = 2e5 + 10; ll n, m, i, j, k, t, x, y, z; mapdd, mm; mapv; ll dfs(char ne, ll step) { if (mm[ne] && step)return maxn; if (dd[ne])return dd[ne]; dd[ne] = 1; mm[ne] = 1; for (ll i = 0, j = v[ne].size(); i string s[n + 1]; dd.clear(); for (i = 0; i char a = s[i][s[i].length() - 1]; mm.clear(); dd[a] = dfs(a, 0); if (dd[a] >= maxn)cout |
CopyRight 2018-2019 实验室设备网 版权所有 |