JZOJ4387. 【GDOI2016模擬3.15】基因合成

NO IMAGE

題目大意

一共有TT組詢問,每組詢問一個只包含ACGT的字串,求通過以下兩種操作,最少能得到該串的操作次數。

  • 將當前串翻轉後接到原串中
  • 在當前串首或串尾加入一個字元

Data Constraint
對於100%的資料:T≤10,|S|≤105 T \leq 10 , |S| \leq 10^5

題解

可以注意到操作中有一個翻轉,每次操作完以後必然是一個迴文串。可以發現目標串必然是由一個迴文串(可能為空)再直接首尾新增字元得來。如果我們求出目標串中每一個迴文串的最少操作次數,就可以得出答案了。這裡可以用迴文樹來處理。
設f[i]f[i]表示迴文樹上的第ii個節點的迴文串最少需要的操作次數,然後就可以轉移了。比較顯然的是,奇數長度的迴文串並不會對答案造成影響(奇數迴文串必能由偶數迴文串得來,而且無法翻轉得來)。而偶數迴文串可以由他的父親節點增加一對字元得來,這只需要 1次操作(因為可以先新增字元再翻轉),或者可以由他的某個長度小於其一半的字尾轉移來(語文功底有限所以比較繞 = = 詳見程式)
然後直接列舉選擇某個迴文串,求最小值就是答案。

SRC

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std ;
#define N 100000   10
struct Tree {
int Son[4] ;
int cost , len , fail ;
} T[N] ;
char S[N] ;
int Tab[N] ;
int Test , Last , L , tot , ans ;
int Find( int now , int half ) {
while ( T[now].len > half ) now = T[now].fail ;
return now ;
}
int Getfail( int now ) {
while ( S[L-T[now].len-1] != S[L] ) now = T[now].fail ;
return now ;
}
void ADD( int c ) {
L    ;
int now = Getfail( Last ) ;
if ( !T[now].Son[c] ) {
T[  tot].fail = T[Getfail(T[now].fail)].Son[c] ;
T[now].Son[c] = tot ;
T[tot].len = T[now].len   2 ;
if ( (T[tot].len & 1) == 0 ) {
int j = Find( T[tot].fail , T[tot].len / 2 ) ;
T[tot].cost = min( T[now].cost   1 , T[j].cost   T[tot].len / 2 - T[j].len   1 ) ;
} else T[tot].cost = T[tot].len ;
}
Last = T[now].Son[c] ;
}
int main() {
freopen( "gene.in" , "r" , stdin ) ;
freopen( "gene.out" , "w" , stdout ) ;
scanf( "%d" , &Test ) ;
Tab['A'] = 0 , Tab['C'] = 1 , Tab['G'] = 2 , Tab['T'] = 3 ;
while ( Test -- ) {
memset( T , 0 , sizeof(T) ) ;
T[0].fail = T[0].cost = 1 ;
T[1].len = -1 , T[1].cost = 2 ;
Last = S[0] = 0 ;
tot = 1 , L = 0 ;
scanf( "%s" , S   1 ) ;
ans = strlen( S   1 ) ;
for (int i = 1 ; i <= ans ; i    )
ADD( Tab[S[i]] ) ;
for (int i = 2 ; i <= tot ; i    ) ans = min( ans , T[i].cost   L - T[i].len ) ;
printf( "%d\n" , ans ) ;
}
return 0 ;
}

以上.