Chro's Blog


同じ世界に、立っていたんだ。


「BZOJ 4044」「CERC2014」 Virus synthesis

  1. 1. Description
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. Solution

Description

Viruses are usually bad for your health. How about fighting them with… other viruses? In this problem, you need to find out how to synthesize such good viruses.

We have prepared for you a set of strings of the letters A, G, T and C. They correspond to the DNA nucleotide sequences of viruses that we want to svnthesize, using the following operations:

  • Adding a nucleotide either to the beginning or the end of the existing sequence
  • Replicating the sequence, reversing the copied piece, and gluing it either to the beginmng or to the end of the original (so that e.g., AGTC can become AGTCCTGA or CTGAAGTC).

We’re concerned about efficiency, since we have very many such sequences, some of them very long. Find a way to svnthesize them in a mmimum number of operations.

你要用ATGC四个字母用两种操作拼出给定的串:

  1. 将其中一个字符放在已有串开头或者结尾
  2. 将已有串复制,然后reverse,再接在已有串的头部或者尾部

一开始已有串为空。求最少操作次数。

len<=100000

Input

The first line of input contains the number of test cases T. The descriptions of the test cases follow:

Each test case consists of a single line containing a non-empty string. The string uses only the capital letters A, C, G and T and is not longer than 100 000 characters.

Output

For each test case, output a single line containing the minimum total number of operations necessary to construct the given sequence.

Sample Input

1
2
3
4
5
4
AAAA
AGCTTGCA
AAGGGGAAGGGGAA
AAACAGTCCTGACAAAAAAAAAAAAC

Sample Output

1
2
3
4
3
8
6
18

Solution

注意第二种操作,该操作后整个串会变成一个回文串,而且长度一定是偶数。

由于操作一只能给字符串增加 1 的长度,而操作二会使字符串长度翻倍,因此,最优方案一定有最多数目的字符是靠操作二添加的。

或者说,我们可以考虑最后一次操作二形成的回文子串,则剩下的字符都是一个一个暴力添加上去的。


所以,我们只要考虑每个回文子串是怎么构造的。

如果该回文子串长度为偶数,则最后一步一定是操作二(用反证法易证);此时有两种情况。第一种是外侧的两个字符是操作二前最后添加的;第二种是内侧两个字符是操作二前最后添加的。第一种情况,去掉两侧字符,剩下的化为另一个回文子串的问题(去掉两端加 1);第二种情况,取「小于一半长度的最长回文后缀」。如果操作二前最后的操作是「既向内又向外」,则视为「先向内后向外」,也就是当做第一种情形处理(一半长度减去该后缀长度)。

如果该回文子串长度为奇数,则最后一步不可能是操作二。所以去掉两端字符加 2。


对输入串构造一个回文自动机。用 trans[u] 表示节点 u 对应的回文子串的最长回文后缀(且长度小于一半)的那个节点。

「长度不超过一半」这个性质有点类似 NOI2014 的动物园那道题(但是那道题并不求长度,而是求个数),也是跑 fail 指针直到「能匹配回文后缀」且「长度不超过一半」为止。

最后是 DP 的顺序。很显然该顺序必须是……回文树上节点的 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
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
const int maxs = 4;
int n, T;
int next[maxn][maxs], fail[maxn];
int len[maxn], dp[maxn], last, tot;
int q[maxn], qh, qt, trans[maxn], ans;
char s[maxn];
int id(char c) {
if (c == 'A') return 0;
if (c == 'T') return 1;
if (c == 'C') return 2;
return 3;
}
int new_node() {
++tot;
memset(next[tot], 0, sizeof next[tot]);
fail[tot] = len[tot] = 0;
return tot;
}
void init() {
memset(next[0], 0, sizeof next[0]);
memset(next[1], 0, sizeof next[1]);
len[0] = last = 0;
fail[0] = fail[1] = tot = 1;
len[1] = -1;
}
void extend(int c, int n) {
int p = last;
while (s[n - len[p] - 1] != s[n]) p = fail[p];
if (!next[p][c]) {
int o = new_node();
len[o] = len[p] + 2;
int k = fail[p];
while (s[n - len[k] - 1] != s[n]) k = fail[k];
fail[o] = next[k][c];
next[p][c] = o;
if (len[o] <= 2) trans[o] = fail[o];
else {
int q = trans[p];
while (s[n - len[q] - 1] != s[n] || (len[q] + 2) * 2 > len[tot]) q = fail[q];
trans[o] = next[q][c];
}
}
last = next[p][c];
}
int main() {
for (scanf("%d", &T); T--; ) {
scanf("%s", s + 1);
n = strlen(s + 1);
init();
for (int i = 1; i <= n; ++i) extend(id(s[i]), i);
for (int i = 2; i <= tot; ++i) if (len[i] & 1) dp[i] = len[i];
ans = n;
qh = 0, qt = 0;
q[++qt] = 0, dp[0] = 1;
while (qh < qt) {
int u = q[++qh];
for (int c = 0; c < 4; ++c) {
int v = next[u][c];
if (!v) continue;
dp[v] = min(dp[u] + 1, len[v] / 2 - len[trans[v]] + dp[trans[v]] + 1);
ans = min(ans, n - len[v] + dp[v]);
q[++qt] = v;
}
}
printf("%d\n", ans);
}
return 0;
}
最近的文章

终章——我与 OI 的故事

2018-06-02:距离高考只有五天了。回想高三一年的经历、退役后的生活,感慨很多。当时这篇文章写得实在太烂太碎,我抽出了一点时间重写了一遍。 I. Coming to Shenyang2011 年的夏天,听父母说,在沈阳有一所很厉害的学校,叫东北育才。同时,还搞到了当时的几套入学试题。(虽然不知…

OI 继续阅读
更早的文章

NOI 2017 -- AFO

终于到了这一天。NOI 2017。 这大概是我的最后一次 OI 竞赛了吧。写点东西纪念一下。 每日更新。不偷懒。 7.17上午到了绍兴……绍兴北站人真多…… 磨叽磨叽到了学校,11 点 40 了…… 想着要快点去吃饭,结果报到现场人更多……555555555 颓几局 popkart 刷了点模板,结束…

OI 继续阅读