Vòng thi thử - Hội thi tin học

[m2mpro]

bài này chẳng dùng thuật toán nào cả, cứ thực hiện M bước đổi rồi sau đó lấy 2 chồng cao nhất úp lên nhau

Mình nghĩ bạn nhận xét sai vấn đề, khi bạn thực hiện 1 phép biến đổi ban đầu, có nghĩa các chồng chỉ bị thay đổi +1 hoặc -1, còn nếu bạn lấy 2 chồng cao nhất úp lên nhau thì cái thay đổi này là sai hoàn toàn

[ngtrhieu0011]

@linhhahaduc: xin bạn đọc lại cách tham gia đóng góp đề
@m2mpro: xin đọc kĩ lại đề

[=========> Bổ sung bài viết <=========]

Program Bunch;

Const Fin = 'Bunch.Inp';
      Fou = 'Bunch.Out';
      MaxArr = 100000;

Type Arr = Array [1..MaxArr] of Word;

Var A,B : Arr;
    N, M : Longint;
    i : Longint;
    u,v : Longint;
    Max1, Max2 : Longint;
    F : Text;

Begin
 Assign(F, Fin);
 Reset(F);
        Max1 := 1;
        Max2 := 1;
        Readln(F, N,M);
        For i:=1 to N do
         Begin
                A[i] := i;
                B[i] := 1;
         End;
        For i:=1 to M do
         Begin
                Readln(F, u,v);
                While A[v] <> v do
                 v := A[v];
                A[u] := v;
                If u <> v then
                 B[v] := B[v] + B[u];
                If B[v] > Max1
                 then Max1 := B[v]
                 else
                        If B[v] > Max2
                         then Max2 := B[v];

         End;
 Close(F);
 Assign(F, Fou);
 Rewrite(F);
        Write(F, Max1+Max2);
 Close(F);
End.

[m2mpro]

N = 6
Các phép di chuyển
1 -> 3
2 -> 4
4 -> 6

Theo cách của bạn sẽ ra là 5, bạn nghĩ bạn thực hiện phép biến đổi nào trc rồi thực hiện 3 phép biến đổi trên sẽ cho ra 5 ?

[bld]

sao ra 5 được ! anh m2m nói thử anh chuyển thế nào mà ra 5 ?
a hieu test giùm bài của e thử được bao nhiêu điểm ?

[quangtq]

Nếu 2 chồng cao nhất úp lên nhau thì chẳng nhẽ em lại đúng à.

[bld]

ko phải , bài của quang sẽ sai trong lúc tính chiều cao của các chồng , nên sẽ ko bước dc tới bước tìm 2 chồng lớn nhất, -> nên kq ko đúng , thường ra kq thấp hơn bình thường do bạn đặt lại h[a[i]]=0

[ngtrhieu0011]

theo test m2mpro:

1 -> 3
2 -> 4
4 -> 6

thì bước thực hiện của ta là:

3 -> 6

vậy thì 4 bước chuyển:

 
3 -> 6
1 -> 3
2 -> 4
4 -> 6

1 2 3 4 5 6


          3
1 2 _ 4 5 6


          1
          3
_ 2 _ 4 5 6



          1
      2   3
_ _ _ 4 5 6


          2
          4
          1
          3
_ _ _ _ 5 6

Bạn còn gì thắc mắc?

[bld]

bài này bản chất là tìm 2 thành phần liên thông lớn nhất như a linhhahaduc nói ,chồng ly chỉ là lớp vỏ ngoài thôi

[ngtrhieu0011]

mọi người có thể hiểu như vậy, nhưng tác giả viết bài này chủ yếu để đánh đố mọi người thôy.
nếu bạn nhìn ra hướng giải, thì code quá là đơn giản phải không? (tôi code 42dòng, tính lun các dòng thừa)

[quangtq]

Chuẩn. Cứ phức tạp hóa vấn đề lên.
Đi thi nếu ko nghĩ ra thuật toán nào thì nghĩ gì làm nấy