p*****2
发帖数: 21240 | 1 给你一个字符串数组，你需要发现符合如下规律的一组字符串，使得这组字符串的字符
总数最大化
1. 第一个字符串的第一个字符是最后一个字符串的最后一个字符
2. 每一个字符串的最后一个字符是下一个字符串的第一个字符
找到的这组字符串的顺序不变，还是按照在初始数组的顺序排列。
例如
input
3
abc
ca
cba
output
6
abc
ca
符合条件，但是总长度为5
abc
cba
符合条件，长度为6
最后返回最大长度6
字符串的个数最大到 5*10^5 |
l*********8
发帖数: 4642 | 2 带权有向图中找weight sum 最大的回路。 |
l*********8
发帖数: 4642 | 3 不对，还有这个条件：
找到的这组字符串的顺序不变，还是按照在初始数组的顺序排列
【在 l*********8 的大作中提到】
: 带权有向图中找weight sum 最大的回路。
|
q***y
发帖数: 236 | |
p*****2
发帖数: 21240 | 5
时间复杂度？
【在 q***y 的大作中提到】
: DFS 求和最大的路径
|
q***y
发帖数: 236 | 6 可以啊，建图的时候只保留有效地边。
【在 l*********8 的大作中提到】
: 不对，还有这个条件：
: 找到的这组字符串的顺序不变，还是按照在初始数组的顺序排列
|
p*****2
发帖数: 21240 | |
q***y
发帖数: 236 | 8 貌似要O(n^3)。太困了，明天再想。。
【在 p*****2 的大作中提到】
: 更新了一下。输入最大是5*10^5个字符串。
|
l*********8
发帖数: 4642 | 9 只有26个字母吗？
【在 p*****2 的大作中提到】
: 更新了一下。输入最大是5*10^5个字符串。
|
p*****2
发帖数: 21240 | 10
只有26个字母。不会有其他字符。
【在 l*********8 的大作中提到】
: 只有26个字母吗？
|
|
|
g***s
发帖数: 3811 | 11 任何一个字符串，只考虑它的第一个后最后一个字母。
设p(a,b) 为第一个字母是a，最后一个字母是b的字符串数目。
这样，扫描一遍就可以算出所有的p。p的空间是26×26.
后面怎么处理都不难了。
【在 p*****2 的大作中提到】
: 给你一个字符串数组，你需要发现符合如下规律的一组字符串，使得这组字符串的字符
: 总数最大化
: 1. 第一个字符串的第一个字符是最后一个字符串的最后一个字符
: 2. 每一个字符串的最后一个字符是下一个字符串的第一个字符
: 找到的这组字符串的顺序不变，还是按照在初始数组的顺序排列。
: 例如
: input
: 3
: abc
: ca
|
p*****2
发帖数: 21240 | 12
膜拜grass。真是太牛了。这题我想了一个多小时。
【在 g***s 的大作中提到】
: 任何一个字符串，只考虑它的第一个后最后一个字母。
: 设p(a,b) 为第一个字母是a，最后一个字母是b的字符串数目。
: 这样，扫描一遍就可以算出所有的p。p的空间是26×26.
: 后面怎么处理都不难了。
|
A**l
发帖数: 2650 | 13 赞简化问题的思维
【在 g***s 的大作中提到】
: 任何一个字符串，只考虑它的第一个后最后一个字母。
: 设p(a,b) 为第一个字母是a，最后一个字母是b的字符串数目。
: 这样，扫描一遍就可以算出所有的p。p的空间是26×26.
: 后面怎么处理都不难了。
|
l*********8
发帖数: 4642 | 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*********8
发帖数: 4642 | 15 你说的p(a,b)是从a到b的最长通路长度吧？
【在 g***s 的大作中提到】
: 任何一个字符串，只考虑它的第一个后最后一个字母。
: 设p(a,b) 为第一个字母是a，最后一个字母是b的字符串数目。
: 这样，扫描一遍就可以算出所有的p。p的空间是26×26.
: 后面怎么处理都不难了。
|
A**l
发帖数: 2650 | 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*********8
发帖数: 4642 | 17 复杂回路里面节点是可以重复的。
【在 A**l 的大作中提到】
: 好像有点问题
: 字母虽然只有26个，但是是可以重复使用的吧？
: abc
: cde
: efc
: cgh
: ha
: 这样c自己形成了环，不知道是不是合题意？
:
: ,
|
l*********8
发帖数: 4642 | 18 贴个程序。 直接在这里敲的，可能有问题：）
int longestCircle(vector &ss)
{
int len[26][26];
memset(len, 0, 26*26*sizeof(int));
int maxLen = 0;
for (int i=0; i
string &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 的大作中提到】
: 给你一个字符串数组，你需要发现符合如下规律的一组字符串，使得这组字符串的字符
: 总数最大化
: 1. 第一个字符串的第一个字符是最后一个字符串的最后一个字符
: 2. 每一个字符串的最后一个字符是下一个字符串的第一个字符
: 找到的这组字符串的顺序不变，还是按照在初始数组的顺序排列。
: 例如
: input
: 3
: abc
: ca
|
l*********8
发帖数: 4642 | 19 grass， 我越看越不明白你的p是什么意思。 能不能给个例子解释一下？
【在 g***s 的大作中提到】
: 任何一个字符串，只考虑它的第一个后最后一个字母。
: 设p(a,b) 为第一个字母是a，最后一个字母是b的字符串数目。
: 这样，扫描一遍就可以算出所有的p。p的空间是26×26.
: 后面怎么处理都不难了。
|
q***y
发帖数: 236 | 20 高人啊。膜拜。
【在 g***s 的大作中提到】
: 任何一个字符串，只考虑它的第一个后最后一个字母。
: 设p(a,b) 为第一个字母是a，最后一个字母是b的字符串数目。
: 这样，扫描一遍就可以算出所有的p。p的空间是26×26.
: 后面怎么处理都不难了。
|
|
|
l*********8
发帖数: 4642 | 21 我看不懂啊。看懂了麻烦解释一下吧，谢谢！
【在 q***y 的大作中提到】
: 高人啊。膜拜。
|
t*****j
发帖数: 1105 | 22 先预处理，把所有头字母和尾字母相同的的单词，只取最长单词，其他去掉。
这样最多总共有26×26种可能性。然后图论算最长环路。 |
l*********8
发帖数: 4642 | 23 "找到的这组字符串的顺序不变，还是按照在初始数组的顺序排列。"
变成图之后就没办法保持这种顺序了。
另外，以a开头以b结尾的字符串应该能出现多个。
【在 t*****j 的大作中提到】
: 先预处理，把所有头字母和尾字母相同的的单词，只取最长单词，其他去掉。
: 这样最多总共有26×26种可能性。然后图论算最长环路。
|
t*****j
发帖数: 1105 | 24 哦哦哦，没仔细看题，没看到这要求.......
【在 l*********8 的大作中提到】
: "找到的这组字符串的顺序不变，还是按照在初始数组的顺序排列。"
: 变成图之后就没办法保持这种顺序了。
: 另外，以a开头以b结尾的字符串应该能出现多个。
|
