Các Bài Toán Nhập Môn là bước khởi đầu trong hành trình học Competitive Programming, giúp xây dựng nền tảng tư duy thuật toán và kỹ năng lập trình cơ bản. Lộ trình tập trung vào việc phân tích đề bài, tìm quy luật, thiết kế thuật toán và triển khai lời giải hiệu quả thông qua các kỹ thuật như mô phỏng, toán học, tham lam, tìm kiếm toàn bộ, đệ quy, quay lui và xử lý bit.

Đăng nhập để tham gia lộ trình luyện tập

Các Bài Toán Nhập Môn

Giới thiệu

Chương Introductory Problems là bước khởi đầu trong quá trình học Competitive Programming, tập trung vào việc xây dựng các kỹ năng nền tảng cần thiết trước khi tiếp cận những thuật toán và cấu trúc dữ liệu nâng cao.

Các bài toán trong chương này giúp người học rèn luyện khả năng:

  • Phân tích đề bài và mô hình hóa vấn đề.
  • Nhận diện quy luật toán học.
  • Thiết kế thuật toán đơn giản nhưng hiệu quả.
  • Cài đặt lời giải chính xác với độ phức tạp phù hợp.

Mục tiêu chính của chương không chỉ là giải được từng bài toán riêng lẻ, mà là hình thành tư duy thuật toán: từ việc quan sát cấu trúc bài toán, tìm ra ý tưởng, chứng minh tính đúng đắn, đến triển khai chương trình hoàn chỉnh.

Kiến thức trọng tâm

1. Algorithmic Thinking

Rèn luyện quy trình giải quyết bài toán:

  1. Hiểu yêu cầu và giới hạn dữ liệu.
  2. Xây dựng mô hình toán học.
  3. Tìm kiếm cấu trúc hoặc quy luật.
  4. Thiết kế thuật toán.
  5. Phân tích độ phức tạp.
  6. Cài đặt và kiểm thử.

Độ phức tạp thuật toán được biểu diễn bằng ký hiệu:

O(f(n))O(f(n))

Một số mức thường gặp:

O(1), O(log⁡n), O(n), O(nlog⁡n), O(n2)O(1),\ O(\log n),\ O(n),\ O(n\log n),\ O(n^2)

2. Simulation

Làm quen với các bài toán mô phỏng, trong đó lời giải được xây dựng bằng cách tái hiện trực tiếp quá trình biến đổi của trạng thái.

Các kỹ thuật:

  • Duyệt tuần tự.
  • Cập nhật trạng thái.
  • Quản lý biến.
  • Xử lý điều kiện.

3. Mathematics

Phát triển khả năng nhận biết và khai thác các tính chất toán học.

Bao gồm:

  • Công thức số học.
  • Quy luật dãy số.
  • Đếm và tổ hợp cơ bản.
  • Phép toán modulo.

Ví dụ:

(a+b) mod m(a+b)\bmod m

và

ab mod ma^b \bmod m

4. Greedy Techniques

Giới thiệu tư duy tham lam:

Ở mỗi bước, lựa chọn phương án tốt nhất tại thời điểm hiện tại với kỳ vọng dẫn đến nghiệm tối ưu.

Các bài toán dạng này yêu cầu khả năng:

  • Nhận diện cấu trúc tối ưu.
  • Chứng minh lựa chọn cục bộ.
  • Xây dựng đáp án.

Làm quen với phương pháp tìm kiếm toàn bộ không gian trạng thái khi kích thước bài toán cho phép.

Các kỹ thuật:

  • Sinh tập con.
  • Sinh hoán vị.
  • Duyệt trạng thái.
  • Kiểm tra tất cả khả năng.

Một số không gian tìm kiếm phổ biến:

2n2^n

và

n!n!

6. Recursion and Backtracking

Giới thiệu phương pháp giải bài toán bằng đệ quy và quay lui.

Các khái niệm:

  • Trạng thái.
  • Quyết định.
  • Chuyển trạng thái.
  • Khôi phục trạng thái.

Mô hình tổng quát:

F(state)=∑F(next_state)F(state)=\sum F(next\_state)

7. Bit Manipulation

Làm việc với dữ liệu ở mức bit.

Bao gồm:

  • Biểu diễn nhị phân.
  • Các phép toán bit.
  • Tính chất XOR.
  • Tối ưu hóa bằng bit.

Một số tính chất quan trọng:

x⊕x=0x \oplus x = 0 x⊕0=xx \oplus 0 = x

Kỹ năng đạt được

Sau khi hoàn thành chương này, người học có thể:

  • Giải quyết các bài toán thuật toán cơ bản.

  • Phân tích giới hạn và lựa chọn phương pháp phù hợp.

  • Viết chương trình có độ phức tạp hợp lý.

  • Làm nền tảng cho các chủ đề tiếp theo:

    • Sorting and Searching.
    • Dynamic Programming.
    • Graph Algorithms.
    • Data Structures.
    • Advanced Algorithms.

Yêu cầu hoàn thành

Một bài toán được xem là hoàn thành khi người học có thể:

  • Tự xây dựng ý tưởng giải.
  • Giải thích được tính đúng đắn của thuật toán.
  • Phân tích độ phức tạp.
  • Cài đặt lời giải độc lập.

Phần 1. Các Bài Toán Nhập Môn

Mở

Bài toán Tried AC Độ khó
PH001   Thuật toán kỳ lạ (Weird Algorithm) 23 7 1
PH002   Số Bị Thiếu (Missing Number) 31 7 1
PH003   Các đoạn lặp liên tiếp (Repetitions) 11 5 1
PH004   Mảng không giảm (Increasing Array) 20 6 1
PH005   Hoán vị đẹp (Permutations) 19 5 1
PH006   Xoắn ốc số (Number Spiral) 4 1 1
PH007    Hai quân mã (Two Knights) 1 1 1
PH008   Hai tập hợp (Two Sets) 7 3 1
PH009   Xâu bit (Bit Strings) 4 1 1
PH010   Số chữ số 0 tận cùng (Trailing Zeros) 1 1 1
PH011   Hai đống xu (Coin Piles) 2 1 1
PH012   Sắp xếp thành xâu đối xứng (Palindrome Reorder) 8 1 1
PH013   Mã Gray (Gray Code) 6 1 1
PH014   Tháp Hà Nội (Tower of Hanoi) 1 1 1
PH015   Tạo các chuỗi (Creating Strings) 2 1 1
PH016   Chia táo (Apple Division) 2 1 1
 
Người tham gia
8
Tạo bởi
  1. Danh sách tác vụ
  1. Language
  2. Chế độ cũ
  3. Giao diện
  3. Worker 0, 40ms
  4. Powered by Hydro v5.0.4 Community