Hướng dẫn giải của Tệp nhật ký


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Hướng dẫn giải

Các sự kiện là các số nguyên nằm trong xâu; chữ cái và dấu cách chỉ là ký tự chèn vào. Cần đếm số cặp (i < j) có tổng bằng ~S~. Ký tự '-' ngay trước chữ số là dấu âm.

Sub 1: vét cạn mọi cặp — ~O(N^2)~, dùng khi ~N \le 5000~

Thử mọi cặp ~(i, j)~ với ~i < j~. Nếu chỉ nộp sub này: đúng 25/40 test.

Sub 2: sắp xếp và hai con trỏ — ~O(N \log N)~

Sắp xếp các giá trị, gom thành nhóm (giá trị, số lần). Dùng hai con trỏ trên các nhóm: cặp hai giá trị khác nhau đếm bằng tích số lần; cặp cùng giá trị ~v~ với ~2v = S~ đếm bằng ~c(c-1)/2~. Đúng 40/40 test.

Chương trình hoàn chỉnh

main tách các số trong xâu, đọc ~N~ và ~S~. Nếu ~N \le 5000~ thì gọi sub1, ngược lại gọi sub2.

#include <bits/stdc++.h>
using namespace std;

vector<long long> a;   // các sự kiện (số nguyên) đã tách khỏi xâu
long long S;           // mã lỗi: đếm cặp (i<j) có a[i]+a[j] = S

// Sub 1: vét cạn mọi cặp (i,j), O(N^2). Dùng khi N <= 5000.
void sub1() {
    long long cnt = 0;
    int N = a.size();
    for (int i = 0; i < N; i++)
        for (int j = i + 1; j < N; j++)
            if (a[i] + a[j] == S) cnt++;
    cout << cnt << "\n";
}

// Sub 2: sắp xếp, gom các giá trị giống nhau thành nhóm (giá trị, số lần),
// rồi dùng hai con trỏ trên các nhóm. Cặp hai nhóm khác giá trị đếm bằng tích số lần;
// cặp trong cùng một nhóm (2v = S) đếm bằng c(c-1)/2. O(N log N).
void sub2() {
    vector<long long> v = a;
    sort(v.begin(), v.end());
    vector<long long> gv, gc;
    for (size_t i = 0; i < v.size();) {
        size_t j = i;
        while (j < v.size() && v[j] == v[i]) j++;
        gv.push_back(v[i]);
        gc.push_back(j - i);
        i = j;
    }
    long long ans = 0;
    int lo = 0, hi = (int)gv.size() - 1;
    while (lo < hi) {
        long long sum = gv[lo] + gv[hi];
        if (sum == S) { ans += gc[lo] * gc[hi]; lo++; hi--; }
        else if (sum < S) lo++;
        else hi--;
    }
    for (size_t i = 0; i < gv.size(); i++)
        if (2 * gv[i] == S) ans += gc[i] * (gc[i] - 1) / 2;
    cout << ans << "\n";
}

int main() {
    freopen("NHATKY.INP", "r", stdin);
    freopen("NHATKY.OUT", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long N;
    cin >> N;
    cin.ignore(1000000, '\n');
    string s;
    getline(cin, s);
    cin >> S;
    // Tách các số nguyên trong xâu: bỏ chữ cái và dấu cách,
    // dấu '-' ngay trước chữ số là dấu âm.
    for (size_t i = 0; i < s.size();) {
        if (isdigit((unsigned char)s[i])) {
            size_t j = i;
            while (j < s.size() && isdigit((unsigned char)s[j])) j++;
            long long v = stoll(s.substr(i, j - i));
            if (i > 0 && s[i - 1] == '-') v = -v;
            a.push_back(v);
            i = j;
        } else {
            i++;
        }
    }
    if (N <= 5000) sub1();
    else sub2();
    return 0;
}

Bình luận

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


Không có bình luận tại thời điểm này.