Diễn đàn tin học Nguyễn Văn Linh

The second house for every one
 
IndexTrợ giúpTìm kiếmThành viênĐăng kýĐăng Nhập

Share | 
 

 Các đoạn nguyên

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Các đoạn nguyên   Tue 27 Jul 2010, 13:06

Littlelee có một tập hợp các đoạn nguyên. Đầu tiên, anh ấy lấy ra 1 đoạn bất kì. Sau đó thực hiện lấy các đoạn khác, sao cho: đoạn lấy ra nằm trong đoạn vừa được lấy trước nó. Littlelee tiếp tục cho đến khi không tìm được đoạn thoả mãn nữa.
Bạn là một lập trình viên!Bạn hãy giúp littlelee giải này!
Yêu cầu

Tìm số đoạn lớn nhất có thể lấy ra.
Dữ liệu

Dòng đầu tiên chứa số nguyên N, là số đoạn nguyên trong tập hợp.

Dòng thứ i trong số N dòng sau, chứa 2 số nguyên A,B biểu thị cho đoạn i.
Kết quả

Một số duy nhất là kết quả của bài toán.
Giới hạn

1 <= N <= 100000

1 <= A < B <= 1000000
Ví dụ

Dữ liệu

3

1 6

2 5

3 4
Kết quả

3

Dữ liệu

6

1 4

1 5

1 6

1 7

2 5

3 5
Kết quả

5
Về Đầu Trang Go down
http://thongtra.forum-viet.com
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Các đoạn nguyên   Wed 28 Jul 2010, 08:29

Bài này là một bài cơ bản của QHD.

Xếp các đoạn theo thứ tự tăng dần của điểm đầu. QHD để tìm số đoạn bao hàm nhiều nhất.

Có điều nói vậy chứ Littlelee ko biết code đâu, mà dữ liệu lại lớn quá, hok làm tay được devilish . Mấy bạn code để giúp Littlelee nhé

_________________
Đời là cây đinh, mình là cây búa.
Về Đầu Trang Go down
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Re: Các đoạn nguyên   Wed 28 Jul 2010, 16:20

Code:

Var            N,M:longint;
                A,B,F,L:Array[0..100001] of longint;

Procedure      Input;
Var            i:longint;
Begin
                Readln(N);
                For i:=1 to N do Readln(A[i],B[i]);
End;

Procedure      Init;
Begin
                A[0]:=Low(longint);
                A[N+1]:=High(longint);
                M:=1;
                L[N+1]:=1;
                F[1]:=N+1;
End;

Procedure      Sort(L,R:longint);
Var            i,j,Tam,Tam1,Key,Key1:longint;
Begin
                If L>=R then Exit;
                i:=L;
                j:=R;
                Key:=B[(L+R) div 2];
                Key1:=A[(L+R) div 2];
Repeat
                While (B[i]>Key) or ((B[i]=Key) and (A[i]<Key1)) do Inc(i);
                While (B[j]<Key) or ((B[j]=Key) and (A[j]>Key1)) do Dec(j);
                If i<=j then
                Begin
                        Tam:=B[i];
                        B[i]:=B[j];
                        B[j]:=Tam;
                        Tam1:=A[i];
                        A[i]:=A[j];
                        A[j]:=Tam1;
                        Inc(i);
                        Dec(j);
                End;
Until          i>j;
                Sort(L,j);
                Sort(i,R);
End;

Function        Find(i:longint):longint;
Var            Dau,Cuoi,Giua,j:longint;
Begin
                Dau:=1;
                Cuoi:=M+1;
Repeat
                Giua:=(Dau+Cuoi) div 2;
                j:=F[giua];
                If A[j]>=A[i] then      Dau:=Giua
                Else                    Cuoi:=Giua;
Until          Dau+1=Cuoi;
                Find:=F[Dau];
End;

Procedure      Xuli;
Var            i,j,k:longint;
Begin
                For i:=N downto 0 do
                Begin
                        j:=Find(i);
                        K:=L[j]+1;
                        If K>M then
                        Begin
                                M:=K;
                                F[K]:=i;
                        End
                        Else
                                If A[F[K]]<A[i] then F[K]:=i;
                        L[i]:=K;

                End;
End;

Procedure      Output;
Begin
                Writeln(M-2);
End;

BEGIN
                Input;
                Init;
                Sort(1,N);
                Xuli;
                Output;
END.






_________________
P.T.H.T
Về Đầu Trang Go down
http://thongtra.forum-viet.com
whatsgoingon
Gà nhỏ


Tổng số bài gửi : 30
Join date : 18/07/2010
Age : 21
Đến từ : Nơi tận cùng vũ trụ

Bài gửiTiêu đề: Re: Các đoạn nguyên   Wed 28 Jul 2010, 20:58

Hovanthong cũng ở đà nẵng hay sao mà được làm admin
Hướng thì cũng giống ông lit mà cũng ko code được, đành copy code của chủ thớt về ngâm cứu
Crying or Very sad

Để ý thấy diễn đàn bây giờ là dành cho THPT rồi bounce
P/s ông lit kiếm đâu ra cái chữ kí đẹp thế bày tui làm với nào
Về Đầu Trang Go down
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Re: Các đoạn nguyên   Wed 28 Jul 2010, 23:12

Thuật toán qua rõ ràng:
1.ta sort giảm B[i] nếu có b[i] bằng nhau thì sort tăng a[i].
2.Tìm dãy con tăng dài nhất bằng TKNP.
Mình không phải ở Đà Nẵng.

_________________
P.T.H.T
Về Đầu Trang Go down
http://thongtra.forum-viet.com
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Re: Các đoạn nguyên   Wed 28 Jul 2010, 23:13

Các bạn lên làm thành viên Forum mình nhé: [You must be registered and logged in to see this link.]

_________________
P.T.H.T
Về Đầu Trang Go down
http://thongtra.forum-viet.com
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Các đoạn nguyên   Thu 29 Jul 2010, 18:16

Lên taochu.com mà tạo chữ kí lovestruck

_________________
Đời là cây đinh, mình là cây búa.
Về Đầu Trang Go down
toan_9a2
Gà con


Tổng số bài gửi : 17
Join date : 03/05/2010

Bài gửiTiêu đề: Re: Các đoạn nguyên   Thu 12 Aug 2010, 21:57

thế hovanthong là thong93 ah.
Về Đầu Trang Go down
Sponsored content




Bài gửiTiêu đề: Re: Các đoạn nguyên   Today at 21:30

Về Đầu Trang Go down
 
Các đoạn nguyên
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang
 Similar topics
-
» Rừng Mắm - Bình Nguyên Lộc
» Nguyên liệu và dụng cụ đan len
» Những Giai Thoại về Các Vị Tam Nguyên
» THƠ PHƯƠNG NGUYÊN
» Gánh cải Trạng Nguyên

Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn đàn tin học Nguyễn Văn Linh :: Góc tin học :: Lớp chuyên tin-
Chuyển đến