Erdos Numbers

PC/UVa IDs: 110206/10044

分析:如果把一个作者看作一个顶点,若两个作者合作发表过一篇论文则对应的两点有一条边相连,那么一个作者的Erdos数就是该点到Erdos点的最短距离。在此图中从Erdos点开始宽度优先遍历即可得解。不过,此题真正困难之处并不在此, 继续阅读

Common Permutation

PC/UVa IDs: 110303/10252

分析:本题只要求得到一个字符串x,使得x的某两个排列分别是两个给定字符串的子串,并没有要求x的某一个排列同时是两个给定字符串的子串。理解清楚这一点非常重要——如果题目要求是后者,则问题就演变成了求两个字符串的最长(非连续的)公共子序列(LCS)的问题,难度陡升。 继续阅读