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.

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

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.