AC. 梦想

frank_c1

TopCoder SRM 696 (Div. 2)

发布于2016年08月12日 | 暂无评论 | 3,105阅读 | 比赛经历

有一场早上9点的TC,一定要好好珍惜哇。想想打大号最多也就涨一点rating,说不定还跌。听说TC第一次打rating涨的最多,于是萌生了打小号的念头,希望不要太惨。

于是时间来到了上午九点。开场看题,发现250pts是个模拟,有点细节,还坑了一会儿。500pts是个贪心,有点细节,也坑了一会儿。写完前两题就40min+了,一看排名rank 40+,这没指望啊…… 开1000pts,发现一言不和就来最大团,完了这东西我一次也没写过啊惨啊。而且题目奥妙重重数据范围奥妙重重根本不会做。zkx大爷提供了一个做法但我感觉15min写不完。于是最后10min弃疗打了一个裸暴力交上去。

结束后感觉很虚,500pts感觉要挂,1000pts就没想过能过。开测,这…… 我发现500pts真炸了,1000pts居然过了。由于1000pts的优势居然强行跻身rank 4,简直奥妙重重。后来发现自己500pts炸是因为数组开小了惨啊。

TC第一次打送rating果然慷慨,第一次就送了1690,好开心啊。

A. Ropestring

给定字符串s,仅包含'-'和'.'。一段连续的'-'称为绳子。现在要把所有绳子重新排列。要求两端绳子中间必须要有至少一个'.',且所有长度为偶数的绳子在长度为奇数的绳子前面。

1 \le |s| \le 50

模拟。注意细节。

B. Arrfix

给定长度为n的数列A,Bm个标签f_i

你可以使用一个标签f_k,将A_i变成f_k。所有标签须恰好使用一次,一个位置上至多使用一次标签。

求在贴完标签后,至少有多少i满足A_i \neq B_i

1 \le m \le n \le 50, 1 \le A_i, B_i \le 1000

贪心选取即可。注意细节。

C. Clicountingd2

给定一个n点简单无向图,没有重边和自环。

k条边没有确定是否存在。求所有2 ^ k种情况下图的最大团点数总和。

1 \le n \le 20, 0 \le k \le 20

其实我比赛时不会正解。

由于最大团朴素求复杂度比较高,考虑暴搜加剪枝。

枚举每一种边集的状态,求最大团即可。理论时间复杂度上界O(n ^ 2 2 ^ n 2 ^ k),不知为何能过……

[UPD 8.12] 学姐提供了一个巧妙的做法。按大小从大到小枚举最大团的点集S,求一下要使这个点集成为最大团至少需要加哪几条未确定的边,我们把这些边状压一下,设为c,则|S|可以来更新所有c的超集的答案。于是先在c上记录一下答案,最后取一下子集\max即可。时间复杂度O(n ^ 2 2 ^ n + n 2 ^ n)