A. Định dạng văn bản Orange

Để xử lý đầu vào đa dòng, chúng ta dùng vòng lặp while kết hợp hàm getline. Biến đếm dòng và tìm độ dài tối đa của các dòng:

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    string line;
    int soDong = 0, maxDai = 0;
    while (getline(cin, line)) {
        soDong++;
        maxDai = max(maxDai, (int)line.size());
    }
    cout << soDong << " " << maxDai << endl;
    return 0;
}

B. Tìm chuỗi số tăng liên tiếp dài nhất

Sử dụng thuật toán hai con trỏ để quét mảng:

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n, arr[50001];
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];

    int maxLength = 0;
    for (int start = 1, end = 1; start <= n; start = end) {
        end = start + 1;
        while (end <= n && arr[end] - arr[end-1] == 1) end++;
        maxLength = max(maxLength, end - start);
    }
    cout << maxLength << endl;
    return 0;
}

C. Tổng đoạn mảng một chiều

Sử dụng mảng tiền tố (prefix sum) để xử lý truy vấn hiệu quả:

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    long long n, m, arr[200010] = {0}, prefix[200010] = {0};
    cin >> n >> m;
    
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        prefix[i] = prefix[i-1] + arr[i];
    }
    
    while (m--) {
        int l, r;
        cin >> l >> r;
        cout << prefix[r] - prefix[l-1] << endl;
    }
    return 0;
}

D. Tổng đoạn mảng hai chiều

Mở rộng tiền tố sang ma trận hai chiều:

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m, T;
    long long a[1005][1005] = {0}, prefix[1005][1005] = {0};
    
    cin >> n >> m >> T;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            prefix[i][j] = a[i][j] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1];
        }
    }
    
    while (T--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1] << endl;
    }
    return 0;
}

E. Biến đổi mảng một chiều

Áp dụng kỹ thuật mảng hiệu số (difference array):

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    long long n, m, arr[200010] = {0}, diff[200010] = {0};
    cin >> n >> m;
    
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        diff[i] += arr[i];
        diff[i+1] -= arr[i];
    }
    
    while (m--) {
        int l, r, x;
        cin >> l >> r >> x;
        diff[l] += x;
        diff[r+1] -= x;
    }
    
    for (int i = 1; i <= n; i++) {
        diff[i] += diff[i-1];
        cout << diff[i] << " ";
    }
    return 0;
}

F. Biến đổi mảng hai chiều

Mở rộng hiệu số sang ma trận hai chiều:

#include <iostream>
using namespace std;

int main() {
    int n, m, t;
    long long diff[1005][1005] = {0};
    
    auto update = [&](int x1, int y1, int x2, int y2, long long val) {
        diff[x1][y1] += val;
        diff[x1][y2+1] -= val;
        diff[x2+1][y1] -= val;
        diff[x2+1][y2+1] += val;
    };
    
    cin >> n >> m >> t;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            long long x;
            cin >> x;
            update(i, j, i, j, x);
        }
    }
    
    while (t--) {
        int x1, y1, x2, y2;
        long long val;
        cin >> x1 >> y1 >> x2 >> y2 >> val;
        update(x1, y1, x2, y2, val);
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1];
            cout << diff[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

G. Tối ưu hóa trò chơi Orange

Sử dụng tiền tố tổng và tiền tố max để tối ưu chiến lược:

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    
    long long firstPass[200010] = {0}, sweepMax[200010] = {0};
    
    for (int i = 1; i <= n; i++) {
        cin >> firstPass[i];
        firstPass[i] += firstPass[i-1];
    }
    
    for (int i = 1; i <= n; i++) {
        cin >> sweepMax[i];
        sweepMax[i] = max(sweepMax[i], sweepMax[i-1]);
    }
    
    long long maxScore = 0;
    for (int i = 1; i <= min(n, q); i++) {
        maxScore = max(maxScore, firstPass[i] + (long long)(q - i) * sweepMax[i]);
    }
    
    cout << maxScore << endl;
    return 0;
}