卫星图像(Sateliti) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

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

using ull = unsigned long long;
const ull B1 = 131;
const ull B2 = 13331;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<string> g(2 * n);
    for (int i = 0; i < n; ++i) {
        string row;
        cin >> row;
        g[i] = row + row;
        g[i + n] = g[i];
    }
    int N = 2 * n, M = 2 * m;
    vector<ull> p1(M + 1, 1), p2(N + 1, 1);
    for (int j = 1; j <= M; ++j) p1[j] = p1[j - 1] * B1;
    for (int i = 1; i <= N; ++i) p2[i] = p2[i - 1] * B2;

    vector<vector<ull>> h(N + 1, vector<ull>(M + 1, 0));
    for (int i = 1; i <= N; ++i) {
        ull row_h = 0;
        for (int j = 1; j <= M; ++j) {
            row_h = row_h * B1 + (ull)g[i - 1][j - 1];
            h[i][j] = h[i - 1][j] * B2 + row_h;
        }
    }

    auto get_rect = [&](int r1, int c1, int r2, int c2) -> ull {
        // 0-indexed [r1..r2-1][c1..c2-1]
        ull res = h[r2][c2] - h[r1][c2] * p2[r2 - r1] - h[r2][c1] * p1[c2 - c1] + h[r1][c1] * p2[r2 - r1] * p1[c2 - c1];
        return res;
    };

    auto less_shift = [&](int rA, int cA, int rB, int cB) -> bool {
        if (get_rect(rA, cA, rA + n, cA + m) == get_rect(rB, cB, rB + n, cB + m)) return false;
        int lo = 1, hi = n, diff_r = n;
        while (lo <= hi) {
            int mid = (lo + hi) >> 1;
            if (get_rect(rA, cA, rA + mid, cA + m) == get_rect(rB, cB, rB + mid, cB + m)) {
                lo = mid + 1;
            } else {
                diff_r = mid - 1;
                hi = mid - 1;
            }
        }
        lo = 1;
        hi = m;
        int diff_c = m;
        while (lo <= hi) {
            int mid = (lo + hi) >> 1;
            if (get_rect(rA + diff_r, cA, rA + diff_r + 1, cA + mid) == get_rect(rB + diff_r, cB, rB + diff_r + 1, cB + mid)) {
                lo = mid + 1;
            } else {
                diff_c = mid - 1;
                hi = mid - 1;
            }
        }
        return g[rA + diff_r][cA + diff_c] < g[rB + diff_r][cB + diff_c];
    };

    int best_r = 0, best_c = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (i == 0 && j == 0) continue;
            if (less_shift(i, j, best_r, best_c)) {
                best_r = i;
                best_c = j;
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        cout << g[best_r + i].substr(best_c, m) << "\n";
    }
    return 0;
}