Olympic Sinh Viên 2025 - Chuyên tin - DÃY NGẮN NHẤT

Xem dạng PDF
Gửi bài giải
Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 0
    pt48583994  đã bình luận lúc 8, Tháng 4, 2026, 22:51

    Hướng giải:

    Duyệt các số fibonacci từ cao đến thấp, sau đó đệ quy chia 2 trường hợp. Nhận xét trong 1 dãy mà các số cùng bit cao nhất thì số cuối (số nhỏ nhất) thì có thể nhận xét trực tiếp mà không cần chia 2 trường hợp. Sau đó tham lam khi đã xét 1 tập có tổng XOR bằng n (chia ~(m-s)/2~ thành các số fibo). Đpt ~O(m^{\frac{\log(2)}{\log(\phi)}-1} \log(m))~.