Tiêu đề Sol đề HSG THCS Hà Nội 2024-2025.pdf ✅

SỞ GIÁO DỤC VÀ ĐÀO TẠO HÀ NỘI ________________ HƯỚNG DẪN GIẢI ĐỀ CHÍNH THỨC KỲ THI CHỌN HỌC SINH GIỎI THÀNH PHỐ LỚP 9 CẤP THCS NĂM HỌC 2024-2025 Môn: TIN HỌC Ngày thi: 17/01/2025 Thời gian làm bài: 150 phút, không kể thời gian giao đề Bài 1. (5,0 điểm) CẮT HÌNH - Số hàng p còn dư của M sau khi cắt: p = M % k, diện tích phần này sẽ là p * N; - Số cột q còn dư của N sau khi cắt: q = N % k, diện tích phần này là q * M; - Hai phần còn dư sẽ có 1 phần diện tích chồng lên nhau là p * q; - Diện tích còn lại là: p * N + q * M – p * q Độ phức tạp: O(1) Code tham khảo: #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); freopen("cathinh.inp", "r", stdin); freopen("cathinh.out", "w", stdout); long long m,n,k; cin>>m>>n>>k; long long p=m%k; long long q=n%k; cout< using namespace std; string s; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); freopen("machdna.inp", "r", stdin); freopen("machdna.out", "w", stdout); cin>>s; int num=0;
for (int i=0; i='0' && s[i]<='9') num=num*10+(s[i]-'0'); else { char c='A'; if (s[i]=='A') c='T'; else if (s[i]=='T') c='A'; else if (s[i]=='G') c='C'; else c='G'; for (int j=0; j N thì tính đến N. Sub 1: N, M, Q ≤ 103  Gọi F[i] là số lần tác động lên bóng đèn ở vị trí i. Ban đầu tất cả F[i] đều bằng 0.  Với mỗi lệnh X, duyệt từ i = max(1, X-K) đến min(n, X+K), tăng F[i] lên 1.  Duyệt lại F, nếu F[i] chẵn thì in ra V, ngược lại in D. Độ phức tạp thuật toán: O(M * Q) Code tham khảo subtask 1: int f[1003]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); freopen("DAYDEN.INP", "r", stdin); freopen("DAYDEN.OUT", "w", stdout); int n, m, q, k; cin >> n >> m >> q >> k; for (int i = 1; i <= 1000; i++) f[i]=0;
int x; for (int i=1; i<=m; i++) { cin >> x; for (int i=max(1,x-k); i<=min(n,x+k); i++) f[i]+=1; } for (int i=1; i<=q; i++) { cin>>x; if (f[x]%2==0) cout<<"V\n"; else cout<<"D\n"; } return 0; } Sub 2: N, M ≤ 105 Với số lượng N lớn, ta không cần phải duyệt qua tất cả các vị trí của mỗi lệnh X, mà chỉ cần ghi nhận lại trạng thái 2 đầu mút của X:  F[X-K] = 1, nếu X-K < 1 thì F[1] = 1, nghĩa là có thêm 1 tác động bắt đầu từ vị trí X-K;  F[X+K+1] = -1 , nếu X+K+1> N+1 thì F[N+1] = -1, nghĩa là khi kết thúc tác động ở vị trí X+K thì từ vị trí X+K+1 sẽ giảm đi một tác động. Chẳng hạn với test ví dụ sau: 10 4 3 2 5 6 7 9 3 7 8 Ta ghi nhận lại mảng F như sau: Vị trí 1 2 3 4 5 6 7 8 9 10 11 F[i] 0 0 1 1 1 0 1 -1 -1 -1 -1 Lúc này ta sẽ thấy rằng, ở vị trí số 4 sẽ chịu 1 tác động bởi lệnh 5 và 1 tác động bởi lệnh 6. Tính lại mảng F theo phương thức cộng dồn, khi đó F[i] chính là số lượng tác động lên điểm i. Vị trí 1 2 3 4 5 6 7 8 9 10 11 F[i] 0 0 1 2 3 3 4 3 2 1 0
Xét theo nguyên tắc chẵn, lẻ như đã quy ước đầu bài, ta có kết quả là: input output 10 4 3 2 5 6 7 9 3 7 8 D V D Code tham khảo subtask 2: #include using namespace std; int f[100005]; int n, m, q, k; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); freopen("DAYDEN.INP", "r", stdin); freopen("DAYDEN.OUT", "w", stdout); cin >> n >> m >> q >> k; for (int i = 1; i <= 100001; i++) f[i]=0; int x; for (int i=1; i<=m; i++) { cin>>x; f[max(1, x-k)]+=1; f[min(n+1,x+k+1)]-=1; } for (int i=2; i<=n; i++) f[i]+=f[i-1]; for (int i=1; i<=q; i++) { cin>>x; if (f[x]%2==0) cout<<"V\n"; else cout<<"D\n"; } return 0; } Độ phức tạp thuật toán: O(M + Q) Sub 3: N ≤ 109 Giới hạn N đã vượt khỏi phạm vi sử dụng mảng đánh dấu. Dựa trên ý tưởng ở Sub 2, ta cải tiến như sau: Sử dụng một mảng F kiểu pair để ghi nhận lại giá trị và trạng thái 2 đầu mút, khi đó với mỗi lệnh X, ta đưa giá trị X-K và X+K+1 vào mảng F như sau: