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
Giúp mình bài BWPOINT (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 1
CHỦ ĐỀ - Giúp mình bài BWPOINT
#64304
CTK41 (Thành viên)
pktc
Biết code binary-indexed tree
Bài viết: 43
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Giúp mình bài BWPOINT 8 năm, 5 tháng trước   (+0)
http://vn.spoj.pl/problems/BWPOINTS/
Code:
{$MODE OBJFPC}
const
  fi='';
  fo='';
  max=100010;
type
  diem=record
    x:longint;
    b:boolean;
end;
var
  f1,f2:text;
  F:array[0..2*max] of longint;
  res:longint;
  a:array[1..2*max] of diem;
  n:longint;
procedure input;
var
  i:longint;
begin
  Assign(f1,fi);reset(f1);
  readln(f1,n);
  For i:=1 to n do
  begin
    read(f1,a[i].x);
    a[i].b:=true;
  end;
  For i:=n+1 to 2*n do
    begin
      read(f1,a[i].x);
      a[i].b:=false;
    end;
  close(f1);
end;
procedure quicksort(l,r:longint);
var
  i,j,pivot:longint;
  temp:diem;
begin
  i:=l;
  j:=r;
  pivot:=a[random(r-l+1)+l].x;
  while i<=j do
    begin
      while a[i].x<pivot do inc(i);
      while a[j].x>pivot do dec(j);
      if i<=j then
        begin
          temp:=a[i];
          a[i]:=a[j];
          a[j]:=temp;
          inc(i);
          dec(j);
        end;
    end;
  if i<r then quicksort(i,r);
  if j>l then quicksort(l,j);
end;
function getmax(x,y:longint):longint;
begin
  if x<y then getmax:=y else
  getmax:=x;
end;
procedure slove;
var
  i,j:longint;
  t:longint;
begin
  Assign(f2,fo);rewrite(f2);
  quicksort(1,2*n);
  res:=0;
  F[0]:=0;
  if(a[1].b xor a[2].b=true) then F[1]:=1
  else F[1]:=0;
  For i:=2 to 2* n do
  begin
    F[i]:=F[i-1];
    if(a[i].b xor a[i-1].b=true) then F[i]:=getmax(F[i-2]+1,F[i-1])
  end;
  For i:=1 to 2*n do res:=getmax(res,F[i]);
  writeln(f2,res);
  close(f2);
end;
begin
  input;
  slove;
  //readln;
end.
code mình sai ở đâu mà có 95 điểm vậy
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#64312
kuchiki (Thành viên)
franco1+6
Super fast coder
Bài viết: 61
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: Giúp mình bài BWPOINT 8 năm, 5 tháng trước   (+0)
Bạn cho mình xin cái thuật toán
 
Đã lưu IP Đã lưu IP  
 
We're just big one family
  Đã khóa chức năng gửi bài.
#64313
theguiler (Thành viên)
c_hunter+4
Biết code binary-indexed tree
Bài viết: 27
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: Giúp mình bài BWPOINT 8 năm, 5 tháng trước   (+0)
@ctk41: Bạn nên nói thuật toán cho mọi người biết chứ ai có thời gian mà đọc code của bạn. Theo mình bạn có thể giải theo hường này,sắp xếp tăng hoặc giảm tọa độ rồi với mỗi hai điểm có màu và chưa được chọn bạn tính là một cặp rồi đánh dấu là đã chọn rồi
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#64314
trungteok44 (Thành viên)
ze0mung-
Đã code là AC
Bài viết: 86
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: Giúp mình bài BWPOINT 8 năm, 5 tháng trước   (-2)
bạn thử đừng qs theo kiểu random xem sao nghĩa là làm như bình thường thôi key:=a[(i+j)div 2] nak
 
Đã lưu IP Đã lưu IP  
 
My life.Ngày hôm qua đã từng ...!!!...
  Đã khóa chức năng gửi bài.
#64318
CTK41 (Thành viên)
pktc
Biết code binary-indexed tree
Bài viết: 43
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: Giúp mình bài BWPOINT 8 năm, 5 tháng trước   (+0)
Thuật toán mình là QHD giống 1 bạn nào đấy trên diễn đàn
- Khai báo mảng a[2*maxn] of Record x:Longint; b:Boolean End;
(x là tọa độ của điểm, b=true nếu đó là điểm đen, ngược lại là điểm trắng.
- Lần lược đọc các điểm vào mảng a, sau đó dùng sort tăng dần theo x.
- Khai báo mảng F[2*maxn] of Longint.
- Cở sở QHD:
F[0]:=0; F[1]:=1 nếu a[1].b xor a[2].b = True, ngược lại F[1]:=0;
- Công thức truy hồi: F[i]:=MaF[i-2]+t,F[i-1]) (i từ 2->2*n). Với t=1 nếu a[i].b xor a[i-1].b = True, ngược lại t=0.
-Duyệt từ 1->2*n cập nhật kết quả res=getmares,F[i]);
Mong mọi người sửa code giúp mình với,mình chưa phát hiện ra sai chỗ nào
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#64321
textbyteit (Thành viên)
textbyteit
Đang tập code
Bài viết: 1
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: Giúp mình bài BWPOINT 8 năm, 5 tháng trước   (+0)
bài này em làm thế này:
sắp xếp dãy [2*n];
chạy i từ 1 đến 2*n nếu:
a[i] và a[i+1] khác màu thì tăng kq lên 1 và tăng i lên 2 ngược lại tăng i lên 1;
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#64326
CTK41 (Thành viên)
pktc
Biết code binary-indexed tree
Bài viết: 43
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: Giúp mình bài BWPOINT 8 năm, 5 tháng trước   (+0)
Đã phát hiện ra chỗ sai,Mình quên chưa đánh dấu diểm chọn ,Chọn rồi thì xóa luôn
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69864
Tran Ngoc (Thành viên)
Đang tập code
Bài viết: 1
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: Giúp mình bài BWPOINT 8 năm trước   (+0)
Tại sao k dùng cách quicksort mảng trộn theo thứ tự tăng dần và xét a[i] và a[i+1]. Nếu 2 pt này là đen và trắng thì có thể lấy đoạn này...Nhg tại sao làm vậy k đúng???
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
Bài viết trên cùng Gửi trả lời
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