Bài F1+F2 - Codeforces Round #547 -(Div.3)

Bài F1+F2:
Đề bài: Vấn đề này được cho gồm hai phiên bản, và chúng chỉ khác nhau về ràng buộc của n.
Bạn được cho một mảng các số nguyên a(1),a(2),...,a(n). Một block là một dãy các phần tử liên tiếp a(l),a(l+1),...,a(r)(1<=l<=r<=n). Vì vậy, một block được định nghĩa bởi một cặp chỉ số (l,r).
 Tìm một tập các block (l(1),r(1)),(l(2),r(2)),...,(l(k),r(k)) thỏa mãn:
+ Chúng không được giao nhau (nghĩa là chúng rời nhau). Chính thức là, với mỗi cặp block (l(i),r(i)) với i#j thì hoặc r(i)<l(j) hoặc r(j)<l(i).
+ Với mỗi block, tổng các phần tử của chúng phải bằng nhau. Chính thức là, a(l(1))+a(l(1)+1)+...+a(r(1))=a(l(2))+a(l(2)+1)+...+a(r(2))=...=a(l(k))+a(l(k)+1)+...+a(r(k)).
+ Số block trong một tập là lớn nhất. Chính thức là, không tồn tại một tập các block (l(1)',r(1)'),(l(2)',r(2)'),...,(l(k)',r(k)') thỏa mãn cả hai yêu cầu trên với k'>k.
Viết chương trình tìm tập như vậy.
Đầu vào:
+ Dòng đầu tiên chứa số nguyên n (1<=n<=50)- Độ dài của mảng được cho.
+ Dòng thứ hai chứa một dãy các số nguyên a(1),a(2),...,a(n)(-10^5<=a(i)<=10^5).
Đầu ra:
+ Dòng đầu tiên in số nguyên k(1<=k<=n).
+ k dòng tiếp theo chứa các block, mỗi cái một dòng. Với mỗi dòng in một cặp chỉ số l(i),r(i)(1<=l(i)<=r(i)<=n)- là giới hạn của block thứ i.
+ Bạn có thể in block theo bất kỳ thứ tự nào. Nếu có nhiều đáp án, in ra bất kì.
Ví dụ:
Đầu vào:
7
4 1 2 2 1 5 3
Đầu ra:
3
7 7
2 3
4 5
Hướng dẫn: Gọi x là tổng giống nhau của các block trong câu trả lời. Quan sát thấy rằng, x có thể biểu diễn dưới dạng tổng của các phần tử kề nhau trong a, có nghĩa là x=a(l)+a(l+1)+...+a(r) với l và r nào đó.
Duyệt qua tất cả các trường hợp có thể của block với độ phức tạp O(n^2) và lưu lại tất cả các block. Bạn có thể sử dụng công cụ 'map<int, vector<pair<int,int>>>' để lưu block được tạo bởi cùng một tổng. Bạn có thể làm nó theo đoạn code sau:
 
map<int,vector<pair<int,int>>> segs;
for (int r = 0 ; r < n ; r++){
    int sum = 0;
   for ( int l = r ; l >= 0; l-- ){
      sum+=a[l];
     segs[sum].push_back({l,r});
}
}

Chú ý rằng, các block này được sắp xếp theo đầu bên phải trong mỗi nhóm.
Sau đó, bạn có thể độc lập thử mỗi nhóm (có O(n^2) chúng) và tìm kiếm tập rời rạc gồm các block cùng một nhóm có số lương lớn nhất. Bạn có thể làm việc này bằng phương pháp tham lam, mỗi lần đưa vào phân đoạn (segment) trả lời với đầu bên phải nhỏ nhất. Bởi vì mỗi nhóm chúng đều được sắp theo thứ tự đầu bên phải nên bạn có thể tìm thấy khối tách rời tối đa cần thiết với một lần duyệt. Chúng ta giả sử pp là nhóm gồm các block hiện tại (chúng được sắp xếp theo the right end), thì đoạn code dưới đây xây dựng tập rời rạc lớn nhất:

int cur = 0;
int r = -1;
vector<pair<int,int>> now;
for(auto seg : pp)
   if ( seg.first > r){
     cur++;
     now.push_back(seg);
    r=seg.second;
}
Chọn giá trị lớn nhất trong số các tập phân biệt lớn nhất cho nhóm.
Lời giải:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
    cin >> a[i];
map<int, vector<pair<int,int>>> segs;
for (int r = 0; r < n; r++) {
    int sum = 0;                              
    for (int l = r; l >= 0; l--) {
        sum += a[l];
        segs[sum].push_back({l, r});
    }
}
int result = 0;
vector<pair<int,int>> best;
for (const auto& p: segs) {
    const vector<pair<int,int>>& pp = p.second;
    int cur = 0;
    int r = -1;
    vector<pair<int,int>> now;
    for (auto seg: pp)
        if (seg.first > r) {
            cur++;
            now.push_back(seg);
            r = seg.second;
        }
    if (cur > result) {
        result = cur;
        best = now;
    }
}
cout << result << endl;
for (auto seg: best)
    cout << seg.first + 1 << " " << seg.second + 1 << endl;
    return 0;
}