Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1

Danh tiếng các thành viên

HạngThành viênĐiểm
1mr_invincible+213
2conankudo+149
3khuc_tuan+137
4tuananhnb93+129
5khanhptnk+108
6hphong+103
7flash_mt+99
8paulmcvn+71
9technolt+70
10hoangle+63

Topcoder Vietnam

HạngThành viênĐiểm
Diễn đàn
Forum
Trả lời: COIN34 (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 0
  • Trang:
  • << < 1 2 > >>
CHỦ ĐỀ - Trả lời: COIN34
#48740
ngmq (Thành viên)
Biết code binary-indexed tree
Bài viết: 42
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: COIN34 9 năm, 6 tháng trước   (+0)
bài này làm theo cách ghép cặp độ phức tạp 20*(2^20) + testcase*(2^20) là TLE.

Nếu làm theo ghép cặp thì có trick nào không nhỉ, đây là đoạn sinh tổ hợp của mình

Code:
 
/*
 
Tm : struct tap thu nhat ( 20 phan tu )
  Tm.m : gia tri cua 1 to hop
  Tm.xm : so phan tu tao ra tong Tm.m do
Tn : struc tap thu hai ( 14 phan tu )
  Tm.n : gia tri cua 1 to hop
  Tm.xn : so phan tu tao ra tong Tn.n do
 
*/
 
#define T 34
#define T1 20
#define T2 14
inline void init()
  a[0] = 2;
  a[1] = 3;
  a[2] = 5;
  FOR(i,3,T)
    a[i] = a[i-1] + a[i-2] + a[i-3];
 
  FOR(i,0,1<<T1){// tap 1 : co 2^20 trang thai
    FOR(j,0,T1){// gom 20 phan tu dau tien
      if(i & (1<<j)){// neu bit j trong i la 1
        Tm[i].m += a[j];
        Tm[i].xm++;// so dong xu tao ra tong m[i] tang len 1
      }
    }
    
  }
  
  FOR(i,0,1<<T2) {// tap 2 : co 2^14 trang thai
    FOR(j,T1,T) {// gom 14 phan tu tiep theo
      if(i & (1<<(j-T1))){
        Tn[i].n += a[j];
        Tn[i].xn++; // so dong xu tao ra tong n[i] tang len 1
      }
    }
  }
}
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#55246
giahuynd (Thành viên)
giahuynd-
Super fast coder
Bài viết: 58
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: COIN34 9 năm, 3 tháng trước   (+0)
bài này chia đôi có ac được không vậy mấy anh?
đây là code của e theo chia đội mà cứ bị tle hoài,ai có thể nói rõ cách tham lam không ạ?
Code:
 
const fi='';
      fo='';
type tong=array[1..1048576] of longint;
     tong2=array[1..1048576] of byte;
var f1,f2:text;
    sum,sum2:tong;
    count,count2:tong2;
    a:array[1..34] of longint;
    x,i,s,sl,sl2,dem,kq,n,t:longint;
 
function max(a,b:longint):longint;
begin
 if a>b then max:=a else max:=b;
end;
procedure sinh;INLINE;
begin
 inc(sl);
 sum[sl]:=s;
 count[sl]:=dem;
end;
procedure tryS(i,k:byte);
var j:byte;
begin
 for j:=0 to 1 do
  begin
   s:=s+a[i]*j;
   if j=1 then inc(dem);
   if i=k then sinh else tryS(i+1,k);
   if j=1 then dec(dem);
   s:=s-a[i]*j;
  end;
end;
procedure swap1(var a,b:longint);
var tmp:longint;
begin
 tmp:=a;
 a:=b;
 b:=tmp;
end;
procedure swap2(var a,b:byte);
var tmp:byte;
begin
 tmp:=a;
 a:=b;
 b:=tmp;
end;
procedure quicksort(l,h:longint);  INLINE;
var x:longint;
    i,j:longint;
begin
 i:=l;
 j:=h;
 x:=sum2[l+random(h-l+1)];
 repeat
  while sum2[i]<x do inc(i);
  while sum2[j]>x do dec(j);
  if i<=j then
    begin
     swap1(sum2[i],sum2[j]);
     swap2(count2[i],count2[j]);
     inc(i);
     dec(j);
    end;
 until i>j;
 if j>l then quicksort(l,j);
 if i<h then quicksort(i,h);
end;
procedure process;
begin
 a[1]:=2;
 a[2]:=3;
 a[3]:=5;
 for i:=4 to 34 do begin a[i]:=a[i-3]+a[i-2]+a[i-1];end;
 sl:=0;
 tryS(1,20);
 sum2:=sum;
 count2:=count;
 sl2:=sl;
 quicksort(1,sl2);
 fillchar(sum,sizeof(sum),0);
 fillchar(count,sizeof(count),0);
 sl:=0;
 tryS(21,34);
end;
procedure tknp;   
var dau,cuoi,mid,k,node:longint;
begin
 kq:=-1;
 for i:=1 to sl do
  begin
   k:=x-sum[i];
   dau:=1;
   cuoi:=sl2;
   while dau<=cuoi do
    begin
       mid:=(dau+cuoi)div 2;
       if sum2[mid]=k then
          begin
            kq:=max(kq,count[i]+count2[mid]);
            node:=mid-1;
               while sum2[node]=k do
                begin
                   kq:=max(kq,count[i]+count2[node]);
                   dec(node);
                   if node =0 then break;
                end;
             node:=mid+1;
               while sum2[node]=k do
                begin
                  kq:=max(kq,count[i]+count2[node]);
                  inc(node);
                  if node=sl2+1 then break;
                end;
            break;
          end
       else if sum2[mid]>k then cuoi:=mid-1
       else dau:=mid+1;
      end;
   end;
end;
BEGIN
 assign(f1,fi);
 reset(f1);
 readln(f1,n);
 assign(f2,fo);
 rewrite(f2);
 process;
 for t:=1 to n do
  begin
   readln(f1,x);
   tknp;
   writeln(f2,'Case #',t,': ',kq);
  end;
 close(f1);
 close(f2);
END.
 
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#55248
haplinhavxt (Thành viên)
hhiepit_k52+16
Nhắm mắt code không bug
Bài viết: 180
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: COIN34 9 năm, 3 tháng trước   (+0)
giahuynd viết:
QUOTE:
bài này chia đôi có ac được không vậy mấy anh?
đây là code của e theo chia đội mà cứ bị tle hoài,ai có thể nói rõ cách tham lam không ạ?
Code:
 
const fi='';
      fo='';
type tong=array[1..1048576] of longint;
     tong2=array[1..1048576] of byte;
var f1,f2:text;
    sum,sum2:tong;
    count,count2:tong2;
    a:array[1..34] of longint;
    x,i,s,sl,sl2,dem,kq,n,t:longint;
 
function max(a,b:longint):longint;
begin
 if a>b then max:=a else max:=b;
end;
procedure sinh;INLINE;
begin
 inc(sl);
 sum[sl]:=s;
 count[sl]:=dem;
end;
procedure tryS(i,k:byte);
var j:byte;
begin
 for j:=0 to 1 do
  begin
   s:=s+a[i]*j;
   if j=1 then inc(dem);
   if i=k then sinh else tryS(i+1,k);
   if j=1 then dec(dem);
   s:=s-a[i]*j;
  end;
end;
procedure swap1(var a,b:longint);
var tmp:longint;
begin
 tmp:=a;
 a:=b;
 b:=tmp;
end;
procedure swap2(var a,b:byte);
var tmp:byte;
begin
 tmp:=a;
 a:=b;
 b:=tmp;
end;
procedure quicksort(l,h:longint);  INLINE;
var x:longint;
    i,j:longint;
begin
 i:=l;
 j:=h;
 x:=sum2[l+random(h-l+1)];
 repeat
  while sum2[i]<x do inc(i);
  while sum2[j]>x do dec(j);
  if i<=j then
    begin
     swap1(sum2[i],sum2[j]);
     swap2(count2[i],count2[j]);
     inc(i);
     dec(j);
    end;
 until i>j;
 if j>l then quicksort(l,j);
 if i<h then quicksort(i,h);
end;
procedure process;
begin
 a[1]:=2;
 a[2]:=3;
 a[3]:=5;
 for i:=4 to 34 do begin a[i]:=a[i-3]+a[i-2]+a[i-1];end;
 sl:=0;
 tryS(1,20);
 sum2:=sum;
 count2:=count;
 sl2:=sl;
 quicksort(1,sl2);
 fillchar(sum,sizeof(sum),0);
 fillchar(count,sizeof(count),0);
 sl:=0;
 tryS(21,34);
end;
procedure tknp;   
var dau,cuoi,mid,k,node:longint;
begin
 kq:=-1;
 for i:=1 to sl do
  begin
   k:=x-sum[i];
   dau:=1;
   cuoi:=sl2;
   while dau<=cuoi do
    begin
       mid:=(dau+cuoi)div 2;
       if sum2[mid]=k then
          begin
            kq:=max(kq,count[i]+count2[mid]);
            node:=mid-1;
               while sum2[node]=k do
                begin
                   kq:=max(kq,count[i]+count2[node]);
                   dec(node);
                   if node =0 then break;
                end;
             node:=mid+1;
               while sum2[node]=k do
                begin
                  kq:=max(kq,count[i]+count2[node]);
                  inc(node);
                  if node=sl2+1 then break;
                end;
            break;
          end
       else if sum2[mid]>k then cuoi:=mid-1
       else dau:=mid+1;
      end;
   end;
end;
BEGIN
 assign(f1,fi);
 reset(f1);
 readln(f1,n);
 assign(f2,fo);
 rewrite(f2);
 process;
 for t:=1 to n do
  begin
   readln(f1,x);
   tknp;
   writeln(f2,'Case #',t,': ',kq);
  end;
 close(f1);
 close(f2);
END.
 
Cách làm bài này như bạn lion_it đã viết ở bên dưới!
 
Đã lưu IP Đã lưu IP  
 
'+' cho em đi nào!
  Đã khóa chức năng gửi bài.
#55295
LIKIA (Thành viên)
silver_arrow+12
Đã code là AC
Bài viết: 90
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: COIN34 9 năm, 3 tháng trước   (+0)
Bài này không cần tìm kiếm nhị phân đâu bạn ah. Bạn có thể tìm được k ở mảng sum2 trong O(1) mà
 
Đã lưu IP Đã lưu IP  
 
  Đã khóa chức năng gửi bài.
#69891
babameme (Thành viên)
babamemepbc
Super fast coder
Bài viết: 57
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: COIN34 8 năm trước   (+0)
Mọi người xem hộ em với, em cũng làm giống lion_it mà sao bị WA mãi, lúc đầu em hạn chế bộ nhớ nhưng sau thấy WA nên em thay toàn bộ bởi QWORD và longint rồi???
Code:
{$mode ObjFpc} {$-R,-Q} {$inline on}
const
      finp    =     '';
      fout    =     '';
var
      fi,fo   :     text;
      X       :     Array[1..35] of qword;
      S1,S2   :     qword;
      St2,T   :     qword;
      T1      :     Array[0..1048577,1..2] of qword;
      T2      :     Array[1..16385,1..2] of qword;
      Q       :     qword;
      max1,max2 :   longint;
//
Procedure OpenFile;
begin
      Assign(fi,finp);
      reset(fi);
      Assign(fo,fout);
      Rewrite(fo);
end;
//
procedure CloseFile;
begin
      Close(fi);
      Close(fo);
end;
//
Procedure Back1(i:byte);
var
      j       :     byte;
begin
      if i=1 then max1:=0;
      for j:=0 to 1 do
        begin
          s1:=s1+j*X[i];
          if j=1 then inc(max1);
          if i=20 then
            begin
              inc(T1[s1][1]);
              if T1[s1][2]=0 then T1[s1][2]:=max1
              else if T1[s1][2]<max1 then T1[s1][2]:=max1;
            end
          else
            Back1(i+1);
          s1:=s1-j*X[i];
          if j=1 then dec(max1);
        end;
end;
//
Procedure Back2(i:byte);
var
      j       :     byte;
begin
      if i=21 then max2:=0;
      for j:=0 to 1 do
        begin
          s2:=s2+j*X[i];
          if j=1 then inc(max2);
          if i=34 then
            begin
              inc(St2);
              T2[St2][1]:=s2;
              T2[St2][2]:=max2;
            end
          else
            Back2(i+1);
          s2:=s2-j*X[i];
          if j=1 then dec(max2);
        end;
end;
//
Procedure Solve(j:longint);
var
      i,res   :     longint;
begin
      readln(fi,Q);
      res:=0;
      for i:=1 to St2 do
        if (Q-T2[i][1]>=0) and (Q-T2[i][1]<=1048577) then
          if T1[Q-T2[i][1]][2]+T2[i][2]>res then res:=T1[Q-T2[i][1]][2]+T2[i][2];
      if res=0 then res:=-1;
      writeln(fo,'Case #',j,': ',res);
end;
//
Procedure Process;
var
      i       :     integer;
begin
      X[1]:=2;
      X[2]:=3;
      X[3]:=5;
      for i:=4 to 34 do
        X[i]:=X[i-3]+X[i-2]+X[i-1];
      S1:=0;S2:=0;St2:=0;
      Back1(1);
      Back2(21);
      readln(fi,T);
      for i:=1 to T do
        Solve(i);
end;
//
begin
      OpenFile;
      Process;
      CloseFile;
end.
 
Đã lưu IP Đã lưu IP  
 
+ cho mình nhé
  Đã khóa chức năng gửi bài.
Bài viết trên cùng Gửi trả lời
  • Trang:
  • << < 1 2 > >>
Powered by FireBoardBài viết mới nhất từ diễn đàn cho các chương trình nhận tin RSS