Chào buổi sáng! (00:50:13)

Đây là lần thi khá thuận lợi: giải được tổng cộng 6 bài toán.

A. Tạo Dữ Liệu Thử

Sử dụng cấu trúc ánh xạ để đếm tần suất ký tự.

#include<bits/stdc++.h>
using namespace std;
const int MAX_SIZE = 2e5+10;
int test_cases, n, m;
char input_array[MAX_SIZE];
unordered_map<char, int> frequency;
int main() {
    cin >> test_cases;
    while(test_cases--) {
        frequency.clear();
        cin >> n >> m;
        cin >> (input_array + 1);
        for(int i = 1; i <= n; i++) {
            frequency[input_array[i]]++;
        }
        int result = 0;
        for(char c = 'A'; c <= 'G'; c++) {
            result += max(0, m - frequency[c]);
        }
        cout << result << endl;
    }
    return 0;
}

B. Chọn Khối Lập Phương

Bài toán này có hai điểm cần lưu ý khi đọc đề:

1. Yêu cầu chọn k phần tử đầu tiên, không phải phần tử thứ k;
2. Cần kiểm tra các giá trị trùng với a[m] ở vị trí khác.

#include<bits/stdc++.h>
using namespace std;
const int MAX_SIZE = 2e5+10;
int test_cases, n, m, k, cube_values[MAX_SIZE];
unordered_map<int, int> count_map;
int main() {
    cin >> test_cases;
    while(test_cases--) {
        count_map.clear();
        cin >> n >> m >> k;
        for(int i = 1; i <= n; i++) {
            cin >> cube_values[i];
            count_map[cube_values[i]]++;
        }
        int target = cube_values[m];
        sort(cube_values + 1, cube_values + n + 1, greater<int>());
        if(cube_values[k] > target) cout << "no" << endl;
        else {
            if(cube_values[k] == target && cube_values[k] == cube_values[k+1]) cout << "maybe" << endl;
            else cout << "yes" << endl;
        }
    }
    return 0;
}

C. Kiểm Tra Phép Toán Mất

Xác minh tính hợp lệ của phần tử cuối cùng và sự khớp giữa các phần tử.

#include<bits/stdc++.h>
using namespace std;
const int MAX_SIZE = 2e5+10;
int test_cases, n, array1[MAX_SIZE], array2[MAX_SIZE], array3[MAX_SIZE], m;
unordered_map<int, int> count1, count2;
int main() {
    cin >> test_cases;
    while(test_cases--) {
        count1.clear(); count2.clear();
        cin >> n;
        for(int i = 1; i <= n; i++) cin >> array1[i];
        for(int i = 1; i <= n; i++) {
            cin >> array2[i];
            count1[array2[i]]++;
        }
        cin >> m;
        for(int i = 1; i <= m; i++) {
            cin >> array3[i];
            count2[array3[i]]++;
        }
        if(count1.find(array3[m]) == count1.end()) cout << "no" << endl;
        else {
            bool valid = true;
            for(int i = 1; i <= n; i++) {
                if(array1[i] != array2[i]) {
                    if(count2[array2[i]] <= 0) {
                        valid = false;
                        break;
                    }
                    count2[array2[i]]--;
                }
            }
            cout << (valid ? "yes" : "no") << endl;
        }
    }
    return 0;
}

D. Dãy GCD Liên Tục

Kiểm tra điều kiện liên tiếp của các cặp phần tử và tìm vị trí phù hợp.

#include<bits/stdc++.h>
using namespace std;
const int MAX_SIZE = 2e5+10;
int test_cases, n, numbers[MAX_SIZE], gcd_values[MAX_SIZE];
bool prefix_valid[MAX_SIZE], suffix_valid[MAX_SIZE];
int main() {
    cin >> test_cases;
    while(test_cases--) {
        memset(prefix_valid, true, sizeof(prefix_valid));
        memset(suffix_valid, true, sizeof(suffix_valid));
        cin >> n;
        for(int i = 1; i <= n; i++) cin >> numbers[i];
        for(int i = 2; i <= n; i++) {
            gcd_values[i] = __gcd(numbers[i], numbers[i-1]);
        }
        for(int i = 3; i <= n; i++) {
            prefix_valid[i] = prefix_valid[i-1] && (gcd_values[i] >= gcd_values[i-1]);
        }
        for(int i = n-2; i >= 1; i--) {
            suffix_valid[i] = suffix_valid[i+1] && (gcd_values[i+1] <= gcd_values[i+2]);
        }
        bool possible = false;
        for(int i = 2; i < n; i++) {
            int current_gcd = __gcd(numbers[i-1], numbers[i+1]);
            if(prefix_valid[i-1] && suffix_valid[i+1] && current_gcd >= gcd_values[i-1] && current_gcd <= gcd_values[i+2]) {
                possible = true;
                break;
            }
        }
        cout << (possible || prefix_valid[n-1] || suffix_valid[2] ? "Yes" : "No") << endl;
    }
    return 0;
}