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

[bld]

trời , vậy a hieu : e không được nộp bài nữa à ! huhu

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

biết vậy nộp sớm , khỏi chỉnh sửa cũng ăn dc vài test roài huhu

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

hay a kéo dài hạn nộp ra , a cứ cho hạn nộp là 1 ngày thì cuối cùng cuộc thi cũng chỉ cho mình quang thi chớ mấy ^^, mem khác bận túi bụi

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

code của e nè , quái là chạy với m, n =10000 thì 1s, còn 100000 thì lên tới 15s , kì lạ thật
a hieu có code nào chạy 1s với M=N=100000 thì chỉ giùm cái thuật toán với

type bld=-2..100000;
var h,ax:array***91;1..100000***93; of bld;
    free:array***91;1..100000***93; of boolean;
    f:text;
    m,n:bld;
    max1,max2:bld;

procedure init;
var i:bld;
begin
 for i:=1 to n do begin free***91;i***93;:=true; h***91;i***93;:=1; ax***91;i***93;:=i; end;
 max1:=-1;
 max2:=-2;
end;

procedure find(var a,b:bld);
begin
 while ax***91;a***93;<>a do a:=ax***91;a***93;;
 while ax***91;b***93;<>b do b:=ax***91;b***93;;
end;

procedure nhap;
var i,a,b:bld;
begin
 assign(f,'bunch.inp');
 reset(f);
 readln(f,n,m);
 init;
 for i:=1 to m do
  begin
   readln(f,a,b);
   find(a,b);
   if a<>b then
    begin
     free***91;a***93;:=false;
     h***91;b***93;:=h***91;b***93;+h***91;a***93;;
     ax***91;a***93;:=b;
    end;
  end;
 close(f);
end;

procedure findmax;
var i:bld;
begin
 for i:=1 to n do if free***91;i***93; then
   if h***91;i***93;>max1 then
    begin
     max2:=max1;
     max1:=h***91;i***93;;
    end
   else if h***91;i***93;>max2 then max2:=h***91;i***93;;
end;

procedure ghi;
begin
 assign(f,'bunch.out');
 rewrite(f);
 write(f,max1+max2);
 close(f);
end;

BEGIN
 nhap;
 findmax;
 ghi;
END. 

[quangtq]

Do đang bận ôn nên mình làm bài thi có trong 1 tiếng. Thấy đúng cái test đầu là nộp, đi làm mấy bài hình (do limit bài, toàn bài khó).
Bao giờ bắt đầu vòng 2? Cho hạn thêm đi chứ. Em dạo này bận tóe khói.
Thuật toán của bld là gì vậy. Thấy hơi giống của mình.

[bld]

bài này tìm 2 thành phần liên thông lớn nhất , cứ xem mỗi thành phần có 1 nút gốc , nút đó mang độ lớn của thành phần đó và có ax của nó = chính nó , free của nó = true , các nút phụ thuộc khác có ax nối tới 1 nút khác và free = false , sau khi thực hiên hết thì tìm max1,max2 của các nút có free=true , công lại,....

[quangtq]

Vậy ăn được mấy test?????????

[bld]

mình đâu có test , đề anh hieu test thử chứ

[m2mpro]

Hiếu đã nói hướng giải rồi đó :

(1) : Thực hiện 1 bước của mình trc.
(2) : Thực hiện M bước theo yêu cầu.

Nhận xét : Do tất cả các chồng lúc đầu đều có 1 ly => (1)->(2) <=> (2)->(1).

Bây giờ, ta thực hiện M bước theo đề bài, tất nhiên ta sẽ có dễ dàng tính đc chồng lớn nhất có bao nhiêu ? Bây giờ có 2 trường hợp xảy ra :

- Tất cả các chồng đều bị ảnh hưởng của M phép biến đổi : thì ta sẽ lấy 1 ly từ một chồng nào đó ko ảnh hưởng trong việc biến đổi tạo ra chồng lớn nhất chồng lên chồng lớn nhất

- Tồn tại 1 chồng ko bị ảnh hưởng của M phép biến đổi : vẫn đơn giản lấy 1 ly của chồng này chổng lên chồng lớn nhất

[linhhahaduc]

Cách làm của mình là coi mỗi a b là đỉnh a và b có đg nối , rồi qua m bước , tìm 2 thành phần liên thông có nhiều đỉnh nhất . Từ đó lấy 1 a và 1 b bất kì nào đó trong 2 thành phần liên thông đó ---> kết quá . chả biết có đúng ko ? =))

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

P/s : Hình như có 1 nhận xét là M bước đó thực hiện bước nào trước cũng đều ra 1 kq giống nhau

[ngtrhieu0011]

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

[caimongs]

tại sao thi tin học toàn thấy lập trình nhỉ

[linhhahaduc]

Thảo nào thôi xác định luôn bài mình tle

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

Có được đóng góp đề cho BGK đề làm đề thi ko nhỉ ? ) mình còn cả đống bài khó , đang bí )