比赛题解

C:括号
题目：
小A有一个只包含左右括号的字符串S.gif 。但他觉得这个字符串不够美观，因为它不是一个合法的括号串。一个合法的括号串是这样定义的：
1. ().gif 是合法的括号串
2. 若 A.gif 是合法的括号串，则(A).gif 则是合法的括号串
3. 若 A,B.gif 是合法的括号串，则 AB.gif 也是合法的括号串。
小A现在希望删掉 S.gif 中若干个字符，使得剩下的字符串是一个合法的括号串。小A想知道有多少不同的方案。两个方案是不同的，当且仅当他们删除的位置不同。比如当 S.gif 是 (().gif 时，有两种方案。分别是删掉第一个位置，或是删掉第二个位置。
解析：
这题的第一档部分分是暴力枚举删掉哪些括号，然后判断是否是合法的括号序列。这个可以使用栈来做，每次遇到一个右括号则弹出左括号，遇到左括号则加入栈中，不合法当且仅当最后有多余的左括号或中途不够左括号弹出。
可以发现只关心中间每一步有多少左括号。可以使用DP.gif 。设F[i][j].gif 表示考虑到第 i.gif 个位置，当前选取的子序列（或删剩的括号序列）结尾恰好为第i个位置。左括号数量为 j.gif 。那么可以枚举上一个位置i'.gif ,以及对应的左括号数量j'.gif 。因为i位置必须考虑，则若 i.gif 为右括号，则j=j'-1.gif ,否则j=j'+1.gif 。但要 j>=0.gif 。最后的答案就是 F[i][0].gif 的和。这个Dp.gif 的复杂度是O(n^3).gif 的。但是可以把i位置不选也加入转移，那么就是 F[i][j]->F[i+1][j'].gif 。复杂度 O(n^2).gif 。使用滚动数组优化空间即可。

D:配对
题目：
小A有n个长度都是L的字符串。这些字符串只包含前8个小写字符，'a'~'h'。但这些字符串非常的混乱，它们几乎长得互不相同。小A想通过一些规则，让它们长得尽可能相同。小A现在有K次机会，他可以每次机会，可以选择一对字符x,y，让x,y变成等价的字符（注意这里x,y和字符'x', 'y'不是一样的，只是个代号）。注意，等价关系是有传递性的。比如小A让'a'和'b'等价， 'b'和'c'等价，那么'a'和'c'等价。对于两个长度字符串P,Q是等价的，当且仅当对于每一位，P的字符和Q的字符都是等价的。小A希望你告诉他，要怎么利用好这K次机会（当然可以不用完），使得尽可能多对字符串是等价的。注意每对字符串只能算一次。
解析：
直接枚举选择哪些字母配对很慢，可以考虑枚举联通块。当K>7时，显然所有串都能相同了，因为只需要7条边就能让所有字母等价。因此考虑枚举字母的联通块情况。而贪心地想，K肯定用完最好，因此联通块情况就只有S(8,8-K)种情况，其中S为第二类斯特林数。枚举完联通块情况后，每个字符串中，每种字符替代为对应联通块编号，变成等价的字符串。然后计算哈希排序算等价对数。但这样可能超时。可以按字母分别维护每个字母出现位置的哈希值，重新算时复杂度是O(Σ)，而不是O(L)的。