今天灌水不踊跃，出道题吧 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

今天灌水不踊跃，出道题吧

今天灌水不踊跃，出道题吧# JobHunting - 待字闺中

p*22012-05-28 07:05

1 楼

给你一个字符串数组，你需要发现符合如下规律的一组字符串，使得这组字符串的字符
总数最大化
1. 第一个字符串的第一个字符是最后一个字符串的最后一个字符
2. 每一个字符串的最后一个字符是下一个字符串的第一个字符
找到的这组字符串的顺序不变，还是按照在初始数组的顺序排列。
例如
input
3
abc
ca
cba
output
6
abc
ca
符合条件，但是总长度为5
abc
cba
符合条件，长度为6
最后返回最大长度6
字符串的个数最大到 5*10^5

l*82012-05-28 07:05

2 楼

带权有向图中找weight sum 最大的回路。

l*82012-05-28 07:05

3 楼

不对，还有这个条件：
找到的这组字符串的顺序不变，还是按照在初始数组的顺序排列

【在 l*********8 的大作中提到】

: 带权有向图中找weight sum 最大的回路。

q*y2012-05-28 07:05

4 楼

DFS 求和最大的路径

p*22012-05-28 07:05

5 楼

时间复杂度？

【在 q***y 的大作中提到】

: DFS 求和最大的路径

q*y2012-05-28 07:05

6 楼

可以啊，建图的时候只保留有效地边。

【在 l*********8 的大作中提到】

: 不对，还有这个条件：
: 找到的这组字符串的顺序不变，还是按照在初始数组的顺序排列

p*22012-05-28 07:05

7 楼

更新了一下。输入最大是5*10^5个字符串。

q*y2012-05-28 07:05

8 楼

貌似要O(n^3)。太困了，明天再想。。

【在 p*****2 的大作中提到】

: 更新了一下。输入最大是5*10^5个字符串。

l*82012-05-28 07:05

9 楼

只有26个字母吗？

【在 p*****2 的大作中提到】

: 更新了一下。输入最大是5*10^5个字符串。

p*22012-05-28 07:05

10 楼

只有26个字母。不会有其他字符。

【在 l*********8 的大作中提到】

: 只有26个字母吗？

g*s2012-05-28 07:05

11 楼

任何一个字符串，只考虑它的第一个后最后一个字母。
设p(a,b) 为第一个字母是a，最后一个字母是b的字符串数目。
这样，扫描一遍就可以算出所有的p。p的空间是26×26.
后面怎么处理都不难了。

【在 p*****2 的大作中提到】

: 给你一个字符串数组，你需要发现符合如下规律的一组字符串，使得这组字符串的字符
: 总数最大化
: 1. 第一个字符串的第一个字符是最后一个字符串的最后一个字符
: 2. 每一个字符串的最后一个字符是下一个字符串的第一个字符
: 找到的这组字符串的顺序不变，还是按照在初始数组的顺序排列。
: 例如
: input
: 3
: abc
: ca

p*22012-05-28 07:05

12 楼

膜拜grass。真是太牛了。这题我想了一个多小时。

【在 g***s 的大作中提到】

: 任何一个字符串，只考虑它的第一个后最后一个字母。
: 设p(a,b) 为第一个字母是a，最后一个字母是b的字符串数目。
: 这样，扫描一遍就可以算出所有的p。p的空间是26×26.
: 后面怎么处理都不难了。

A*l2012-05-28 07:05

13 楼

赞简化问题的思维

【在 g***s 的大作中提到】

l*82012-05-28 07:05

14 楼

维护26个字母之间的最长距离矩阵。
每个字符串代表一条边，边的两个节点是字符串第一个字符和最后一个字符。
例如 cba 代表从c到a的weight为3的边。
每scan一个字符串， update一次最长距离矩阵,并检查回路。( O(k) for each scan,
which k is 26. )
For n strings, O(k*n) time.

l*82012-05-28 07:05

15 楼

你说的p(a,b)是从a到b的最长通路长度吧？

【在 g***s 的大作中提到】

A*l2012-05-28 07:05

16 楼

好像有点问题
字母虽然只有26个，但是是可以重复使用的吧？
abc
cde
efc
cgh
ha
这样c自己形成了环，不知道是不是合题意？

,

【在 l*********8 的大作中提到】

: 维护26个字母之间的最长距离矩阵。
: 每个字符串代表一条边，边的两个节点是字符串第一个字符和最后一个字符。
: 例如 cba 代表从c到a的weight为3的边。
: 每scan一个字符串， update一次最长距离矩阵,并检查回路。( O(k) for each scan,
: which k is 26. )
: For n strings, O(k*n) time.

l*82012-05-28 07:05

17 楼

复杂回路里面节点是可以重复的。

【在 A**l 的大作中提到】

: 好像有点问题
: 字母虽然只有26个，但是是可以重复使用的吧？
: abc
: cde
: efc
: cgh
: ha
: 这样c自己形成了环，不知道是不是合题意？
:
: ,

l*82012-05-28 07:05

18 楼

贴个程序。直接在这里敲的，可能有问题：）
int longestCircle(vector &ss)
{
int len[26][26];
memset(len, 0, 26*26*sizeof(int));
int maxLen = 0;
for (int i=0; istring &str = v[i];
int vFrom = str[0] - '0';
int vTo = str[str.size()-1] - '0';

for(int j=0; j<26; ++j)
len[j][vTo] = max(len[j][vTo], len[j][vFrom]+len[vFrom][vTo])
maxLen = max(maxLen, len[vTo][vTo];
}
return maxLen;
}

【在 p*****2 的大作中提到】

l*82012-05-28 07:05

19 楼

grass，我越看越不明白你的p是什么意思。能不能给个例子解释一下？

【在 g***s 的大作中提到】

q*y2012-05-28 07:05

20 楼

高人啊。膜拜。

【在 g***s 的大作中提到】

l*82012-05-28 07:05

21 楼

我看不懂啊。看懂了麻烦解释一下吧，谢谢！

【在 q***y 的大作中提到】

: 高人啊。膜拜。

t*j2012-05-28 07:05

22 楼

先预处理，把所有头字母和尾字母相同的的单词，只取最长单词，其他去掉。
这样最多总共有26×26种可能性。然后图论算最长环路。

l*82012-05-28 07:05

23 楼

"找到的这组字符串的顺序不变，还是按照在初始数组的顺序排列。"
变成图之后就没办法保持这种顺序了。
另外，以a开头以b结尾的字符串应该能出现多个。

【在 t*****j 的大作中提到】

: 先预处理，把所有头字母和尾字母相同的的单词，只取最长单词，其他去掉。
: 这样最多总共有26×26种可能性。然后图论算最长环路。

t*j2012-05-28 07:05

24 楼

哦哦哦，没仔细看题，没看到这要求.......

【在 l*********8 的大作中提到】

: "找到的这组字符串的顺序不变，还是按照在初始数组的顺序排列。"
: 变成图之后就没办法保持这种顺序了。
: 另外，以a开头以b结尾的字符串应该能出现多个。