Hướng dẫn giải của Vần hoàn hảo


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của ladpro98

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
const int maxLen = 250050;
const int lim = 800000;
using namespace std;
int next[lim][26], min1[lim], min2[lim], prev[lim];
char s[lim][33], q[33];
int Peak, cnt, st[maxLen];

void Add(char *s, int t) {
    int pos = 1; char c; int n = strlen(s);
    if (min1[pos] == 0) min1[pos] = t; else
    if (min2[pos] == 0) min2[pos] = t;
    for(int i = n - 1; i >= 0; i--) {
        c = s[i] - 'a';
        if (next[pos][c] == 0)
            next[pos][c] = ++Peak;
        pos = next[pos][c];
        if (min1[pos] == 0) min1[pos] = t; else
        if (min2[pos] == 0) min2[pos] = t;
    }
}

int Find(char *s, int &pos) {
    int i, n = strlen(s); pos = 1;
    for(i = n - 1; i >= 0; i--) {
        char c = s[i] - 'a';
        if (next[pos][c] == 0) return i;
        prev[next[pos][c]] = pos;
        pos = next[pos][c];
    }
    return i;
}

inline bool cmp(const int &a, const int &b)
    {return strcmp(s[a], s[b]) < 0;}
inline bool uni(const int &a, const int &b) 
    {return strcmp(s[a], s[b]) == 0;}

int main()
{
    while (1) {
        cnt++;
        if (!gets(s[cnt])) break;
        if (!s[cnt][0]) break;
    }
    for(int i = 1; i < cnt; i++)
        st[i] = i;
    sort(st + 1, st + cnt, cmp);
    unique(st + 1, st + cnt, uni);
    Peak = 1;
    for(int i = 1; i < cnt; i++)
        Add(s[st[i]], st[i]);
    while (gets(q) && q[0]) {
        int node;
        int i = Find(q, node);
        if (i >= 0) puts(s[min1[node]]);
        else {
            if (strcmp(s[min1[node]], q) == 0) {
                int exact = min1[node];
                if (min2[node] != 0) puts(s[min2[node]]);
                else {
                    i = prev[node];
                    while (i) {
                        if (min1[i] != exact) {
                            puts(s[min1[i]]);
                            break;
                        }
                        else
                        if (min2[i] != 0) {
                            puts(s[min2[i]]);
                            break;
                        }
                        i = prev[i];
                    }
                }
            }
            else
                puts(s[min1[node]]);
        }
    }
    return 0;
}

Code mẫu của RR

{$R+,Q+}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=250011;
type
  st30=string[31];
var
  a:array[1..MAXN] of st30;
  f1,f2:text;
  n:longint;
  s:st30;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
procedure inp;
var
  s:st30;
  i:longint;
begin
  readln(f1,s); while pos(' ',s)>0 do delete(s,pos(' ',s),1);
  n:=0;
  fillchar(a,sizeof(a),0);
  while s<>'' do
    begin
      inc(n);
      for i:=length(s) downto 1 do
        a[n]:=a[n]+s[i];
      readln(f1,s);
      while pos(' ',s)>0 do delete(s,pos(' ',s),1);
    end;
end;
procedure swap(var a,b:st30);
var
  temp:st30;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure sort(l,r:longint);
var
  i,j:longint;
  mid:st30;
begin
  mid:=a[(l+r) div 2]; i:=l; j:=r;
  repeat
    while a[i]<mid do inc(i);
    while a[j]>mid do dec(j);
    if i<=j then
      begin
        swap(a[i],a[j]);
        inc(i); dec(j);
      end;
  until i>j;
  if i<r then sort(i,r);
  if l<j then sort(l,j);
end;
function find1(l,r:longint):longint;
var
  mid:longint;
begin
  if l>r then exit(0);
  if (a[l]>s) or (a[r]<s) then exit(0);
  if a[l]=s then exit(l);
  if a[r]=s then exit(r);
  mid:=(l+r) div 2;
  if a[mid]=s then exit(mid)
  else if a[mid]>s then exit(find1(l,mid-1))
  else exit(find1(mid+1,r));
end;
function find2(l,r:longint):longint;
var
  mid:longint;
begin
  if l>r then exit(0);
  if (a[l]<s) and (s<a[l+1]) then exit(l);
  if (a[r]<s) and (s<a[r+1]) then exit(r-1);
  mid:=(l+r) div 2;
  if (a[mid]<s) and (s<a[mid+1]) then exit(mid)
  else if a[mid]<s then exit(find2(mid+1,r))
  else exit(find2(l,mid-1));
end;
function comp(s1,s2:st30):longint;
var
  i,l1,l2:longint;
begin
  i:=1;
  l1:=length(s1);
  l2:=length(s2);
  while (i<=l1) and (i<=l2) and (s1[i]=s2[i]) do inc(i);
  comp:=i-1;
end;
function nhohon(a,b:st30):boolean;
var
  i,l,la,lb:longint;
begin
  nhohon:=true;
  la:=length(a); lb:=length(b);
  l:=max(la,lb);
  for i:=0 to l do
    if a[la-i]<b[lb-i] then exit
    else if a[la-i]>b[lb-i] then break;
  nhohon:=false;
end;
procedure work1(k,u:longint);
var
  i:longint;
  kq:st30;
begin
  kq:=a[u];
  for i:=u-1 downto 1 do
    begin
      if comp(a[i+1],a[i])<k then break;
      if nhohon(a[i],kq) then kq:=a[i];
    end;
  for i:=length(kq) downto 1 do write(f2,kq[i]);
  writeln(f2);
end;
procedure work2(k,u:longint);
var
  i:longint;
  kq:st30;
begin
  kq:=a[u];
  for i:=u+1 to n do
    begin
      if comp(a[i-1],a[i])<k then break;
      if nhohon(a[i],kq) then kq:=a[i];
    end;
  for i:=length(kq) downto 1 do write(f2,kq[i]);
  writeln(f2);
end;
procedure work3(k,u:longint);
var
  i:longint;
  kq:st30;
begin
  kq:=a[u+1];
  for i:=u+2 to n do
    begin
      if comp(a[i-1],a[i])<k then break;
      if nhohon(a[i],kq) then kq:=a[i];
    end;
  for i:=u-1 downto 1 do
    begin
      if comp(a[i+1],a[i])<k then break;
      if nhohon(a[i],kq) then kq:=a[i];
    end;
  for i:=length(kq) downto 1 do write(f2,kq[i]);
  writeln(f2);
end;
procedure work4(k,u:longint);
var
  i:longint;
  kq:st30;
begin
  kq:=a[u+1];
  for i:=u+2 to n do
    begin
      if comp(a[i-1],a[i])<k then break;
      if nhohon(a[i],kq) then kq:=a[i];
    end;
  for i:=u downto 1 do
    begin
      if comp(a[i+1],a[i])<k then break;
      if nhohon(a[i],kq) then kq:=a[i];
    end;
  for i:=length(kq) downto 1 do write(f2,kq[i]);
  writeln(f2);
end;
procedure reverse(var s:st30);
var
  i,l:longint;
  temp:st30;
begin
  temp:=s; l:=length(s);
  for i:=1 to l do
    s[i]:=temp[l-i+1];
end;
procedure ans;
var
  u,k1,k2:longint;
  ok:boolean;
begin
  while not eof(f1) do
    begin
      readln(f1,s);
      while pos(' ',s)>0 do delete(s,pos(' ',s),1);
      if s='' then break;
      reverse(s);
      u:=find1(1,n); ok:=true;
      if u=0 then begin ok:=false; u:=find2(1,n); end;
      if ok then
        begin
          if u=1 then k1:=0 else k1:=comp(a[u-1],s);
          if u=n then k2:=0 else k2:=comp(a[u+1],s);
          if k1>k2 then work1(k1,u-1)
          else if k2>k1 then work2(k2,u+1)
          else work3(k1,u);
        end
      else
        begin
          k1:=comp(a[u],s);
          if u=n then k2:=0 else k2:=comp(a[u+1],s);
          if k1>k2 then work1(k1,u)
          else if k2>k1 then work2(k2,u+1)
          else work4(k1,u);
        end;
    end;
end;
procedure refine;
var
  i,j:longint;
begin
  j:=1;
  for i:=2 to n do
  if a[i]>a[j] then
    begin
      inc(j);
      a[j]:=a[i];
    end;
  n:=j;
end;
begin
  openF;
  inp;
  sort(1,n);
  refine;
  a[n+1]:='zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz';
  ans;
  closeF;
end.

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.