ĐỀ CƯƠNG CHI  TIẾT KHÓA HỌC

Tìm hiểu cấu trúc dữ liệu Hàng đợi hai đầu, cho phép thao tác ở đầu và cuối tập hợp với độ phức tạp chỉ O(1); và cách ứng dụng CTDL này vào các bài toán thực tế.

Ứng dụng vào các bài toán như:

  • Tìm phần tử lớn nhất trong mỗi mảng con kích thước K.
  • Tìm mảng con ngắn nhất có tổng các phần tử lớn hơn bằng K.
  • Tìm hình chữ nhật con chứa toàn số 1 có kích thước lớn nhất trong ma trận.

    • Tìm hiểu khái niệm về hàm băm, bảng băm, phương pháp Polynomial để xây dựng hàm băm.

    Ứng dụng vào các bài toán như:

  • Tìm kiếm vị trí xuất hiện của chuỗi T trong chuỗi S.
  • Kiểm tra xâu đối xứng với độ phức tạp chỉ O(1) (chưa tính phần tiền xử lý).
  • Đếm số lần xuất hiện của các tiền tố trong chuỗi.
  • Tìm đoạn trùng nhau dài nhất của hậu tố chuỗi T và tiền tố chuỗi S.

    • Tìm hiểu về bảng thưa – một cấu trúc dữ liệu cho phép giải quyết các bài toán (truy vấn) theo dạng khoảng (range query) trên một tập dữ liệu cố định.

  • Tìm phần tử nhỏ nhất trong đoạn L tới R chỉ trong O(1) (chưa tính phần tiền xử lý).
  • Kiểm tra xâu đối xứng với độ phức tạp chỉ O(1) (chưa tính phần tiền xử lý).
  • Tính tổng các phần tử trong đoạn L tới R chỉ trong O(logN) (chưa tính phần tiền xử lý).
  • Tìm số đoạn từ L tới R thỏa mãn một tính chất cho trước.
  • Tính độ chênh lệch của phần tử nhỏ nhất và lớn nhất trong đoạn L tới R.
  • Tìm độ dài cạnh của ma trận vuông con đối xứng lớn nhất.
  • Tìm phần tử xuất hiện nhiều lần nhất trong đoạn từ L tới R trên mảng không giảm.
  • Tìm ký tự mà con trỏ ở 2 đầu xâu đang chỉ đến sau các lần di chuyển.
  • Giúp một nhà khoa học tìm chi phí ít nhất để mua enzyme sao cho mỗi giờ đều có enzyme để sử dụng, biết rằng chi phí để mua enzyme mỗi giờ là khác nhau, và enzyme không thể tồn tại quá h giờ.
  • …

    • Tìm hiểu về cấu trúc dữ liệu Cây phân đoạn, giúp giải quyết các bài toán trên dãy số có sự thay đổi và cập nhật thường xuyên.

    Ứng dụng vào các bài toán như:

  • Tìm phần tử nhỏ nhất trong đoạn L tới R.
  • Tính tổng các phần tử trong đoạn L tới R.
  • Tính thể tích lớn nhất cho chiếc bánh sinh nhật, biết rằng một tầng bánh chỉ có thể được đặt trên tầng bánh khác có thể tích lớn hơn.
  • Kiểm tra tính “thú vị” của mảng, biết rằng một mảng thú vị khi m mảng con [Li, Ri] thỏa mãn: kết quả phép AND của tất cả phần tử trong mảng con này bằng với một số cho trước.
  • Thực hiện một loạt truy vấn sao chép một phần mảng con A sang một phần của mảng con B, rồi tìm giá trị tại vị trí x của mảng B sau tất cả truy vấn.
  • Tìm mảng con có số lượng cặp ngoặc tròn đúng lớn nhất.

    • Tìm hiểu về cấu trúc dữ liệu Fenwick Tree (hay Binary Indexed Tree – BIT) – một cấu trúc dữ liệu được sử dụng rất phổ biến trong lập trình thi đấu.

    Ứng dụng vào các bài toán như:

  • Tính tổng các phần tử trong các đoạn cho trước.
  • Tìm chiều cao lớn nhất của tháp vòng, biết rằng vòng j chỉ có thể đặt trên vòng i khi bán kính ngoài của vòng j lớn hơn bán kính trong của vòng i; và nhỏ hơn hoặc bằng bán kính ngoài của vòng i.
  • Tìm giá trị phần tử thứ k của mảng, sau một loạt các truy vấn thay đổi giá trị các phần tử theo đoạn.
  • Đếm tổng số thừa số nguyên tố của i + 1 phần tử đầu tiên và tìm tất cả “số nguyên tố ngược” có 7 chữ số trong mảng.
  • Tìm tất cả dãy con khác biệt không giảm. Với mỗi dãy con như vậy, tìm dãy “không vượt quá” dãy con này.
  • Tìm tổng khoảng cách nhỏ nhất bất kể thời điểm của n cặp điểm trên trục Ox, biết rằng điểm thứ i di chuyển trên trục Ox với vận tốc vi.

    • Tìm hiểu các thuật toán giải quyết bài toán Lowest Common Ancestor và cách áp dụng chúng vào các bài toán thực tế.

    Ứng dụng vào các bài toán như:

  • Tìm số đường đi đi qua một cạnh trên đồ thị dạng cây.
  • Tìm tổng khoảng cách nhỏ nhất đi từ c đến a và b trên đồ thị gồm n đỉnh và n cạnh 1 chiều.
  • Tìm đường đi ngắn nhất giữa đỉnh trên đồ thị dạng cây.
  • Tìm độ dài xâu con tốt dài nhất, biết xâu tốt khi số lượng nguyên âm bé hơn hoặc bằng 2 lần số lượng phụ âm.
  • Tìm số vé ít nhất để đi từ thành phố A đến thành phố B trong quốc gia cho trước.
  • Tính tổng trọng số của tất cả các node trên một cây con.
  • Với mỗi truy vấn [L, R], tính f(L, R) cho đoạn đó, với f(L, R) cho trước.
  • Với mỗi truy vấn [L, R], đếm số lượng đoạn con tăng chậm trong đoạn từ L tới R, biết đoạn con liên tiếp tăng chậm khi phần tử đứng sau lớn hơn phần tử đứng trước đúng 1 đơn vị. Ngoài ra, còn có các truy vấn thay đổi các phần tử.

    • Tìm hiểu thuật toán Knuth-Morris-Pratt tìm vị trí chuỗi T xuất hiện trong chuỗi S.

    Ứng dụng vào các bài toán như:

  • Xác định cách chia xâu S thành nhiều xâu con bằng nhau nhất.
  • Đếm số lần xuất hiện của một mẫu kích thước X × Y trong ma trận N × M.
  • Tìm xâu ngắn nhất chứa cả 3 xâu s1, s2 và s3.

    • Tìm hiểu cách xây dựng mảng Z-Function của một chuỗi và ứng dụng nó giải quyết các bài toán về chuỗi.

    Ứng dụng vào các bài toán như:

  • So khớp chuỗi, tìm vị trí chuỗi P xuất hiện trong chuỗi S.
  • Đếm số xâu con phân biệt của một chuỗi.
  • Tìm số cách chọn K xâu con liên tiếp bằng nhau của một chuỗi.
  • Tìm chu kỳ nhỏ nhất của một chuỗi.

    • Tìm hiểu cấu trúc dữ liệu cây tiền tố dùng để lưu trữ danh sách các phần tử trên cây.

    Ứng dụng vào các bài toán như:

  • Lưu trữ một lượng từ ngữ lớn.
  • Gợi ý tìm kiếm trên các công cụ tìm kiếm.
  • Chức năng autocomplete.
  • Tìm kiếm nhanh các chuỗi có tiền tố là chuỗi T.
  • Tìm từ xuất hiện nhiều lần nhất và có tiền tố là chuỗi T.

    • Kỳ thi giữa kỳ.

    Tìm hiểu cấu trúc dữ liệu mảng hậu tố - một loại cấu trúc dạng mảng rất mạnh để giải quyết các bài toán xử lý chuỗi ; thuật toán Prefix Doubling và cách tối ưu hóa thuật toán này để xây dựng mảng hậu tố.

    Ứng dụng vào các bài toán như:

  • Tìm độ dài tiền tố chung lớn nhất giữa các hậu tố liên tiếp (Longest Common Prefix)
  • Tìm chuỗi con T dài nhất xuất hiện ít nhất 2 lần trong chuỗi (Longest repeated substring).
  • Tìm xâu con chung dài nhất giữa hai chuỗi.
  • Tìm xâu con chung dài nhất giữa K chuỗi.
  • Đếm số lượng xâu con phân biệt của một chuỗi.
  • Tìm xâu con trong S mà có thứ tự từ điển thứ k.
  • Đếm số lượng các xâu con phân biệt bắt đầu bằng mỗi chữ cái.

    • Tìm hiểu thuật toán Manacher ứng dụng vào các bài toán xâu con đối xứng.

    Ứng dụng vào các bài toán như:

  • Tìm xâu con đối xứng dài nhất trong một chuỗi (Longest Palindromic Substring).
  • Tìm và in ra số lượng xâu con là xâu đối xứng dài nhất của một chuỗi.
  • Đếm số lượng xâu con đối xứng phân biệt của một chuỗi.
  • Đếm số lượng xâu con đối xứng tạo thành số nguyên chia hết cho 3 trong một chuỗi gồm các chữ số.

    • Tìm hiểu các khái niệm cơ bản trong toán tổ hợp như tổ hợp, chỉnh hợp, hoán vị, tổ hợp lặp, chỉnh hợp lặp, hoán vị lặp, tam giác Pascal... và định lý Đồng dư Trung Hoa dùng để giải hệ phương trình đồng dư bậc nhất.

    Ứng dụng vào các bài toán như:

  • Đếm số mảng có thể xây dựng được thỏa mãn các tính chất cho trước.
  • Tìm số cách để điền vào một vị trí còn trống trong mảng sao cho mảng được cho là một « dãy tốt ».
  • Tìm tổng số cách để hoàn thành tất cả công việc cho trước.
  • Tính tổng P = C(N,0)−C(N,1)+C(N,2)−C(N,3)+...+C(N,N).
  • Đếm số lượng hình chữ nhật con trong ma trậm N × M sao cho có 1 cách sắp xếp trên các xâu trên hàng và cột đều là xâu đối xứng.
  • Kiểm tra xem 2 chuỗi có cùng số lượng xâu con phân biệt hay không.
  • ...

    • Tìm hiểu các khái niệm từ cơ bản về tính xác suất như không gian mẫu, biến cố, quy tắc nhân, quy tắc cộng,… đến nâng cao như biến ngẫu nhiên, giá trị kỳ vọng, tính tuyến tính của kỳ vọng,…

    Ứng dụng vào các bài toán như:

  • Tính xác suất để tung N đồng xu để được chính xác K đồng xu ra mặt đầu.
  • Chọn ngẫu nhiên một số p trong đoạn [pL , pR], và một số v trong đoạn [vL , vR]. Tính xác suất để đoạn [min(v, p), max(v, p)] có đúng k số may mắn.
  • Tính xác suất để quả banh cuối cùng sau các thủ thuật của nhà ảo thuật là màu đen.

    • Tìm hiểu nguyên lý bao hàm – loại trừ dùng để tính kích thước tập hợp gộp (hợp) của các tập hợp con.

    Ứng dụng vào các bài toán như:

  • Tính tổng các phần tử trong đoạn [L, R] trên mảng.
  • Đếm số lượng số nguyên trong đoạn [L, R] mà nguyên tố cùng nhau với N.
  • Đếm số bộ nghiệm thỏa mãn phương trình x1 + x2 + ⋯ + xm = k.
  • Đếm số lượng hoán vị tốt của n cặp số nguyên cho trước.
  • Đếm số bộ 4 số có UCLN bằng 1 trên dãy gồm N số.
  • Tìm các số từ 1 đến N không chia hết cho bất kỳ số nào trong dãy cho trước.
  • Đếm số lượng các mảng con nguyên tố cùng nhau trên mảng.

    • Tìm hiểu về dãy số Catalan, cách xây dựng dãy số Catalan và các ứng dụng của dãy số này.

    Ứng dụng vào các bài toán như:

  • Đếm số cây BST khác nhau với các node là các số « perfect power » nằm trong đoạn [a, b], biết rằng số m là « perfect power » khi tồn tại x > 1 và y > 1, sao cho m = x^y.
  • Đếm số cách để một nhóm N người xếp thành vòng tròn có thể bắt tay với nhau mà không đè lên nhau.
  • Tìm số hoán vị phân biệt tăng dần của N số.
  • Đếm số các số trong khoảng [n, m] sao cho số đó không chia hết cho a hoặc (a+d) hoặc (a+2d) hoặc (a+3d) hoặc (a+4d).
  • Tính giá trị dự đoán số người đang đứng trên thang cuốn ở thời điểm thứ t.
  • Tính xác suất con mã sau k nước đi vẫn ở trên bàn cờ.
  • ...

    • Kiểm tra cuối kỳ.