题目大意：字符集大小为m，给出一个长度为n字符串S，问有多少个长度为n的字符串T，使得S和T的LCS长度为n-1。
标准做法是DP套DP的状压DP，然而太烦了不想写。在官方题解的讨论里找到了一个简单很多的非DP做法，不想翻译了自己看吧。
I think there's a simpler solution to 1D without DP (the hard part is verifying that it's valid, I suppose, but this follows from a small bit of case analysis).We want the number of strings other than S which can result from removing one character and adding one. First, we block the string S into groups of consecutive equal characters. Removing a character from any part of one group is equivalent, so if there are k groups, we consider each of these k possibilities. Suppose we've taken from a group with size g and character c; you can add back any color in any place, except you can't add back c adjacent to any of the g - 1 remaining c's in the group (or you would get S back). Also, for each other group with size h and color d, we overcount the number of ways to add another d into this group by h, so the total number of valid distinct ways to add a character to S with one of the k groups diminished is nm - n (since n is the sum of the sizes of all of the groups).So our total answer would be k(mn - n), except a few of the strings T are double counted. It turns out that the only way to double count T is if there is some substring ab...aba in S (alternating different letters of some length ≥ 2) which becomes replaced by ba...bab (see if you can see the two ways to make this transformation). Thus the final answer isk(mn-n)-Number of alternating substrings of length at least 2which runs in O(n) pretty easily.
代码在此。
评论 (0)
