洛谷 P1019 单词接龙

缘起

和 99° 兄（要是是妹纸就太好啦,嘿嘿~）的日常联谊~ ^_^ 洛谷 P1019 单词接龙

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
题目描述
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和 atide 间不能相连。

输入格式
输入的第一行为一个单独的整数n (n≤20)表示单词数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.

输出格式
只需输出以此字母开头的最长的“龙”的长度

输入输出样例
输入 #1复制
5
at
touch
cheat
choose
tact
a
输出 #1复制
23
说明/提示
（连成的“龙”为atoucheatactactouchoose）

NOIp2000提高组第三题

如果将单词视作图的顶点, 单词a和单词b可以接龙, 则a和b之间就有一条 a->b的弧. 则题目给的单词就是一个有向图. 则既然是有向图, 其实就是求最长路（必须从某些顶点出发的，为什么? 因为题目要求必须以某个字母开头啊~） 本题本蒟蒻想到了以下几种姿势艹它

这里首先说清楚一下题意（一道题可以有多重理解足以说明题目出的有多烂了）

1
2
3
两个单词, 单词1和单词2拼接, 取最小的k（因为要求最长的龙）, 
使得单词1的k后缀和单词2的k前缀一样. 如果k等于单词1或
单词2的长度的话, 则不能拼接.

开一个visited数组, 要求visited[i]<=2即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
//#include "stdafx.h"

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL

int n, head[25],cnt, v[30],ans, len[30], inc[30][30]; // len[i]是第i个单词的长度, inc[i][j]是a[i]->a[j]能增加的长度
char a[25][105],b;

struct Arc
{
	int from, to, nxt;
}g[500];

void addArc(int from, int to)
{
	g[cnt].from = from, g[cnt].to=to, g[cnt].nxt = head[from];
	head[from] = cnt++;
}

bool can(int x, int y) // 单词 a[x]->a[y]是否可以接龙?
{
	int kk; // a[x]后缀的长度kk
	for (kk = 1; kk<min(len[x], len[y]); kk++)
	{
		if (strstr(a[y], a[x]+len[x]-kk)==a[y])
		{
			break;
		}
	}
	if (kk<len[x] && kk < len[y])
	{
		inc[x][y]=len[y]-kk;
	}
	return kk<len[x] && kk < len[y];
}

void build() // 建有向图
{
	for (int i = 1; i<=n; i++)
	{
		for (int j = 1; j<=n; j++)
		{
			if (can(i, j))
			{
				addArc(i,j);
			}
		}
	}
}

void dfs(int i, int curlen) // 当前到了i号顶点, 当前的长度是curLen
{
	ans = max(ans, curlen);
	for (int h = head[i],to; ~h; h = g[h].nxt)
	{
		to = g[h].to;
		if (v[to]>=2) // 一个单词最多用2次,如果已经是2了, 就不允许再用了
		{
			continue;
		}
		v[to]++;
		dfs(to, curlen+inc[i][to]);
		v[to]--;
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	memset(head, -1, sizeof(head));
	scanf("%d", &n);
	for (int i = 1;i<=n;i++)
	{
		scanf("%s", a[i]);
		len[i] = strlen(a[i]);
	}
	cin>>b; // 这里说一下, 对于字符, 洛谷不欢迎getchar(), 使用cin. 我特么被WA的莫名其妙~
	build();
	for (int i = 1;i<=n;i++)
	{
		if (a[i][0]!=b)
		{
			continue;
		}
		memset(v, 0, sizeof(v));
		v[i]++;
		dfs(i, len[i]);
	}
	printf("%d\n", ans);
	return 0;
}

ac情况

1
2
3
4
5
6
所属题目
P1019 单词接龙
评测状态
Accepted
评测分数
100