Editorial for Đường đi trên cây
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
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(); }
Comments