题意：在一个有字母和数字组成的矩形里面找最大的等腰对称直角三角形，直角边分别平行于矩形边，对称的意思是对称轴两边的字符相同。
思路：首先考虑一种情况，三角形的直角边在右方和下方，对于其它情况可以通过旋转矩形来得到。这样令dp[i][j]表示直角点在(i,j)的最大三角形的直角边的长度，不难得到dp[i][j] = max(dp[i-1][j-1] + 2, len)。len表示从(i,j)向左和向上两个方向上的字符串"最长公共前缀"的长度。此类匹配问题用二分+hash来说简直妙不可言~
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 | #include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <queue>#include <cmath>#include <algorithm>using namespace std;const int X = 12121;typedef unsigned long long uLL;int buf[567][567], img[567][567], dp[567][567];int n, m;void change() { for (int i = 1; i <= n; i ++) { for (int j = 1; j <= m; j ++) { buf[m - j + 1][i] = img[i][j]; } } swap(n, m); for (int i = 1; i <= n; i ++) { for (int j = 1; j <= m; j ++) { img[i][j] = buf[i][j]; } }}uLL H1[567][567], H2[567][567];uLL MUL[567];void init() { memset(H1, 0, sizeof(H1)); memset(H2, 0, sizeof(H2)); for (int i = 1; i <= n; i ++) { for (int j = 1; j <= m; j ++) { H1[i][j] = H1[i][j - 1] * X + img[i][j]; H2[i][j] = H2[i - 1][j] * X + img[i][j]; } } MUL[0] = 1; for (int i = 1; i <= 500; i ++) { MUL[i] = MUL[i - 1] * X; }}bool chk(int x, int y, int len) { uLL row = H1[x][y] - H1[x][y - len] * MUL[len]; uLL col = H2[x][y] - H2[x - len][y] * MUL[len]; return row == col;}int solve() { init(); int ans = 0; for (int i = 1; i <= n; i ++) { for (int j = 1; j <= m; j ++) { int L = 1, R = min(i, j); while (L < R) { int M = (L + R + 1) >> 1; if (chk(i, j, M)) L = M; else R = M - 1; } dp[i][j] = min(dp[i - 1][j - 1] + 2, L); ans = max(ans, dp[i][j]); } } return ans;}int main() {#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin);#endif // ONLINE_JUDGE int T; cin >> T; while (T --) { cin >> n >> m; for (int i = 0; i < n; i ++) { char s[567]; scanf("%s", s); for (int j = 0; j < m; j ++) { img[i + 1][j + 1] = s[j]; } } int ans = 0; for (int i = 0; i < 4; i ++) { ans = max(ans, solve()); change(); } cout << ans * (ans + 1) / 2 << endl; } return 0;} |