Hướng dẫn giải của Đường đi trên cây
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 flashmt
const fi=''; fo=''; base=100000000; digit=8; type bignum=array[0..251] of longint; var num,re,cur,pre,t:bignum; st:ansistring; l,i:longint; procedure put(var x:bignum;y:longint); var i:longint; begin for i:=1 to x[0] do x[i]:=0; x[0]:=1; x[1]:=y; end; procedure plus(var c:bignum;a,b:bignum); var i,mem,max:longint; begin mem:=0; if a[0]>b[0] then max:=a[0] else max:=b[0]; for i:=1 to max do begin c[i]:=a[i]+b[i]+mem; if c[i]<base then mem:=0 else begin mem:=1; c[i]:=c[i] mod base; end; end; if mem>0 then begin max:=max+1; c[max]:=mem; end; c[0]:=max; end; procedure multi(var c:bignum;a:bignum;b:longint); var i,mem,max:longint; begin mem:=0; max:=a[0]; for i:=1 to max do begin c[i]:=a[i]*b+mem; if c[i]<base then mem:=0 else begin mem:=c[i] div base; c[i]:=c[i] mod base; end; end; if mem>0 then begin max:=max+1; c[max]:=mem; end; c[0]:=max; end; procedure mul(var c:bignum;a:bignum;b:longint); var i,mem,max:longint; begin mem:=0; max:=a[0]; for i:=1 to max do begin c[i]:=a[i] shl b+mem; if c[i]<base then mem:=0 else begin mem:=c[i] div base; c[i]:=c[i] mod base; end; end; if mem>0 then begin max:=max+1; c[max]:=mem; end; c[0]:=max; end; procedure pr(c:char); begin multi(pre,pre,3); if c<>'L' then begin plus(pre,pre,num); if c='R' then plus(pre,pre,num); end; plus(re,re,pre); end; procedure star; begin mul(re,re,2); multi(cur,pre,9); multi(t,num,3); plus(cur,cur,t); plus(num,num,t); plus(re,re,cur); plus(pre,pre,cur); end; procedure rf; var c:char; begin assign(input,fi); reset(input); read(st); l:=length(st); re[0]:=1; num[0]:=1; pre[0]:=1; put(re,1); put(num,1); put(pre,1); for i:=1 to l do begin if st[i]='S' then continue; if st[i]='*' then star else pr(st[i]); end; close(input); end; procedure wf; var i,j,t:longint; s:string; begin assign(output,fo); rewrite(output); for i:=re[0] downto 1 do begin if i<re[0] then begin str(re[i],s); t:=length(s); for j:=t+1 to digit do write(0); end; write(re[i]); end; close(output); end; begin rf; wf; end.
Code mẫu của RR
//Written by RR {$Mode objfpc} {$R-,Q-} uses math; const FINP = ''; FOUT = ''; MAXN = 2000; scs = 255; base = 100000000; lbase = 8; type big = array[0..scs] of longint; var res,now, sl,tmp : big; s : ansistring; f1,f2 : text; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; procedure inp; begin readln(f1,s); end; procedure add(a,b:big; var c:big); inline; var i,nho:longint; begin c[0]:=max(a[0],b[0]); nho:=0; for i:=1 to c[0] do begin c[i]:=a[i]+b[i]+nho; if c[i]<base then nho:=0 else begin dec(c[i],base); nho:=1; end; end; if nho=1 then begin inc(c[0]); c[c[0]]:=nho; end; end; procedure mul(a:big; k:longint; var c:big); inline; var i,nho:longint; begin c[0]:=a[0]; nho:=0; for i:=1 to c[0] do begin c[i]:=a[i]*k+nho; if c[i]<base then nho:=0 else begin nho:=c[i] div base; c[i]:=c[i] mod base; end; end; if nho>0 then begin inc(c[0]); c[c[0]]:=nho; end; end; procedure minus(a,b:big; var c:big); inline; var i,nho:longint; begin c[0]:=a[0]; nho:=0; for i:=1 to c[0] do begin c[i]:=a[i]-b[i]-nho; if c[i]>=0 then nho:=0 else begin inc(c[i],base); nho:=1; end; end; while (c[0]>0) and (c[c[0]]=0) do dec(c[0]); end; procedure print(var a:big); var i,u,cs,k:longint; begin if a[0]=0 then begin writeln(f2,0); exit; end; write(f2,a[a[0]]); for i:=a[0]-1 downto 1 do begin u:=a[i]; cs:=0; while u>0 do begin inc(cs); u:=u div 10; end; for k:=1 to lbase-cs do write(f2,'0'); write(f2,a[i]); end; writeln(f2); end; procedure solve; var i:longint; begin res[0]:=1; res[1]:=1; now:=res; sl:=res; for i:=1 to length(s) do case s[i] of 'S': begin end; 'L': begin mul(now,3,now); add(now,res,res); end; 'C': begin mul(now,3,now); add(now,sl,now); add(now,res,res); end; 'R': begin mul(now,3,now); add(now,sl,now); add(now,sl,now); add(now,res,res); end; '*': begin mul(res,4,res); minus(res,now,res); mul(sl,3,tmp); mul(sl,4,sl); mul(now,10,now); add(tmp,now,now); add(now,res,res); end; end; print(res); end; begin openF; inp; solve; closeF; end.
Code mẫu của hieult
#include <cstdio> #include <iostream> //#include <conio.h> #define base 100000000 using namespace std; struct solon { int so; long long a[500]; solon(){} solon(long long x){ so = 1; a[1] = x; } }; solon tong (solon A,solon B) { int du = 0; solon C; if(A.so<B.so) { C = A; A = B; B = C; } for(int i = B.so+1;i<=A.so;i++) B.a[i] = 0; C.so = A.so; for(int i = 1;i<=A.so;i++) { C.a[i] = (A.a[i]+B.a[i]+du)%base; du = (A.a[i]+B.a[i]+du)/base; } if(du>0) {C.so++; C.a[C.so] = du;} return C; } solon tichnho(solon A,long long k,int chuso) { solon C; long long du = 0; C.so = A.so+chuso; for(int i = 1;i<=chuso;i++) C.a[i] = 0; for(int i = chuso+1;i<=chuso+A.so;i++) { C.a[i] = (A.a[i-chuso]*k+du)%base; du = (A.a[i-chuso]*k+du)/base; } if(du>0) {C.so++; C.a[C.so] = du;} return C; } solon tich(solon A,solon B) { solon C; C.so = 1; C.a[1] = 0; for(int i = 1;i<=B.so;i++) { C = tong(C,tichnho(A,B.a[i],i-1)); } return C; } void print(solon A) { printf("%lld",A.a[A.so]); for(int i = A.so-1;i>=1;i--) printf("%08lld",A.a[i]); } solon KQ,run,T,cong,the,nhanh; char s[2222]; int main() { scanf("%s",s); KQ = solon(1); run = solon(1); nhanh = solon(1); for(int i = 0;i<strlen(s);i++){ if(s[i]=='L'){ run = tichnho(run,3,0); KQ = tong(KQ,run); } else if(s[i]=='C'){ run = tong(tichnho(run,3,0),nhanh); KQ = tong(KQ,run); } else if(s[i]=='R'){ run = tong(tichnho(run,3,0),tichnho(nhanh,2,0)); KQ = tong(KQ,run); } else if(s[i]=='*'){ the = run; run = tong(tichnho(run,9,0),tichnho(nhanh,3,0)); KQ = tong(tichnho(KQ,4,0),run); run = tong(run,the); nhanh = tichnho(nhanh,4,0); } //print(KQ); //printf("\n"); } print(KQ); //getch(); }
Bình luận