COMNET – spoj

Đề bài:

Tóm tắt đề:

Cho M đường truyền có các chi phí wi, các truy vấn người ta thay đổi trọng số một số cạnh và hỏi xem cạnh thứ k có thể loại bỏ vì nó không thuộc vào cây khung nhỏ nhất của đồ thị hay không.

Thuật toán:

-Sau khi thay đổi trọng số các cạnh theo đề bài (nếu các cạnh có trọng số bằng nhau thì ưu tiên xét cạnh k đứng đầu), tìm cây khung nhỏ nhất của đồ thị và in ra ‘YES’ hay ‘NO’ tương ứng là cây trả lời. ĐPT O(test*nlogn)
-Thuật toán trên sẽ giúp bạn có được 60->70 điểm, đề ăn full bạn cần thay đổi một chút trước khi tìm cây khung: Vẫn thay đổi trọng số các cạnh theo đề bài, nhưng không sort lại các cạnh mà tìm các cạnh có trọng số nhỏ hơn trọng số của cạnh thứ k, hợp nhất các gốc lại.

Kiểm tra xem hai đỉnh của cạnh thứ k đã thuộc vào cây khung hay chưa rồi in ra ‘YES’ hay ‘NO’ tương ứng. ĐPT O(test*n).

Code:

#include <iostream>
#include <vector>
using namespace std;
 
#define LL long long
 
struct universe {
    vector<int> cha, rank;
    universe(int n): cha(n + 1), rank(n + 1, 0) {
        for (int i=1; i<=n; i++) cha[i] = i;
    }
    int find(int u) {
        if (cha[u] != u) cha[u] = find(cha[u]);
        return cha[u];
    }
    bool join(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return false;
        if (rank[u] == rank[v]) rank[u]++;
        if (rank[u] > rank[v]) cha[v] = u;
        else cha[u] = v;
        return true;
    }
};
 
struct pack { int u, v; };
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T; cin >> T;
    while (T--) {
        int n, m, Q; cin >> n >> m >> Q;
        vector<pack> e(m);
        vector<int> w(m);
        for (int i=0; i<m; i++) cin >> e[i].u >> e[i].v >> w[i];
        while (Q--) {
            int id; cin >> id; id--;
            int s; cin >> s;
            vector<int> ww(w);
            while (s--) {
                int t, w; cin >> t >> w;
                ww[t-1] = w;
            }
            universe a(n);
            for (int i=0; i<m; i++) if (ww[i] < ww[id]) {
                a.join(e[i].u, e[i].v);
            }
            if (a.join(e[id].u, e[id].v)) cout << "NO\n";
            else cout << "YES\n";
        }
    }
    return 0;
}

Tổng hợp tài liêu, đề thi môn Cơ Nhiệt

 Các hãy bạn trao đổi kết quả, lời giải bằng cách comment ở bên dưới bài viết. Để đáp án các đề được hoàn thiện hơn

Đề cương ôn tập

Đề thi cuối kỳ

co-nhiet-2017-yeulaptrinh

co-nhiet-16-yeulaptrinh

co-nhiet-2016-yeulaptrinh

co-nhiet-yeulaptrinh-14

Lời giải một số đề Cơ nhiệt cuối kỳ

https://drive.google.com/file/d/0BxaNmKNXkJWJWGxUUW12cTNyN3M/view?usp=sharing

https://drive.google.com/file/d/0B9WAwe4vPnvDV1pyRU9fVTlKbkk/view?usp=sharing

 

(Sẽ có cập nhập thêm)

LUBENICA – spoj

Đề bài:

Thuật toán:

  • LCA

Code:

uses    math;
const   fi='';
        fo='';
        maxk=20;
        maxn=trunc(1e5)+3;
        oo=2*trunc(1e9);
 
type    arr1    =array[1..maxn] of longint;
        arr2    =array[1..maxn,0..maxk] of longint;
 
var     mi,ma,p         :arr2;
        depth,dad       :arr1;
        i,j,n,m,q       :longint;
        link,head,ke,ts :array[-maxn..maxn] of longint;
        resma,resmi     :longint;
        cx      :array[1..maxn] of boolean;
procedure add(i,u,v,w:longint);
begin
        link[i]:=head[u];
        head[u]:=i;
        ke[i]:=v;
        ts[i]:=w;
end;
 
procedure enter;
var     u,v,w   :longint;
begin
        readln(n);
        for i:=1 to n-1 do
        begin
                read(u,v,w);
                add(i,u,v,w);
                add(-i,v,u,w);
        end;
end;
 
procedure dfs(u:longint);
var     i,v     :longint;
begin
        cx[u]:=false;
        i := head[u];
        while i<>0 do
                begin
                        v:=ke[i];
                        if cx[v] then
                                begin
                                        depth[v]:=depth[u]+1;
                                        dad[v]:=u; ma[v,0] := ts[i]; mi[v,0] := ts[i];
                                        dfs(v);
                                end;
                        i:=link[i];
                end;
end;
 
procedure init;
var     i,j     :longint;
begin
        fillchar(cx,sizeof(cx),true);
        dad[1] := 1; depth[1] :=1;
        dfs(1);
        for i:=1 to n do
                begin
                        p[i,0] := dad[i];
                end;
        for j:=1 to maxk do mi[1,0] := oo;
        for j:=1 to maxk do ma[1,0] := -oo;
        for j:=1 to maxk do
                for i:=1 to n do
                        begin
                                p[i,j] := p[p[i,j-1],j-1];
                                ma[i,j] := max(ma[i,j-1],ma[p[i,j-1],j-1]);
                                mi[i,j] := min(mi[i,j-1],mi[p[i,j-1],j-1]);
                        end;
end;
procedure lca(u,v:longint);
var     i,j     :longint;
begin
        for i:=maxk downto 0 do
                if depth[p[u,i]]>=depth[v] then
                        begin
                                resma := max(resma,ma[u,i]);
                                resmi := min(resmi,mi[u,i]);
                                u := p[u,i];
                        end;
        for i:=maxk downto 0 do
                if depth[p[v,i]]>=depth[u] then
                        begin
                                resma := max(resma,ma[v,i]);
                                resmi := min(resmi,mi[v,i]);
                                v := p[v,i];
                        end;
        if u=v then exit;
        for i:=maxk downto 0 do
                if p[u,i]<>p[v,i] then
                        begin
                                resma := max(resma,ma[v,i]);
                                resmi := min(resmi,mi[v,i]);
                                resma := max(resma,ma[u,i]);
                                resmi := min(resmi,mi[u,i]);
                                v := p[v,i];
                                u := p[u,i];
                        end;
        resma := max(resma,ma[v,0]);
        resmi := min(resmi,mi[v,0]);
        resma := max(resma,ma[u,0]);
        resmi := min(resmi,mi[u,0]);
end;
procedure process;
var     u,v,qq  :longint;
begin
        read(q);
        for qq:=1 to q do
                begin
                        read(u,v);
                        if u=v then begin writeln(0,' ',0); continue; end;
                                resmi := oo;
                                resma := -oo;
                                lca(u,v);
                        writeln(resmi,' ',resma);
                end;
end;
procedure print;
begin
 
end;
 
begin
        assign(input,fi);reset(input);
        assign(output,fo);rewrite(output);
                enter;
                init;
                process;
                print;
        close(input);close(output);
end

Tôi đã học lập trình thế nào (Phần 1)

Năm cấp 3

Lần đầu tôi được tiếp cận với giải thuật và ngôn ngữ lập trình Pascal.

Nói chung là chẳng hiểu bất cứ thứ gì và cũng chẳng có hứng thú gì. Trong đầu tôi xuất hiện những câu hỏi chuối tới mức người ta nhìn vô là sẽ thấy tôi chẳng có chút tư duy gì hết, ví dụ như:

  • Học cái quái gì mà khi chạy chương trình lại hiện ra trên cái màn hình xanh xấu xí thế này.
  • Tại sao cộng từ 1 đến 10 lại phải dùng vòng for làm gì cho mệt sao không dùng máy tính bỏ túi cho nhanh. À mà vòng for là cái ếu gì vậy.

Hồi đó, chẳng có hứng thú gì và cũng chẳng nghĩ gì đến Software Engineer hay Developer trong danh sách nghề nghiệp tương lai của mình.

Giữa năm cấp 3

Lúc này mình vẫn còn lơ mơ về con đường sự nghiệp tương lai của mình, đúng lúc này mình biết đến game online do thằng bạn giới thiệu và con đường bước chân vào ma đạo của mình bắt đầu từ đây. Mình bắt đầu học hành chểnh mảng hơn thay vào đó suốt ngày ngoài làm việc vặt hằng ngày ra thì mình lại chơi game. Ngoài ra thì mình cũng vào trang web HaiVL để chém gió, hóng hớt với mọi người đủ thứ chuyện trên đời ? nhưng tiếc là giờ nó chết mất rồi, nghĩ lại hơi buồn vì mình có quá nhiều kỉ niệm với trang web này.

Cuối năm cấp 3

Vậy là thoáng 1 cái đã gần hết 3 năm học hành trình cày game của mình cũng sắp kết thúc và mình vẫn chưa có gấu.  Ấy nhầm mình nói đến đâu rồi ấy nhể.

Hôm đó là vào 1 buổi chiều gió nhẹ, trong lành mình đang ngồi ở ghế đá trong sân trường chơi game trên con máy điện thoại cùi bắp thì có tờ giấy bay ngang  vào mặt mình thấy bực quá mở ra xem thì thấy tiêu đề bài viết là ” Học CNTT không lo chết đói”. Nghĩ là cái thứ chẳng hay ho gì nên mình cũng chẳng quan tâm lắm. Thế rồi kì thi đại học đến gần, lúc đó mình còn trẻ trâu chưa biết nên thi ngành gì, và trong thời gian đó thì mọi người đổ xô theo CNTT, và có người bảo với mình là trường đại học Quốc Gia gì gì đấy đào tạo CNTT cũng được lắm. Thấy mọi người bảo vậy thì tôi cũng thi thử cho biết, thế là tôi bắt đầu ôn thi vào trường đại học Quốc Gia, may thay năm đó tôi thi lại vừa đủ điểm đỗ vào trường ĐHQG, thuộc khoa Công Nghệ Thông Tin của trường  và hành trình dấn thân vào ma đạo ấy nhầm dấn thân vào con đường lập trình của tôi bắt đầu từ đây ?

Câu chuyện đưa mình đến với cái ngành bèo nhất hành tinh là như vậy đấy ?

À mà viết tới đây cũng dài quá rồi và chắc hẳn các bạn cũng than rằng viết gì mà dài thế. Ở phần 2 mình sẽ kể cho các bạn nghe tiếp về con đường lập trình mà mình đang theo và các hướng đi cho các bạn đang theo ngành này, các bạn nhớ đón đọc nhé ?

Các bạn  nhớ đăng ký theo dõi blog để cập nhật những bài viết mới nhất hằng tuần nhé ?

Con đường cho một lập trình viên (Phần 1)

Từ câu hỏi của các bạn trẻ mới chập chững bước vào nghề

Hôm nay mình dậy sớm hơn mọi khi ? và sau một hồi dạo chơi trên các blog lập trình như là dậy nhậu học, sờ tắc câu vờ phờ lâu, quơ ra :D……thì mình thấy khá nhiều các bạn trẻ chủ yếu là các bạn đang học lớp 12 và các bạn sắp thi đại học thường đặt những câu hỏi kiểu như là “Làm lập trình viên có khó không“, “Làm sao để trở thành 1 lập trình viên” hay như là “Có phải các anh lập trình viên đều rất đẹp trai không” :D.

Số lượng quả thật không hề ít qua đó thấy rằng rất nhiều bạn trẻ đang rất quan tâm đến ngành lập trình và mong muốn theo đuổi nó.

Đến các công việc mà các bạn có thể làm khi theo ngành này

Quả thực thì đối với những bạn mới bắt đầu tìm hiểu về lập trình và học lập trình thì đây là một câu hỏi khó, nó còn khó hơn cả là “Em nên chọn ngôn ngữ gì để học bây giờ” hay như là” Em muốn làm game Android thì nên học những gì đây”..bla,bla…Đa phần các tài liệu trên mạng hiện nay đều nặng về code, không chú trọng vào việc định hướng nghề nghiệp, bập một phát bắt tay ngay vào code dễ làm các bạn hoảng sợ.

Untitled1

Untitled

Chuyện này cũng dễ hiểu vì khi mình mới bắt đầu học lập trình cũng không biết học lập trình sau sẽ làm những công việc gì :D. Theo mình thì khi bắt đầu học lập trình thay vì ngồi code và sửa bug thì ta cần phải định hướng cho các bạn về ngành lập trình: lập trình viên thì làm gì, tố chất cần là gì, làm lập trình khó có gấu lắm đúng ko…bla,bla…..Do đó mình chọn hướng tiếp cận riêng, bắt đầu học lập trình ko có 1 dòng code nào, điều đó làm các bạn dễ thở hơn đỡ hoảng hồn hơn ?

Ôi Dào, nói gì mà dài dòng thế vào thằng vấn đề chính luôn đi

Và dài dòng thế là đủ rồi, series này không nói về code vậy nó nói cái ếu gì vậy? Bạn hãy coi nó là một series định hướng lập trình. Đối tượng hướng đến là các bạn đang học lớp 12 và những bạn đang học năm nhất đại học. Tuy nhiên đây chỉ là ý kiến của riêng cá nhân tác giả rất mong các đàn anh đi trước vào góp ý “dạy” mình và mọi người ?

Tóm tắt nội dung trong series:

  • Lập trình viên thì làm những công việc gì? Công việc thường ngày của họ là gì?
  • Học lập trình có thể làm được gì: app, game, di động……
  • Tố chất cần có của một lập trình viên là gì?
  • Làm sao để học ngôn ngữ đầu tiên?
  • Học xong 1 ngôn ngữ thì làm gì? Viết ứng dụng đầu tiên

Đôi lời nhắn nhủ

Đọc xong blog này chắc chắn các bạn sẽ không viết được dòng code nào, nhưng đừng quá vội vàng nhé. Trước khi học thì ta cần phải có định hướng trước thì mới hiểu được sau mình sẽ làm gì nhé ?

Nếu có thắc mắc gì trong quá trình đọc blog thì các bạn có thể thoải mái PM cho mình qua email để hỏi nhé.

Nhớ theo dõi blog để xem tiếp series bài viết ở phần 2 nhé ?

Học lập trình như thế nào?

Một trong những câu hỏi được nhiều bạn sinh viên ngành công nghệ quan tâm nhất đó là: Cần học những kiến thức gì, kĩ năng gì để trở thành một lập trình viên?Câu hỏi nghe có vẻ đơn giản nhưng rất khó để trả lời, lập trình là một mảng rất rộng có hàng tá công nghệ để theo và cũng có hàng tá ngôn ngữ để học.

lap-trinh-vien

Cũng chẳng có gì là xa vời cả và bạn có thể thấy lập trình rất gần gũi với chúng ta đó là:

  • Ứng dụng tin nhắn chúc mừng sinh nhật tự động gửi đến sớm mai khi ta chưa kịp nhớ mai là ngày gì.
  • Những ứng dụng quản lí trong siêu thị, ngân hàng mà chỉ với vài cú click nhấp chuột cô nhân viên, cô chủ kho đã có hóa đơn cho khách hàng thay vì mất cả buổi trời như trước kia.
  • Những chương trình học trực tuyến giúp chúng ta ghi nhớ chương trình học, nhắc nhở chúng ta làm bài tập, khen thưởng cho chúng ta khi chúng ta nỗ lực học tập cho tới khi đến đích.
  • Những ứng dụng, trò chơi đấu trí, cờ tướng, po ké mon – thực tế ảo làm cho con người phát hiện ra nhiều điều thú vị trong cuộc sống.

Và còn nhiều nữa……..

Học lập trình để làm gì?

Trước khi quyết định học ngôn ngữ gì, đầu tư thời gian như thế nào thì bạn nên dừng lại và nghĩ xem mình học lập trình để làm gì? Đây là điều quan trọng vì chỉ khi bạn biết mình sẽ đến đâu thì việc lựa chọn con đường và cách đi lúc này mới thật sự có ý nghĩa. Thế giới lập trình vô cùng rộng lớn, có rất nhiều ngã rẽ và mỗi hướng đi đều có nhiều cơ hội và thử thách đang chờ bạn.

Lập trình là một ngành kỹ thuật (of course :D) thế nên bạn phải trang bị cho mình những kiến thức về kỹ thuật nhất định. Vậy túm cái váy lại thì lập trình viên cần học những gì?

Và không làm mất thời gian của các bạn nữa, mình sẽ vào thẳng vấn đề chính luôn!

Có thể chia nghề lập trình ra làm mấy loại như sau, bạn chỉ việc chọn cái mà bạn thích nhất và lao đầu vào nghiên cứu nhé.

  • Mảng mobile: Bạn nào thích làm game, app chạy trên điện thoại di động thì chắc chắn sẽ thích mảng này rồi :D, chắc các bạn vẫn nhớ con chim Flappy Bird nổi tiếng một thời chứ nhỉ. Để theo mảng này bạn sẽ  viết phần mềm chạy trên điện thoại mà phổ thông nhất là Android và IOS. Bạn sẽ phải học Java (Anroid)Objective-C (IOS). Bây giờ thì Google cũng đã phát triển ngôn ngữ mới cho việc phát triển Android đó là Kốt Lin, còn mình không học IOS nên cũng không biết là có biến gì không ?
  • Mảng Web: Cái này thì khỏi phải giới thiệu nữa rồi, nó có từ rất lâu đời trên Internet rồi. Theo cái này khỏi lo thiếu việc, vì công ty nào cũng cần web. Và rất nhiều ngôn ngữ có thể dùng để làm web được, thoải mái chọn: Java,php,python….nhưng phải học thêm cả đống lằng nhằng: html, css, javascript…..
  • Mảng desktop app: Tức làm phần mềm chạy trên máy tính , các ngôn ngữ C#, C, C++ đều có thể làm desktop app được. Còn việc nên chọn cái nào hay là cái nào tốt hơn cái nào thì mình không biết nhé, vì mình không theo mảng này nên không biết ?
  • Mảng Embedded: Còn gọi là lập trình nhúng, tức là viết các chương trình chạy trong các thiết bị điện tử như tivi điều hòa, tủ lạnh, máy giặt, robot… nói chung là điều khiển các thiết bị thật, sờ nắm được. Mảng này thì thường các bác học ngành điện tử viễn thông, cơ điện tử…….làm nhiều.

Và túm lại váy lại thì đây là 4 mảng để cho các bạn theo ngành lập trình có thể theo, việc của bạn là chỉ việc chọn 1 trong 4 mảng mà mình đã nêu ở trên để học và nghiên cứu thật kỹ về nó ?

Nói chung, lập trình là một thế giới vô cùng thú vị.  Đây là bài viết mà mình lảm nhảm tất tần tật những điều bạn cần phải học, những kiến thức cần được trang bị khi mà chọn hướng đi riêng cho mình. Hi vọng sẽ giúp được các bạn một chút gì đó ? chúc các bạn thành công với đam mê của mình.

Lập trình viên là gì? Những công việc của người lập trình viên

Đây là bài đầu tiên trong series ” Định hướng nghề nghiệp cho các lập trình viên“. Như mình đã nói từ trước thì đây là series giúp các bạn trẻ có cái nhìn tổng quan hơn về nghề lập trình trước khi theo đuổi nó.Bài viết này sẽ trả lời câu hỏi ” Làm lập trình viên là làm gì” và Công việc thường ngày của một lập trình viên là gì?

Trước hết chúng ta cần phải hiểu thế nào là lập trình viên?

Hiểu một cách đơn giản lập trình viên là những người thiết kế, xây dựng và bảo trì các phần mềm máy tính bằng các ngôn ngữ lập trình khác nhau. Họ có thể tạo ra các chương trình mới, sửa lỗi hay nâng cấp các phần mềm đó để tăng hiệu quả cho việc sử dụng máy tính.

Các ngôn ngữ lập trình chủ yếu: C, C#, Java, PHP……

ky-nang-lap-trinh-vien-gioi-1

Và nhắc đến lập trình viên nhiều bạn sẽ nghĩ ngay đến việc lập trình web, lập trình game, lập trình phần mềm, bla,bla……Bạn nghĩ như vậy là đúng rồi đấy ? Một phần mềm phải được tạo ra từ một “thiết kế”(framework) và để kết nối các chương trình lại với nhau để tạo ra phần mềm đó thì phải cần tới các lập trình viên.

Tới đây chắc các bạn cũng hiểu thế nào là lập trình viên rồi đúng không nào ?

Ôi Dào, dài dòng quá định nghĩa nãy giờ thế rốt cuộc công việc hằng ngày của lập trình viên là gì?

Công việc thường ngày của một lập trình viên đó là học cách gõ 10 ngón tay trên bàn phím máy tính (đùa đấy).

Hiểu một cách đơn giản thì công việc thường ngày của lập trình viên đó là “Code”. Các lập trình viên dành phần lớn thời gian làm việc của mình cho việc code. Code xong thì tiếp theo đó là “Test” code, công việc này thì các bạn sinh viên thường đảm nhận cả việc code lẫn test luôn, nhưng khi đi làm, công việc đòi hỏi phải làm với những hệ thống lớn thì sẽ có người khác lo nhé ?

Cuối cùng và cũng rất quan trọng đó là “Fix Bug”. Bug là những lỗi ta gặp khi code, Code nào cũng có Bug, không ít thì nhiều. Khi phát hiện Bug ta phải vá và sửa code để chương trình chạy đúng.

Công việc của lập trình viên thường xuyên phải ngồi với chiếc máy tính, laptop suốt cả ngày, từ ngày này qua ngày khác, năm này ra năm khác :D. Nhiều người nhìn những anh lập trình viên ai cũng đeo kính cận dày cộp, suốt ngày chỉ biết cắm đầu vào máy tính mà chẳng hề quan tâm thế giới ngoài kia có biết bao nhiều cô gái xinh tươi ? Họ nhìn với ánh mắt dè bỉu và nghĩ ” thứ này chắc cũng chả hay ho gì” :(( . Nhưng do đặc thù công việc nên họ phải chấp nhận vậy thôi, nó là đam mê của mỗi người ?

Kết luận

Vậy là ở phần này, các bạn đã hiểu được những công việc mà các lập trình viên phải làm rồi đúng không nào.

À mà quên như đã nói ở trên do đặc thù của ngành suốt ngày phải ngồi với máy tính nên đến tận bây giờ mình vẫn chưa có gấu :(( . Vì thế rất khuyến khích các bạn nữ gửi thư, in bốc làm quen nhé ?

Ở phần sau, chúng ta sẽ tìm hiểu về chủ đề “Học lập trình có thể làm được gì?”. Nhớ like và theo dõi blog để đón xem nhé.