薛猫猫杯 成语接龙（纪念第一次一血）
小Z和大Z最近沉迷于成语接龙游戏，他们准备把成语接龙的规则修改一下。规则是这样的：有两个字符串，如果第一个字符串是第二个字符串的子串(也就是第一个字符串在第二个字符串中可以找到)，那么第一个字符串后面可以接第二个字符串。问题来了，现在有n个字符串，你可以把n个字符串的顺序进行重组，使得这n个字符串可以成语接龙，即第一个字符串后面可以接第二个字符串，第二个字符串后面可以接第三个字符串，…，第n-1个字符串后面可以跟第n个字符串。问你能不能把n个字符串顺序重组，满足这n个字符串可以成语接龙。
【薛猫猫杯 成语接龙（纪念第一次一血）】Input
第一行为一个整数T，代表有T组样例。（T<=10)
每组数据中：
第一行为一个整数N，表示有N个字符串。(N<=100)
接下来n行，每行一个字符串，每个字符串长度小于等于100。
Output
对于每组测试样例，如果这n个字符串顺序重排之后可以成语接龙，输出“Yes”，否则输出“No”。每个测试样例占一行。
Sample Input
3
5
Abcabc
Abc
Abca
Abc
A
2
ABAC
ACB
2
ACDB
ACB
Sample Output
Yes
No
No
7分30秒一血。
暴力就完事了。
这不是重点，重点是我后缀自动机做法都想完了看到了n小于100…
按长度排序然后暴力比较。
ac代码：
#include
using namespace std;
typedef long long ll;
const int maxn = 105;
struct Str {
char s[maxn];
int len;
} str[maxn];
bool cmp(Str &a, Str &b) {
return a.len < b.len;
}int main() {
int t, n;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
for(int i = 0;
i < n;
i++) {
scanf("%s", str[i].s);
str[i].len = strlen(str[i].s);
}
sort(str, str + n, cmp);
bool flag = 0;
for(int i = 0;
i < n - 1;
i++) {
if(!strstr(str[i + 1].s, str[i].s)) {
flag = 1;
break;
}
}
printf("%s\n", flag ? "No" : "Yes");
}
return 0;
}
推荐阅读
- 热闹中的孤独
- 诗歌:|诗歌: 《让我们举起世界杯，干了！》
- 年轻人，干了孤独这杯酒
- 不以胜负论出关
- C语言学习|第十一届蓝桥杯省赛 大学B组 C/C++ 第一场
- 蓝桥杯试题
- python青少年编程比赛_第十一届蓝桥杯大赛青少年创意编程组比赛细则
- 临清一中学子斩获北大培文杯作文大赛全国大奖
- 第三届文人杯诗书画大赛获名单公示
- 来自《道德经》的成语