hello
đã đăng vào 22, Tháng 12, 2025, 2:40downvote toi di
VNOI Wiki: Kỹ thuật sinh test
dvtd
đã đăng vào 21, Tháng 12, 2025, 4:56
🖐️ Xin chào các bạn, trong bài viết lần này, VNOI Wiki xin giới thiệu đến các bạn nội dung về Kỹ thuật sinh test. Đây là kỹ năng thực chiến quan trọng trong mọi kỳ thi, giúp bạn chủ động phát hiện những lỗi sai mà test ví dụ thường bỏ sót, đồng thời kiểm soát chặt chẽ thời gian chạy của thuật toán trong trường hợp xấu nhất.
💻 Bài viết hệ thống hóa toàn bộ kiến thức về Kỹ thuật sinh test, trải dài từ tư duy lý thuyết đến ứng dụng thực tiễn, bao gồm:
Vai trò của sinh test trong việc phát hiện lỗi và kiểm soát thời gian chạy trong các kỳ thi Offline/Online, đặc biệt là tại kỳ thi Học sinh giỏi Quốc gia môn Tin học sắp tới.
Phương pháp xây dựng Code "trâu", Code chuẩn và Generator hiệu quả.
Kỹ thuật sinh test random hiệu quả, đo thời gian chạy và template trình chấm tự động.
🔗 Link bài viết: Kỹ thuật sinh test, tự kiểm tra code | VNOI Wiki
✍️ Biên soạn: Nguyễn Quang Minh - Michigan State University.
✅ Reviewers:
- Lê Minh Hoàng - Trường Đại học Khoa học Tự nhiên, ĐHQG-HCM.
Võ Đức Đoàn - THPT Chuyên Nguyễn Tất Thành, Quảng Ngãi.
Nguyễn Tiến Mạnh - Đại học Bách khoa Hà Nội.
Nguyễn Tấn Minh - Trường Đại học Khoa học Tự nhiên, ĐHQG-HCM.
💖 VNOI xin cảm ơn đội ngũ TNV và Admin đã dành tâm huyết hoàn thiện nội dung này. Mong rằng các bạn sẽ nắm vững và vận dụng thành thạo kỹ thuật sinh test trong quá trình luyện tập. Đừng quên theo dõi VNOI để đón đọc những bài viết tiếp theo nhé!
✨ Chúc các bạn ôn luyện hiệu quả và đạt kết quả cao nhất trong kỳ thi HSGQG sắp tới!
Chủ đề sinh test
đã đăng vào 20, Tháng 12, 2025, 15:14Mẹo sinh test cực nhanh
Bình thường các bạn làm bài như nào thì cứ làm như thế(tạo project xog add INP và OUT rồi làm)
Khi muốn sinh test và so sánh code trâu và code full thì tạo 1 folder mới
- Tạo file main_trau.cpp và dán code trâu vào
- Tạo file main.cpp và dán code full vào
- Tạo file test.cpp và code sinh test(có thể đọc ở dưới blog của tôi)
Sử dụng lệnh cmd để build file cpp ra exe:
** ĐỂ CHẠY NHANH THÌ CÁC BẠN COPY HẾT CẢ 3 DÒNG VÀ CLICK CHUỘT PHẢI VÀO CMD, KHÔNG PHẢI COPY TỪNG DÒNG 1 VÀ CHẠY TỪNG LỆNH 1
g++ test.cpp -o test
g++ main.cpp -o main
g++ main_trau.cpp -o main_trau
Cuối cùng là chạy test.exe
Quy Hoạch Động Là Gì ?
đã đăng vào 14, Tháng 12, 2025, 15:33Quy hoạch động (DP) là một kỹ thuật thuật toán thường dựa trên một công thức truy hồi và một (hoặc một vài) trạng thái khởi đầu. Một lời giải con của bài toán được xây dựng từ các lời giải trước đó. Các thuật toán DP có độ phức tạp đa thức, giúp đảm bảo thời gian chạy nhanh hơn nhiều so với các kỹ thuật khác như quay lui (backtracking) hay brute-force.
I. BÀI TOÁN ĐỔI TIỀN
Cho một danh sách gồm N đồng xu với giá trị V1, V2, ..., VN và một tổng tiền cần đạt được là S. Hãy tìm số lượng đồng xu ít nhất sao cho tổng của chúng bằng S (có thể sử dụng một đồng xu nhiều lần), hoặc kết luận rằng không thể chọn được tập hợp đồng xu thỏa mãn điều kiện.
- Xác định trạng thái
Ta gọi Min[i] là số lượng đồng xu ít nhất để tạo ra tổng i (với i ≤ S). Trạng thái nhỏ hơn của i là mọi Min[j] với j < i.
- Khởi tạo
- Min[0] = 0 (tổng 0 không cần đồng xu nào)
- Với mọi i > 0: Min[i] = ∞
- Công thức truy hồi
Với mỗi i từ 1 đến S:
- Với mỗi đồng xu Vj sao cho Vj ≤ i: Min[i] = min(Min[i], Min[i - Vj] + 1)
- Ví dụ minh họa
Các đồng xu: 1, 3, 5 Tổng cần đạt: S = 11
Sau khi tính toán theo quy hoạch động, ta có: Min[11] = 3
Tập đồng xu tối ưu là: 5, 5, 1.
II. BÀI TOÁN DÃY CON KHÔNG GIẢM DÀI NHẤT
Cho dãy số A[1], A[2], ..., A[N]. Hãy tìm độ dài lớn nhất của dãy con không giảm.
- Xác định trạng thái
Gọi S[i] là độ dài của dãy con không giảm dài nhất kết thúc tại phần tử A[i].
- Khởi tạo
Với mọi i: S[i] = 1
- Công thức truy hồi
Với mỗi i từ 1 đến N:
- Với mỗi j < i: Nếu A[j] ≤ A[i] thì: S[i] = max(S[i], S[j] + 1)
- Ví dụ minh họa
Dãy số: 5, 3, 4, 8, 6, 7
Bảng kết quả:
i A[i] S[i] 1 5 1 2 3 1 3 4 2 4 8 3 5 6 3 6 7 4
Kết luận: Độ dài dãy con không giảm dài nhất là 4. Cảm ơn các bạn đã đọc :>
thuật toán fibonacci lifting
đã đăng vào 8, Tháng 12, 2025, 2:04ý tưởng giống binary lifting nhưng thay vì nhảy 2^k bước , ta nhảy số fibonacci thứ k bước (k<=100 hoặc bé hơn )
Debug bằng cách cout cho những người lười như tôi :v
đã đăng vào 6, Tháng 12, 2025, 1:45code:
#define cel cout<<'\n'
#define dbg(...) [](auto&&...x) {int i=0; ((ct<<(i++?" " : "")<<x),...),cel;} (__VA_ARGS__)
khi gọi dbg() và thêm các tham số vào dấu ngoặc đồng thời ngăn cách bởi dấu ',' thì hàm sẽ in hết các giá trị ra màn hình cách nhau bởi dấu cách sau đó xuống dòng
Rating Vnoi
đã đăng vào 2, Tháng 12, 2025, 6:22Làm những gì để tăng rating v mn ??
thuật toán mới
đã đăng vào 1, Tháng 12, 2025, 12:22hôm nay học quy hoạch động chia để trị
Dự án sinh test các kì thi chính thức: Kỳ thi chọn đội tuyển HSGQG THPT tỉnh Quảng Trị (2024-25)
dvtd đã đăng vào 20, Tháng 11, 2025, 12:07
💥 VNOI tiếp tục hành trình tổng hợp các đề thi HSG THPT của 34 tỉnh, thành trên toàn quốc!
🧩 Và điểm dừng chân tiếp theo chính là đề thi chọn đội tuyển HSG Quốc Gia THPT tỉnh Quảng Trị năm học 2024-2025!
💻 Số lượng bài toán: 06 bài.
📌 Ngày thi thực tế: 21–22/09/2024.
📎 Link contest: Kỳ thi chọn Đội tuyển HSGQG Quảng Trị năm 2024-2025
💖 Mời các bạn cùng thử sức với bộ đề hấp dẫn này!
🔥 Chúc các bạn có những trải nghiệm thật bổ ích và thú vị với đề thi này!
Educational Prefix Sum & Differential Array Contest
dvtd đã đăng vào 19, Tháng 11, 2025, 14:23
✨ Educational Contest là chuỗi dự án được xây dựng bởi đội ngũ Tình nguyện viên Team Contest của VNOI, hướng đến việc tạo ra những bộ bài tập luyện tập chất lượng, giúp học sinh – sinh viên rèn luyện kỹ năng lập trình và tư duy thuật toán một cách hiệu quả.
📈 Tiếp nối các chủ đề thuật toán nền tảng, lần này VNOI mang đến Educational Prefix Sum & Differential Array Contest - hai kỹ thuật quan trọng giúp tối ưu hoá xử lý truy vấn mảng và được sử dụng rộng rãi trong lập trình thi đấu.
➕ Prefix Sum (Mảng cộng dồn) là công cụ mạnh mẽ cho phép trả lời nhanh các truy vấn tổng đoạn, giúp giảm độ phức tạp từ O(n) xuống O(1). Đây là một trong những kỹ thuật cơ bản nhưng cực kỳ hiệu quả, là nền tảng để giải các bài toán khác về quy hoạch động hoặc lý thuyết đồ thị, xuất hiện liên tục trong các kỳ thi trong nước và quốc tế.
🔧 Differential Array (Mảng hiệu) lại đặc biệt hữu dụng trong việc xử lý nhiều phép cập nhật trên đoạn. Bằng việc thao tác trên mảng hiệu rồi khôi phục lại mảng gốc bằng prefix sum, kỹ thuật này giúp đơn giản hóa các phép cập nhật hàng loạt, tối ưu các truy vấn.
📌 Bộ đề Prefix Sum & Differential Array bao gồm 25 bài toán giải thuật, bao trùm từ cơ bản đến nâng cao. Contest được thiết kế theo dạng marathon, cho phép các bạn luyện tập bất cứ lúc nào. Đây sẽ là cơ hội để các bạn củng cố nền tảng tư duy thuật toán, làm quen với các mô hình bài toán điển hình và áp dụng hiệu quả hai kỹ thuật quan trọng này trong thực chiến.
📅 Contest sẽ được công khai trên nền tảng VNOJ vào Chủ Nhật, ngày 23/11/2025.
🔗 Thông tin chi tiết về Educational content có thể được tìm thấy thông qua đường link phía dưới 👉
- Educational Prefix Sum & Differential Array Contest - Part 1
- Educational Prefix Sum & Differential Array Contest - Part 2
💛 Xin gửi lời cảm ơn đến đội ngũ Tình nguyện viên VNOI đã dành nhiều tâm huyết để chuẩn bị nội dung cho chủ đề lần này. Chúc các bạn luyện tập hiệu quả và tiếp tục đồng hành cùng VNOI trong những hành trình tiếp theo!
