【题解】bzoj#4044 [CERC2014]Virus Synthesis

初始有一个空串,利用下面的操作构造给定串 $\rm S$ 。

1、串开头或末尾加一个字符

2、串开头或末尾加一个该串的逆串

求最小化操作数, $\rm |S| \leq 10^5$。

dp是不可能会的,这辈子都不会了QAQ

首先预处理处上一篇 $blog$ 里的 $fail$ 和 $fail’$。

然后开始不会dp。发现对于PAM里每个状态 $x$,都可以由 $fail’(x)$ 推出。原因是 $fail’(x)$ 作为半失配指针(名字自己起的233),正好满足复制一遍的需求。于是考虑转移:

前半部分由于我们可以把加一个字符放到前面去执行,所以可以 $+1$ 而不用 $+2$ 。 后半部分由于半失配指针的最优性可以直接转移。

这样就做完了,考虑最后一定是一个长回文串加上一堆下脚料(原因是题目要求不能多串一起生成,只能维护一个回文串,所以不能把两个回文串拼起来之类的)。所以维护答案也很好维护。

按秩转移的话,bfs一遍就完了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
char S[MAXN] ;
queue <int> q ;
int N, C, ans, dp[MAXN] ;

struct PAM{
int val[300], vis[MAXN] ;
int rt0, rt1, sz, last, f[MAXN] ;
int trans[MAXN][4], fail[MAXN], len[MAXN] ;
void Init(){
sz = -1 ;
val['A'] = 0, val['C'] = 1,
val['G'] = 2, val['T'] = 3 ;
rt0 = ++ sz, rt1 = ++ sz ;
len[rt0] = 0, len[rt1] = -1 ;
fail[last = rt0] = fail[rt1] = rt1 ;
}
void Ins(int x, int pos){
int p = last, q, np, nq ;
while (S[pos] != S[pos - len[p] - 1]) p = fail[p] ;
if (!trans[p][x]){
np = ++ sz, q = fail[p] ;
while (S[pos] != S[pos - len[q] - 1]) q = fail[q] ;
len[np] = len[p] + 2, fail[np] = trans[q][x], trans[p][x] = np ;
nq = f[p] ; if (len[np] <= 2) f[np] = fail[np] ;
else {
while (S[pos] != S[pos - len[nq] - 1] || len[nq] + 2 > (len[np] >> 1))
nq = fail[nq] ; f[np] = trans[nq][x] ;
}
}
last = trans[p][x] ;
}
void bfs(){
dp[0] = 1, ans = N, q.push(0), vis[0] = 1 ;
while (!q.empty()){
int x = q.front() ; q.pop() ;
for (int i = 0 ; i <= 3 ; ++ i){
if (!trans[x][i]) continue ;
int y = trans[x][i] ; dp[y] = dp[x] + 1 ;
dp[y] = min(dp[y], dp[f[y]] + len[y] / 2 - len[f[y]] + 1) ;
ans = min(ans, dp[y] + N - len[y]) ; if (!vis[y]) q.push(y), vis[y] = 1 ;
}
}
for (int i = 0 ; i <= sz ; ++ i) vis[i] = 0 ;
}
}T ;
int main(){
cin >> C ;
while (C --){
scanf("%s", S + 1),
N = strlen(S + 1), T.Init() ;
for (int i = 1 ; i <= N ; ++ i)
T.Ins(T.val[(int)S[i]], i) ;
for (int i = 2 ; i <= T.sz ; ++ i) dp[i] = T.len[i] ;
// cout << ans << " " << T.sz << endl ;
T.bfs() ; printf("%d\n", ans) ; ans = 0 ;
for (int i = 0 ; i <= T.sz ; ++ i)
memset(T.trans[i], 0, sizeof(T.trans[i])) ;
}
}

dpdpdpdpdpdpdpdpdpdp不会不会不会不会好烦烦烦烦烦烦烦烦烦烦烦烦烦烦烦烦烦烦烦烦烦烦啊QAQ