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.
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