[mathjax]

Đề bài

• http://vn.spoj.com/problems/MESSAGE1/

Thuật toán

Ở bài này ta dời bảng B như hình, trong mỗi lần dời ta so sách các ô trong vùng giao nhau nữa 2 bảng, ô bằng nhau có giá trị 1, khác nhau có giá trị 0.

Cụ thể hơn, giả sử ta dời bảng B theo một vector $(x, y)$, khi đó ô $A(i, j)$ sẽ được so sánh với ô $B(i-x, j-y)$. Ta tính toạ độ các ô trong phần giao giữa 2 bảng như sau, có 4 điều kiện:

$
\begin{cases}
0 <= i < m\\
0 <= j < n\\
0 <= i-x < m\\
0 <= i-y < n\\
\end{cases}
$

Từ đó suy ra:

$
\begin{cases}
max(0, x) <= i < min(m, m + x)\\
max(0, y) <= j < min(n, n + y)\\
\end{cases}
$

Sau đó ta tìm hình chữ nhật chứa toàn số 1 và có diện tích lớn nhất (như bài QBRECT).

Sau đây là cách tìm hình chữ nhật như trên trong thời gian $O(n^2)$:

Với mỗi ô $j$ trên hàng $i$, ta tìm $f(j)$ là số ô 1 liên tiếp trên cột $j$, tính từ hàng $i$ trở lên. Sau đó, với mỗi cột $j$, ta tiếp tục tìm ô gần nhất bên trái và ô gần nhất bên phải có $f$ nhỏ hơn $f(j)$, sau đó tính diện tích hình chữ nhật ở cột $j$ là $S = f(j)\times(r – l – 1)$ với $l, r$ là chỉ số 2 ô bên trái và bên phải nói trên.

Hình minh hoạ khi tính $f(4)$:

Để tìm $l, r$ nhanh, ta dùng kĩ thuật sử dụng Deque tìm Min/Max trên đoạn tịnh tiến.

Độ phức tạp của toàn bộ lời giải là $O(n^4)$.

Code

• C++

#include 
#include 
#include 
using namespace std;

void calc(int &res, int x, int y, const vector &a, const vector &b) {
    int m = a.size(), n = a[0].size();
    int low_i = max(0, x), high_i = min(m, m + x);
    int low_j = max(0, y), high_j = min(n, n + y);
    if ((high_i - low_i)*(high_j - low_j) <= res) return;
    vector f(high_j, 0);
    vector l(high_j), q(high_j), idx(high_j);
    for (int i=low_i; i < high_i; i++) {
        int top = 0;
        for (int j=low_j; j < high_j; j++) {
            if (a[i][j] == b[i-x][j-y]) {
                f[j]++;
                while (top && q[top-1]>=f[j]) top--;
                if (!top) l[j] = low_j-1;
                else l[j] = idx[top-1];
                q[top] = f[j], idx[top] = j, top++;
            } else {
                f[j] = 0;
                q[0] = 0, idx[0] = j, top = 1;
            }
        }
        top = 0;
        int r;
        for (int j=high_j-1; j >= low_j; j--) {
            if (f[j]) {
                while (top && q[top-1]>=f[j]) top--;
                if (!top) r = high_j;
                else r = idx[top-1];
                res = max(res, f[j]*(r - l[j] - 1));
                q[top] = f[j], idx[top] = j, top++;
            } else {
                q[0] = 0, idx[0] = j, top = 1;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T; cin >> T;
    while (T--) {
        int n, m; cin >> m >> n;
        vector a(m), b(m);
        for (auto &s: a) cin >> s;
        for (auto &s: b) cin >> s;
        int res = 0;
        for (int i=-m+1; i