bzoj3790

观察发现，这道题目其实就相当于一个最小区间覆盖问题
这里的区间是指以每个点为中心的最长回文串
很久没写manacher，有点感动
不得不说manacher是一个非常好的算法
  1 var s:array[0..100010] of char;
  2     c,l,r,f,p:array[0..100010] of longint;
  3     i,j,t,n,m,ans,k,right:longint;
  4     ch:char;
  5 
  6 procedure swap(var a,b:longint);
  7   var c:longint;
  8   begin
  9     c:=a;
 10     a:=b;
 11     b:=c;
 12   end;
 13 
 14 function min(a,b:longint):longint;
 15   begin
 16     if a>b then exit(b) else exit(a);
 17   end;
 18 
 19 function lowbit(x:longint):longint;
 20   begin
 21     exit(x and (-x));
 22   end;
 23 
 24 procedure sort(ll,rr: longint);
 25   var i,j,x,y: longint;
 26   begin
 27     i:=ll;
 28     j:=rr;
 29     x:=r[(ll+rr) shr 1];
 30     y:=l[(ll+rr) shr 1];
 31     repeat
 32       while (r[i]<x) or (r[i]=x) and (l[i]<y) do inc(i);
 33       while (x<r[j]) or (r[j]=x) and (y<l[j]) do dec(j);
 34       if not(i>j) then
 35       begin
 36         swap(r[i],r[j]);
 37         swap(l[i],l[j]);
 38         inc(i);
 39         j:=j-1;
 40       end;
 41     until i>j;
 42     if ll<j then sort(ll,j);
 43     if i<rr then sort(i,rr);
 44   end;
 45 
 46 function ask(x:longint):longint;
 47   begin
 48     if x=0 then exit(0);
 49     ask:=n+1;
 50     while x<=n do  //因为求的是后缀最小值，事实上只要将查询和修改的范围换一下即可
 51     begin
 52       ask:=min(ask,c[x]);
 53       x:=x+lowbit(x);
 54     end;
 55   end;
 56 
 57 procedure add(i:longint);
 58   var x:longint;
 59   begin
 60     x:=r[i];
 61     while x>0 do
 62     begin
 63       c[x]:=min(c[x],f[i]);
 64       x:=x-lowbit(x);
 65     end;
 66   end;
 67 
 68 begin
 69   while true do
 70   begin
 71     read(ch);
 72     if not((ch>='a') and (ch<='z')) then break;
 73     s[0]:='$';
 74     s[1]:='#';
 75     m:=1;
 76     n:=0;
 77     while (ch>='a') and (ch<='z') do
 78     begin
 79       inc(n);
 80       inc(m);
 81       s[m]:=ch;
 82       inc(m);
 83       s[m]:='#'; //将回文串的奇偶转化为一种情况
 84       read(ch);
 85     end;
 86     s[m+1]:=' ';
 87     readln;
 88     k:=0;
 89     right:=0;
 90     t:=0;
 91     fillchar(p,sizeof(p),0);
 92     for i:=1 to m do
 93     begin
 94       if right>i then   //manacher的核心
 95         p[i]:=min(p[2*k-i],right-i)
 96       else p[i]:=1;
 97       while s[i+p[i]]=s[i-p[i]] do inc(p[i]);
 98       if p[i]+i>right then
 99       begin
100         right:=p[i]+i;
101         k:=i;
102       end;
103       if (s[i]='#') and (p[i]=1) then continue
104       else begin
105         inc(t);
106         l[t]:=(i-p[i]+2) div 2;
107         r[t]:=(i+p[i]-2) div 2;
108       end;
109     end;
110     sort(1,t);  //解决区间覆盖问题，右端点排序
111     ans:=n;
112     for i:=1 to n do
113       c[i]:=n+1;
114     for i:=1 to t do
115     begin
116       f[i]:=ask(l[i]-1)+1; //以前这个问题我都是用单调队列的，这里写了树状数组，更简明
117       if r[i]=n then ans:=min(ans,f[i]);
118       add(i);
119     end;
120     writeln(ans-1);
121   end;
122 end.
View Code