【BZOJ3790】神奇项链（manacher，树状数组）

题意：

思路：生成一些回文拼起来使生成的段数最小

显然存在一种最优的方案，使生成的那些回文是目标串的极长回文子串

求出对于每个位置的最长回文子串，问题就转化成了：

给定一些已知起始和终止位置的线段，求覆盖住整个区域的最小线段数量

这个可以BIT做，求当前已经覆盖的区域最远能拓展到哪里

也可以预处理一下前缀最小值，跳转时直接调用即可

 const oo=;

 var t,a,x,y,p:array[..]of longint;

     len,n,i,id,mx,ans,m:longint;

     ch:ansistring;

 function lowbit(x:longint):longint;

 begin

  exit(x and (-x));

 end;

 function max(x,y:longint):longint;

 begin

  if x>y then exit(x);

  exit(y);

 end;

 function min(x,y:longint):longint;

 begin

  if x<y then exit(x);

  exit(y);

 end;

 procedure update(x,y:longint);

 begin

  while x<=n- do

  begin

   t[x]:=max(t[x],y);

   x:=x+lowbit(x);

  end;

 end;

 function query(x:longint):longint;

 begin

  query:=-oo;

  while x> do

  begin

   query:=max(query,t[x]);

   x:=x-lowbit(x);

  end;

 end;

 begin

  assign(input,'bzoj3790.in'); reset(input);

  assign(output,'bzoj3790.out'); rewrite(output);

  while not eof do

  begin

   readln(ch);

   len:=length(ch);

   if len= then break;

   fillchar(a,sizeof(a),);

   fillchar(p,sizeof(p),);

   n:=; a[]:=; a[]:=;

   for i:= to len do

   begin

    inc(n); a[n]:=ord(ch[i])-ord('a')+;

    inc(n); a[n]:=;

   end;

   inc(n); a[n]:=;

   mx:=; id:=;

   for i:= to n- do

   begin

    if mx>i then p[i]:=min(p[id*-i],mx-i)

     else p[i]:=;

    while a[i-p[i]]=a[i+p[i]] do inc(p[i]);

    if p[i]+i>mx then

    begin

     mx:=p[i]+i; id:=i;

    end;

   end;

   for i:= to m do

   begin

    x[i]:=; y[i]:=;

   end;

   m:=;

   for i:= to n- do

   begin

    inc(m); x[m]:=i-p[i]; y[m]:=i+p[i]-;

   end;

   fillchar(t,sizeof(t),);

   for i:= to m do update(x[i],y[i]);

   i:=; ans:=;

   while i<n- do

   begin

    i:=query(i+);

    inc(ans);

   end;

   writeln(ans-);

  end;

  close(input);

  close(output);

 end.

巴特西

【BZOJ3790】神奇项链（manacher，树状数组）

最新文章

热门文章