Tin học THCS

em bây giờ đang học lớp 9 rồi, xác định thi chuyên tin mà em yếu tìm kiếm nhị phân quá ạ, ai có link bài tập tìm kiếm nhị phân cơ bản thì gửi em được không ạ

Giả sử đề bài bảo cho 1 số n và nhập dữ liệu mảng từ a[1] đến a[n] rồi đếm số lượng số hạng chẵn/lẻ.
Mẹo tối ưu: Ta ko cần tạo mảng ta chỉ cần khai báo thêm biến bất kỳ rồi kiểm tra luôn tính chẵn/lẻ. Ngoài ra ko chỉ bài này mà còn có những bài khác cũng làm vậy.
Cách dùng mẹo và lý do ac: Nếu khi phân tích bài, ta thấy rằng khi nhập vào 1 biến thì có thể xử lý luôn mà khi nhập vào dữ liệu tiếp theo thì coi như dữ liệu đã xử lý xong rồi thì có thể dùng mẹo này. Lý do ac là bởi vì mảng dùng để ghi nhớ quá khứ mà nếu hiện tại có thể xử lý xong thì ko cần nhớ quá khứ nữa.
Tên gọi của mẹo này: Stream Processing - Xử lý luồng
Mô tả chi tiết:
_Bản chất dòng chảy dữ liệu: Dữ liệu được đưa vào hệ thống dưới dạng một dòng chảy liên tục (stream). Mỗi khi một phần tử dữ liệu xuất hiện, nó được tiếp nhận và xử lý ngay lập tức.
_Sự giải phóng bộ nhớ: Khi dữ liệu mới bước vào và xử lý xong, hệ thống lập tức hoàn thành nhiệm vụ với phần tử đó và chuyển sang phần tử tiếp theo mà không cần lưu trữ hay quay đầu nhìn lại lịch sử cũ, giúp tối ưu hóa không gian bộ nhớ đạt mức O(1).

cho vào nhóm để học hỏi pls

Bài gợi ý: Đường đi có tổng lớn nhất
Tóm tắt: Bạn xuất phát từ ô \((1, 1)\) trên bảng kích thước \(n \times m\), chỉ được đi sang phải hoặc đi xuống dưới để tới ô \((n, m)\). Hãy tìm một đường đi sao cho tổng các số trên các ô đi qua đạt giá trị lớn nhất.

Xét bảng \(4 \times 4\) trong đề bài. Nếu đi theo lộ trình \((1,1) \to (1,2) \to (2,2) \to (3,2) \to (3,3) \to (3,4) \to (4,4)\), ta lần lượt đi qua các ô chứa số \(4, 3, 2, 5, 6, 7, 2\) [0]. Tổng điểm thu được là \(4 + 3 + 2 + 5 + 6 + 7 + 2 = 29\) [0].

Bảng có kích thước lên tới \(1000 \times 1000\) [0]. Nếu thử duyệt từng nhánh đường đi, số lượng cách đi sẽ cực kỳ lớn và chương trình chạy không kịp. Nhưng để bước vào ô \((i, j)\), ta chỉ có đúng hai cách: đi từ ô phía trên \((i - 1, j)\) xuống, hoặc đi từ ô bên trái \((i, j - 1)\) sang.

Vì vậy, ta không cần tìm lại toàn bộ hành trình từ đầu. Ta chỉ cần lưu lại tổng điểm lớn nhất để đến được từng ô. Kỹ thuật nhớ kết quả của các bước trước để tính bước sau gọi là quy hoạch động (DP). Gọi \(dp[i][j]\) là tổng lớn nhất khi đi từ \((1, 1)\) tới \((i, j)\), công thức tính là \(dp[i][j] = a[i][j] + \max(dp[i - 1][j], dp[i][j - 1])\).

Do mỗi ô \(a_{i, j} \le 10^{10}\), tổng đường đi sẽ vượt quá giới hạn của số nguyên thông thường, nên bạn hãy dùng kiểu long long [0]. Bạn chỉ cần khởi tạo \(dp[1][1] = a[1][1]\), chạy hai vòng lặp for (int i = 1; i <= n; ++i) và for (int j = 1; j <= m; ++j) để điền bảng, rồi in ra kết quả tại dp[n][m].