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.

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

Please read the guidelines before commenting.


There are no comments at the moment.