Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

pascal 题解

Posted by zhouzixuan at 2013-02-16 21:56:10 on Problem 3294
var
  n,m,l,r,mid:longint;
  s:ansistring;
  once:boolean;
  sa,rank,key1,key2,height,belong:array [1..300000] of longint;
  v:array [0..1001] of boolean;
procedure init;
var
  i,j,k:longint;
  s1:ansistring;
begin
  n:=0; s:=''; k:=0;
  readln(m); l:=1; r:=0;
  if m=0 then halt;
  for i:=1 to m do
  begin
    readln(s1); if length(s1)>r then r:=length(s1);
    for j:=1 to length(s1) do begin s1[j]:=chr(ord(s1[j])+10); belong[n+j]:=i; end;
    inc(k); s1:=s1+chr(k); belong[n+length(s1)]:=0;
    s:=s+s1; n:=n+length(s1);
  end;
  for i:=1 to n do rank[i]:=ord(s[i]);
end;
procedure qsort(x,y:longint);
var
  p,q,mid1,mid2,t:longint;
begin
  p:=x;
  q:=y;
  mid1:=key1[(x+y) div 2];
  mid2:=key2[(x+y) div 2];
  repeat
    while (key1[x]<mid1) or ((key1[x]=mid1) and (key2[x]<mid2)) do inc(x);
    while (key1[y]>mid1) or ((key1[y]=mid1) and (key2[y]>mid2)) do dec(y);
    if x<=y then
    begin
      t:=key1[x]; key1[x]:=key1[y]; key1[y]:=t;
      t:=key2[x]; key2[x]:=key2[y]; key2[y]:=t;
      t:=sa[x]; sa[x]:=sa[y]; sa[y]:=t;
      inc(x); dec(y);
    end;
  until x>y;
  if x<q then qsort(x,q);
  if p<y then qsort(p,y);
end;
procedure suffix_array;
var
  i,tot,p:longint;
begin
  p:=1;
  while p<n do
  begin
    for i:=1 to n do key1[i]:=rank[i];
    for i:=1 to n do key2[i]:=rank[i+p];
    for i:=1 to n do sa[i]:=i;
    qsort(1,n); rank[sa[1]]:=1; tot:=1;
    for i:=2 to n do
    begin
      if (key1[i]<>key1[i-1]) or (key2[i]<>key2[i-1]) then inc(tot);
      rank[sa[i]]:=tot;
    end;
    if tot=n then break;
    p:=p*2;
  end;
  for i:=1 to n do rank[sa[i]]:=i;
end;
procedure make_height;
var
  i,j,h:longint;
begin
  h:=0;
  for i:=1 to n do
  begin
    if rank[i]=1 then begin height[1]:=0; continue; end;
    j:=sa[rank[i]-1];
    while s[i+h]=s[j+h] do inc(h);
    height[rank[i]]:=h;
    if h>0 then dec(h);
  end;
end;
function ok(x:longint):boolean;
var
  i,j,k,tot:longint;
begin
  fillchar(v,sizeof(v),false);
  v[0]:=true; tot:=0;
  for i:=2 to n do
  begin
    if height[i]<x then
    begin
      fillchar(v,sizeof(v),false); v[0]:=true; tot:=0; continue;
    end;
    if v[belong[sa[i]]]=false then
    begin
      v[belong[sa[i]]]:=true;
      inc(tot);
    end;
    if v[belong[sa[i-1]]]=false then
    begin
      v[belong[sa[i-1]]]:=true;
      inc(tot);
    end;
    if tot>m div 2 then exit(true);
  end;
  exit(false);
end;
procedure print(x:longint);
var
  i,j,k,tot:longint;
  flag:boolean;
begin
  fillchar(v,sizeof(v),false);
  v[0]:=true; tot:=0; flag:=true;
  for i:=2 to n do
  begin
    if height[i]<x then
    begin
      fillchar(v,sizeof(v),false); v[0]:=true; tot:=0; flag:=true; continue;
    end;
    if v[belong[sa[i]]]=false then
    begin
      v[belong[sa[i]]]:=true;
      inc(tot);
    end;
    if v[belong[sa[i-1]]]=false then
    begin
      v[belong[sa[i-1]]]:=true;
      inc(tot);
    end;
    if (tot>m div 2) and flag then
    begin
      for j:=sa[i-1] to sa[i-1]+x-1 do write(chr(ord(s[j])-10));
      writeln;
      flag:=false;
    end;
  end;
end;
procedure main;
var
  ans:longint;
begin
  ans:=0;
  while l<=r do
  begin
    mid:=(l+r) div 2;
    if ok(mid) then begin ans:=mid; l:=mid+1; end
    else r:=mid-1;
  end;
  if ans<>0 then print(ans)
  else writeln('?');
end;
begin
  once:=false;
  while true do
  begin
    init;
    if once then writeln;
    once:=true;
    suffix_array;
    make_height;
    main;
  end;
end.

把数组从500000变成1000就AC 原来TLE...

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator