【cf666X】 Codeforces Round #349 (Div. 1)

2016年5月1日9370

A. Reberland Linguistics

此题最重要的是理解题意!!!

英语渣伤不起

给定一个字符串,先去掉一个长度至少为5的前缀,要求把剩下的字符串划分成长度为2或3的串,这些串相邻之间不能完全相同,问可能有哪些长度为2或3的串

看错题意就写了个哈希+搜索一直wa,后来领悟了就没另起炉灶,改成了牵强的记搜

大概和dp差不多意思,f[i][0/1]表示前i个字符,最后一个串长度为2/3是否可行,转移显然。。。

B. World Tour

给定一张边权为1的有向图,求四个不同点A, B, C, D

使得dis(A, B) + dis(B, C) + dis(C, D)取最大值

先bfs出任意两点的距离,f(i, 0-2)表示从i出发的最远的三个点,g(i, 0-2)表示到i的最远的三个点

枚举B和C,再枚举3 * 3个点对,选出最优的A和D

保留三个点的原因是保证A, B, C, D互不相同

复杂度n^2