首页 > 代码库 > Codeforces Round #244 (Div. 2)
Codeforces Round #244 (Div. 2)
A. Police Recruits
B. Prison Transfer
A，B两个是水题。
C. Checkposts
DFS找出所有的环就行了。
每次搜索一个结点u时，给u加一个递增标号low[u]，同时记录搜索u及u的子结点过程中遇到的最小标号minc，也就是当搜索u的子结点v时，minc = min(minc, low[v])。搜索完成后，如果minc < low[u]，说明搜索u的子结点时又回到了u的父结点，也就是说u在一个环中，然后求出这个环的最小费用及取到最小费用的结点数。
D. Match & Catch
首先把原问题转换一下：
对于位于字符串str1和str2的两个位置p（str1中）和q（str2中）：记suffix(p)和str1的LCS长度为len1，suffix(q)和str2的LCS长度为len2，suffix(p)和suffix(q)的LCS长度为len。其中suffix(i)表示从位置i开头的后缀，LCS是最长公共子串，那么题目要求的就是满足条件len > max(len1, len2)的最小的max(len1, len2)。取答案为ans = max(len1, len2) + 1，那么子串(p..p+ans-1)在str1中惟一，因为不惟一的最长子串长度为ans - 1。同样q也惟一。同时(p..p+ans-1)是str1和str2的公共子串（它是suffix(p)和suffix(q)的公共子串）。所以原问题就变成了一个纯后缀数组题目。
E. Police Patrol
不知道为什么把这个题放在最后一题，感觉完全是个水题。。。。
<script src="https://code.csdn.net/snippets/324460.js" type="text/javascript"></script>
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。