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)

TỔNG HỢP TÀI LIỆU VÀ ĐỀ THI GIẢI TÍCH 1

 

Đề cương

Đề thi giữa kỳ

Đề giải tích 1 giữa kỳ ĐH Công nghệ (UET)
giai-tich-1-yeulaptrinh

giua-ky-giai-tich-1-yeulaptrinh.pw

Đề thi cuối kỳ

VNU 2016-2017

giai-tich-2016-2017

Giải tích 1 (VNU năm học 2015-2016)

giai-tich-1-2016-yeulaptrinh.pw

Bài tập – Thực hành

https://drive.google.com/open?id=0B1zK9uGpggiyMGczRW1nclA3aWs

 

Lý thuyết – Bài giảng

https://drive.google.com/open?id=0B1zK9uGpggiyMWFxdkJ1R19ua1k

(đang cập nhập)

mọi đóng góp xin gửi về yeulaptrinh.pw@gmail.com

xin cảm ơn!

Tổng hợp đề thi, tài liệu ôn thi giữa kỳ môn Đại số

 

Tổng hợp tất cả đề thi giữa kỳ Đại Số từ K55-K61 BKHN.

https://goo.gl/uvyNj2
https://goo.gl/kyYkDx
https://goo.gl/rr8nkQ


Các tài liệu học tập:

https://goo.gl/84xQeC
https://goo.gl/kaSMT2
https://goo.gl/286fw8
https://goo.gl/jE227Z
https://goo.gl/P3q32L
https://goo.gl/36Np4B
https://goo.gl/Mo3bE6
https://goo.gl/rkAfcM
https://goo.gl/BAvVy7
https://goo.gl/cjV31Y

Một số đề thi mới cập nhập: …

ĐỀ 1 – 20163

 

ĐỀ 2 – 20163

ĐỀ 1 – 20151

ĐỀ 1 – 20161

ĐỀ 2 – 20161

ĐỀ 3 – 20151

ĐỀ 3 – 20161

ĐỀ 5 – 20151

Đề thi, đáp án OLP 2016 (Olympic Tin học sinh viên)

Kì thi Olympic Tin học sinh viên năm 2016 cũng diễn ra được hơn 2 tuần rồi, đề thi cũng đã được public và các bạn có thể tải về để xem tại: https://goo.gl/Vknb6P . Với mong muốn giúp các bạn sinh viên có thể học tập tốt hơn và phát triển khả năng lập trình trong những năm tới nên mình viết lời giải để các bạn nào chưa làm được có thể thử sức làm lại những bài mình chưa giải được trong kì thi, hi vọng sẽ giúp các bạn học thêm được nhiều thứ.
Lưu ý đây chỉ là lời giải mang tính tham khảo dựa trên kiến thức của mình chứ không phải lời giải chính thức từ người ra đề của cuộc thi.

Khối Siêu cúp:

  • LAMPS: Bài này ta có thể giải bằng luồng cực đại (https://en.wikipedia.org/wiki/Maxim…), có nhiều cách xây dựng luồng. Cách xây dựng luồng của mình là:
    • Gọi đỉnh xuất phát là S, đỉnh kết thúc là F, ta có c đỉnh đại diện cho c màu khác nhau của đồ thị, cạnh (S,c(i)) có trọng số x là số lượng đỉnh trên đồ thị có màu là thứ i, mặc khác với mỗi màu i ta tạo cạnh (c(i),F) có trọng số là 1, ta lại có k đỉnh đại diện cho k chu trình khác nhau trong đồ thị, với mỗi với mỗi đỉnh u có màu i nằm trong chu trình j thì ta có cạnh (c(i), k(j)) với trọng số là 1. Tìm luồng cực đại trên đồ thị này, gọi giá trị là X thì kết quả bài toán là X – k. (Các bạn hãy tự chính minh tính đúng đắng)
    • Do mỗi cạnh thuộc tối đa 1 chu trình nên ta có tối đa n/3 chu trình trên đồ thị, số lượng đỉnh tối đa của đồ thị luồng là: m + n / 3 + 2 = n * 5 / 3 + 2 ~ 17000 , số lượng cạnh tối đa là: m + n + n / 3 = n * 8 / 3 ~ 27000. Do đó ta cần phải xây dựng đồ thị luồng một cách tối giản nhất (gọp các cạnh trùng) cũng như dùng thuật toán tìm luồng nhanh như Dinic hoặc Preflow Push thì mới có thể đạt điểm tối đa bài này.
  • CAKE: Tư tưởng bài này là khi đổi bánh khối lượng x từ người có tổng khối lượng bánh Tx sang 1 người có bánh khối lượng y tổng khối lượng bánh Ty, trong đó Tx > Ty thì ta cần có y – Tx + Ty < x < y để tổng chênh lệch lúc sau khi đổi giảm đi. Ta có thể sắp các giá trị Tx tăng dần và dùng IT hoặc BIT để đếm số giá trị x thỏa mãng.
  • RADA: Xét mỗi vòng tròn, ta tính tất cả các giao điểm của vòng tròn này với các vòng tròn còn lại, các trường hợp đặc biệt là vòng tròn này chứa các vòng tròn khác hoặc bị chứa thì ta xử lí riêng. Trường hợp 2 vòng tròn giao nhau tại 2 điểm thì cái khó là ta cần tính được 2 giao điểm này, sau đó 2 giao điểm này nằm trên cung tròn sẽ giống như 2 dấu mở ngoặc và đóng ngoặc ‘(‘ ‘)’. Lúc này ta đưa được về bài toán là tìm điểm được bao bởi nhiều cặp dấu mở ngoặc đóng ngoặc nhất.
  • ALICE: Bài này lời giải khá đơn giản nhưng không phải ai cũng có thể nghĩ ra:
    • Trường hợp tồn tại vị trí số 0 nằm bên trái số 1 thì chắc chắc sẽ luôn tồn tại 1 xâu 01.
    • Trường hợp tất cả các số 1 đều nằm bên trái tất cả các số 0, ta sẽ tìm số 1 bên phải nhất và số 0 bên trái nhất, tập trung hỏi vào vòng giữa 2 số này. Cách hỏi là: Nếu vùng này có độ dài lẻ, ta sẽ hỏi vào các vị trí 2, 4, 6, … Ta có thể hỏi ở bất kì 1 vị trí nào trong các vị trí này, trường hợp độ dài chẵn thì hỏi ở đâu cũng được. Khi hỏi xong nhận kết quả trả về là 0 hay 1 thì ta sẽ cập nhật lại vị trí số 1 bên phải nhất hoặc số 0 bên trái nhất, và đi vào tập trung hỏi trong vùng này theo cách tương tự

Khối chuyên tin:

  • TRASH: Xét mỗi vị trí đoạn thứ i, ta có thể chặc nhị phân hoặc dùng 1 biến tăng dần từ trái sang phải để xác định đoạn j nhỏ nhất sau cho j < i và tổng từ đoạn j đến đoạn i <= m. Đpt là O(nlogn) với cách chặc nhị phân hoặc O(n) với cách dùng biến chạy.
  • SQUARES: Đây chỉ đơn giản là bài toán tính tổng của dãy cấp số nhân, sau một vài phép tính ta có kết quả là: L^2 * (4 ^ (N+1) – 1) / 3
  • RECOVERY: Đi từ số thứ n trở về số đầu tiên, ta thấy số ở vị trí a[n] cần được giữ nguyên, xét số ở vị trí a[n-1], nếu số này lớn hơn a[n], ta cần xóa đi 1 số lượng chữ số ít nhất đảm bảo kết quả a[n-1] <= a[n] và a[n-1] lớn nhất có thể, sau đó ta lại tiếp tục xét số a[n-2] và xóa chữ số đi nếu cần thiết giống cách ta xử lí số a[n-1]…. Do việc ưu tiên số lượng chữ số bị xóa đi ít nhất đồng thời cũng sẽ tỉ lệ thuận với việc số còn lại là lớn nhất nên thuật toán tham này chạy đúng.
    • Ta sẽ phải giải quyết bài toán con: Cho 2 số a, b, ta cần xóa đi 1 số lượng chữ số ít nhất ở số a sao cho a <= b và a có giá trị lớn nhất có thể. Giả sử a > b, với trường hợp ta xóa sao cho số lượng chữ số của a bằng số lượng chữ số của b, a <= b và a lớn nhất ta có thể quy hoạch động, trường hợp ta cần xóa sao cho số lượng chữ số của a nhỏ hơn số lượng chữ số của b thì chỉ cần xử lí tham là đủ.
  • GUIDE: Bài này có nhiều lời giải nhưng mình sẽ chỉ cách làm bằng LCA, bạn nào chưa biết về LCA thì có thể xem tại (http://vnoi.info/wiki/algo/data-str…). Xây dựng các cây(có thể có nhiều cây riêng biệt). Với mỗi truy vấn s – f, có 3 trường hợp:
    • f và s thuộc 2 cây khác nhau, trả về kết quả là -1
    • s và f nằm trong cùng 1 cây, f nằm trong cây con góc s, điều này xảy ra nếu s = LCA(s, f). Với trường hợp này ta xác định độ sâu chênh lệch d giữa s và f, sau đó từ f nhảy lên d-1 bước là ra được đỉnh kết quả.
    • s và f nằm tỏng cùng 1 cây, f không nằm trong cây con góc s. Kết quả trong trường hợp này, ta trả về cha của s.

Khối không chuyên:

  • PALIN: Do độ dài xâu S <= 10000 nên hoàn toàn ta có thể làm thuật toán O(n^2) xét hết tất cả các xâu con và kiểm tra palindrome bằng kĩ thuật Hash xâu (http://vnoi.info/wiki/algo/string/h…). Mặc khác ta có thể giải bài toán này với đpt O(nlogn) bằng phương pháp chặc nhị phân ở từng vị trí của xâu để tìm xâu palindrome dài nhất (nhớ xử lí trường hợp xâu độ dài chẵn/lẻ). Ngoài ra ta cũng có thể giải bài toán này với đpt O(n) với việc sử dụng thuật toán Manacher để tìm xâu palindrome xài nhất.
  • TRASH: Xem lời giải bài này ở khối chuyên tin.
  • PRIMETAB: Trước tiên ta cần dùng thuật toán sàng số nguyên tố(http://vnoi.info/wiki/translate/he/…) để xác định số nguyên tố trong bảng được cho. Kết quả đưa về bảng số 0, 1. Giờ ta cần xử lí truy vấn từ dòng x đến dòng y có tồn tại một hình chữ nhật toàn số 1 với kích thước r * c hay không. Ta cần cài đặt 2 lời giải riêng biệt tùy vào input:
    • Xét trường hợp m <= n ( suy ra được m <= sqrt(m*n) ), ta quy hoạch động O(m^2 * n) để tính mảng f[r][i] = c là giá trị lớn nhất mà tại hàng i tồn tại hình chữ nhật toàn số 1 có kích thước r * c, trong đó dòng đầu tiên của hình chữ nhật ở vị trí i. Như vậy với mỗi truy vấn ta sẽ xét tất cả các giá trị r2 >= r và kiểm tra xem giá trị lớn nhất từ f[r2][x] đến f[r2][y-r2+1] có lớn hơn hoặc bằng c hay không? Để kiểm tra giá trị lớn nhất nhanh ta sẽ dùng cây phân đoạn (http://vnoi.info/wiki/algo/data-str…)
    • Xét trường hợp m > n ( suy ra được n <= sqrt(m * n) ), tương tự ta quy hoạch động O(m * n^2) để tính mảng g[c][i] = r là giá trị lớn nhất mà tại hàng i tồn tại hình chữ nhật toán số 1 có kích thước r * c, trong đó dòng đầu tiên của hình chữ nhật ở vị trí i. Như vậy với mỗi truy vấn ta sẽ xét tất cả các giá trị c2 >= c và kiểm tra xem giá trị lớn nhất từ g[c2][i] đến g[c2][y-r+1] có lớn hơn hoặc bằng r hay không?

Khối cao đẳng:

  • NPRIME: Chỉ cần viết được hàm kiểm tra số nguyên tố chạy trong O(sqrt(n)) là có thể làm được bài này. Cách làm tốt hơn là dùng sàn số nguyên tố (http://vnoi.info/wiki/translate/he/…)
  • LRPALIND: Kiểm tra palindrome bằng kĩ thuật Hash xâu (http://vnoi.info/wiki/algo/string/h…).
  • TRASH: Xem lời giải bài này ở khối chuyên tin.

Thuật toán Kruskal tìm cây khung nhỏ nhất

Định nghĩa cây khung – Cây khung nhỏ nhất

Cho đồ thị vô hướng, cây khung (spanning tree) của đồ thị là một cây con chứa tất cả các đỉnh của đồ thị. Nói cách khác, cây khung là một tập hợp các cạnh của đồ thị, không chứa chu trình và kết nối tất cả các đỉnh của đồ thị.

Trong đồ thị có trọng số, cây khung nhỏ nhất là cây khung có tổng trọng số các cạnh nhỏ nhất. Định nghĩa tương tự với cây khung lớn nhất.

Thuật toán Kruskal

Ban đầu mỗi đỉnh là một cây riêng biệt, ta tìm cây khung nhỏ nhất bằngcách duyệt các cạnh theo trọng số từ nhỏ đến lớn, rồi hợp nhất các cây lại với nhau.

Cụ thể hơn, giả sử cạnh đang xét nối 2 đỉnh u và v nếu 2 đỉnh này nằm ở 2 cây khác nhau thì ta thêm cạnh này vào cây khung, đồng thời hợp nhất 2 cây chứa u và v.

Để thực hiện thao tác trên một cách nhanh chóng, ta sử dụng cấu trúc Disjoint Set, độ phức tạp của toàn bộ thuật toán là O(M log M) với M là số cạnh.

Cài đặt

Đoạn code dưới cài đặt thuật toán Kruskal, có thể dùng để nộp bài

QBMST.

#include <iostream>
#include <vector>
#include <algorithm> // Hàm sort
using namespace std;
 
// Cấu trúc để lưu cạnh đồ thị,
// u, v là 2 đỉnh, w là trọng số cạnh
struct edge {
    int u, v, w;
};
// Hàm so sánh để dùng trong hàm sort ở dưới
bool cmp(const edge &a, const edge &b) {
    return a.w < b.w;
}
 
// Số đỉnh tối đa trong đề bài
#define N 10005
 
// 2 mảng sử dụng trong Disjoint Set
int cha[N], hang[N];
 
// Tìm xem u thuộc cây nào
int find(int u) {
    if (cha[u] != u) cha[u] = find(cha[u]);
    return cha[u];
}
 
// Hợp nhất 2 cây chứ u và v,
// Trả về false nếu không thể hợp nhất
bool join(int u, int v) {
    u = find(u); v = find(v);
    if (u == v) return false;
    if (hang[u] == hang[v]) hang[u]++;
    if (hang[u] < hang[v]) cha[u] = v;
    else cha[v]=u;
    return true;
}
 
int main() {
    // Thêm dòng này để cin, cout chạy nhanh
    ios::sync_with_stdio(false); cin.tie(0);
 
    // Nhập vào số đỉnh và số cạnh
    int n, m; cin >> n >> m;
 
    // Nhập danh sách các cạnh
    vector<edge> edges(m);
    for (edge &e: edges) cin >> e.u >> e.v >> e.w;
 
    // Sắp xếp lại các cạnh theo trọng số tăng dần
    sort(edges.begin(), edges.end(), cmp);
 
    // Khởi tạo cấu trúc Disjoint Set
    for (int i=1; i<=n; i++) {
        cha[i] = i;
        hang[i] = 0;
    }
 
    // Lưu tổng trọng số các cạnh trong cây khung nhỏ nhất
    int mst_weight = 0;
 
    // Duyệt qua các cạnh theo thứ tự đã sắp xếp
    for (edge &e: edges) {
        // Thử hợp nhất 2 cây chứa u và v
        if (join(e.u, e.v)) {
            // Hợp nhất thành công, ta thêm e và kết quả
            mst_weight += e.w;
        }
    }
 
    // Xuất kết quả
    cout << mst_weight;
    return 0;
}

Thuật toán sắp xếp tuần tự

Bài toán đặt ra

Cho mảng A gồm n phần tử. Sắp xếp lại dãy A theo chiều giảm dần

Nhập vào: số nguyên dương n và dãy A.

8
9 7 6 15 16 5 10 11
Xuất ra: dãy A sau khi đã được sắp xếp
5 6 7 9 10 11 15 16

Ý tưởng

Tư duy đơn giản như cách chúng ta xếp bài

sap-xep-1-yeulaptrinhHình trên là thao tác xếp cây bài 7 bằng cách rút nó ra và đặt vào vị trí của phù hợp.

Giải sử bài trên tay đang là:

2 5 7 10 4

ta thấy dãy 2,5,7,10 đã tăng dần chỉ còn cây 4 đứng chưa đúng chỗ nên ta đẩy 4 lên trước 10, rồi lên trước 7 cứ như vậy đến khi gặp cây 2 đứng trước. 2 < 4 suy ra thì dừng. Dãy trở thành

2 4 5 7 10

Dãy đã được sắp xếp.

Ý tưởng: duyệt lần lượt từng cây bài, nếu cây bài nhỏ thì ta đẩy dần lên đầu đến khi nào không chuyển lên được nữa

Ví dụ khác:

sap-xep-yeulaptrinh.pwCode:

#include <bits/stdc++.h>

using namespace std;

int n, a[10000];

void doi_cho(int *x, int *y) {
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

int main() {
    cin >> n;
    for (int i=1; i<=n; i++) cin >> a[i];
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<i; j++)
            if (a[j] > a[i])
            {
                doi_cho(&a[i], &a[j]);
            }
    }
    for (int i=1; i<=n; i++) cout << a[i] << " ";
    return 0;
}
Ví dụ:

Với dãy A = {12, 11, 13, 5, 6}

Cho i chạy từ 1 đến 4

i=1. không làm gì cả

12, 11, 13, 5, 6

i = 2. Vì 11 nhỏ hơn 12 nên chuyển 11 lên trước 12
11, 12, 13, 5, 6

i = 3. 13 không cần chuyển lên đầu nữa
11, 12, 13, 5, 6

i = 4. 5 được chuyển chỗ với 13 rồi chuyển chố tiếp lần lượt với 12, 11.
5, 11, 12, 13, 6

i = 5. 6 cũng giông như 5 được chuyển dần lên đến khi gặp 5 nhỏ hơn thì dừng lại
5, 6, 11, 12, 13

Độ phức tạp:

  • O(n^2)

 

Quý bạn đọc có ý kiến, thắc mắc xin comment bên dưới <3

Tìm kiếm nhị phân (chặt nhị phân) toàn tập

Đã lâu rồi mình chưa viết bài mới, hôm nay mình xin chia sẻ với các bạn cách code thuật toán tìm kiếm phân mà mình thường sử dụng.

Chắc mọi người cũng biết, cùng một thuật toán tìm kiếm nhị phân nhưng có rất nhiều cách code khác nhau, tất cả đều chính xác, tốc độ nhanh như nhau. Và cách mình chia sẻ dưới đây là một trong những cách dễ hiểu nhất, linh hoạt nhất mà tốc độ chạy cũng khá tốt (cách này của anh Kiên – HCB Olympic Tin học Quốc tế)

Dãy con tăng – Tìm phần tử lớn nhất nhỏ hơn x (chỉ số lớn nhất)

// day con tang – tim phan tu lon nhat nho hon x ( chi so lon nhat);

function tim2(r,x : longint) : longint;

  var d,c,g : longint;

  begin

    d:=0;c:=r;

    g:=(d+c) div 2;

    while (g<>d) and (g<>c) do

      begin

        if b[g]>=x then c:=g else d:=g;

        g:=(d+c) div 2;

      end;

    for g:=c downto  d do

      if b[g]<x then exit(g);

   end;

Dãy con tăng – Tìm số bé nhất lớn hơn hoặc bằng x (chỉ số bé nhất)

// day con tang – so be nhat lon hon hoac bang x (chi so be nhat);

sort(a);

left=1, right=n;
i = (left + right) / 2;

while (left != i) and (i != right) do
    if a[i]>=k then right = i;
    else left = i;
    i = (left + right) / 2;

for i = left to right do

if a[i]>=k then return a[i];

print “Not found”

Dãy con tăng – Tìm số bé nhất lớn hơn hoặc bằng x (chỉ số lớn nhất)

// day con tang – so be nhat lon hon hoac bang x ( chi so lon nhat);

sort(a);

left=1, right=n;
i = (left + right) / 2;

while (left != i) and (i != right) do
    if a[i]>k then right = i;
    else left = i;
    i = (left + right) / 2;

for i = right to left do

if a[i]<=k then return a[i];

print “Not found”

Dãy con giảm – Tìm phần tử cuối cùng lớn hơn x

//day con giam – tim phan tu cuoi cung lon hon x

function tim1(r,x : longint) : longint;

  var d,c,g : longint;

  begin

    d:=0;c:=r;

    g:=(d+c) div 2;

    while (g<>d) and (g<>c) do

      begin

        if b[g]>x then d:=g else c:=g;

        g:=(d+c) div 2;

      end;

    for g:=c downto d do

      if b[g]>x then exit(g);

  end;

Dãy con giảm – Tìm phẩn tử đầu tiên nhỏ hơn x

//day con giam – tim phan tu dau tien nho hon x

function tim1(r,x : longint) : longint;

  var d,c,g : longint;

  begin

    d:=0;c:=r;

    g:=(d+c) div 2;

    while (g<>d) and (g<>c) do

      begin

        if b[g]>x then d:=g else c:=g;

        g:=(d+c) div 2;

      end;

    for g:=d to c do

      if b[g]>x then exit(g);

  end;

Các bài khác nhau với các yêu cầu tìm kiếm khác nhau bạn có thể dễ dàng sửa đổi cho phù hợp nếu sử dụng cách tìm kiếm nhị phân mình vừa trình bày.

Mọi thắc mắc rất mong nhận được từ quý bạn đọc <3