某岛

… : "…アッカリ~ン . .. . " .. .
June 15, 2012

Codeforces Round #124

Brief description:

Problem A. Lexicographically Maximum Subsequence
给定一个字符串,求重新排列这个字符串之后所能得到的字典序最大的串。(略。

Problem B. Infinite Maze
给定一个可平铺的迷宫,问出发点所在的区域是否是封闭的。(记录四维状态 BFS() 即可。。。卡步数 TLE 了两次。。

Problem C. Paint Tree
给定一颗树,和平面内一组点集,问是否存在一个对应关系使得,生成的平面图不产生交叉。

Problem D. The Next Good String
。Good String 定义为,不存在长度大于等于 d 的回文子串。给定一个字符串,求该子串的下一个 Good String 。

Problem E. Opening Portals
给定一个 n 个结点,m 条边无向带权图,选中其中 k 个结点作为传送门,
当一个传送门被点亮后,可以在其他已被点亮的传送门之间做无损传送。
问从 1 号结点出发,点亮所有传送门的最少代价。
( .. 1 ≤ k ≤ n ≤ 10^5, m ≤ 10^5 .. .)

Analysis:

Problem C. Paint Tree
。。总是有解。深搜一次得到 sz 数组。之后根据极角序递归构造即可。
。。想明白其实还是简单的一题。

Problem D. The Next Good String
。比赛的时候写了个深搜 TLE 了。。。赛后 Sevenkplus 告诉我就是普通的搜索。。。
于是跑去看了一下 7k+ 的代码。。

于是发现这里我的主要错误是没有注意到回文子串的递归性质。(如果存在一个长度为 x 的回文子串,则必然存在一个长度 x-2 的回文子串。。。

于是利用这个性质 bool illegal() 函数只需要判断 d 和 d+1 两个长度即可。。

bool illegal(int x){
    ++x; FOR_1(l, d, d+1){
        if (l > x) continue;
        int h1 = A[x] - A[x-l]*P[l], h2 = B[x] - B[x-l];
        if (h1*P[x-l] == h2) return true;
    }
    return false;
}

注意到这里的字符串 hash 需要一些技巧,以避免复杂的修改操作
(官方的题解里面这一步使用了树状数组来维护 Hash。。。

(貌似我的算法框架和官方题解一样。。分为两部。
。。先找到第一个要修改的位置。。随后再 dfs()。。
实际也可以直接 dfs() 。。(参见 Sevenkplus 的代码。。。

Problem E. Opening Portals
首先根据传送门的性质,如果所有点都是传送门的话那么结果就是该图的最小生成树。
对于只有其中 k 个结点是传送门的图,只要在原算法的基础上稍作修改即可。
具体,对每个点求出 P[i] 和 D[i] 。(表示距离这个点最近的传送门和其距离。。。
之后对每条边,再根据 D[x] + D[y] + w 作为关键字跑最小生成树。。

以上分别用一次多源 Dijkstra(),和稍作修改的 Kruskal() 即可。
(因此感觉编码难度上也要弱于 D 题。。。

Code:

A B C D E

External link:

http://codeforces.com/contest/196/room/4