题意：求一个n*m的矩阵里面的最大的一个对称等腰直角三角形，三角形的腰必须平行于矩阵的边，n，m<=500。
解题思路：腰平行于矩阵的边，其实也就是做四个方向，这里我的处理方法是只做一个方向的solution，然后把矩阵旋转三次，分别求solution。做法是这样的，先预处理出一个数组，这里我将其记为fuck[i][j]，表示以(i,j)为顶点的，使得横向和纵向两条边相同的最长长度。这里就用到二分+hash了。每一行，每一列分别hash。处理完了之后，从上往下dp下来，dp[i][j]表示以(i.j)为顶点的对称等腰直角三角形的腰最长为多少。那么dp[i][j] = min ( fuck[i][j] , dp[i-1][j-1] + 2 )。这样弄完之后，后面的就很好做了。
ps：这里我处理的三角形是这种形状的：
*
**
***
代码：
#include
#include
#include
#include
#define ull unsigned long long
using namespace std ;
const int x = 123 ;
const int maxn = 555 ;
char s[maxn][maxn] , s1[maxn][maxn] ;
int dp[maxn][maxn] , fuck[maxn][maxn] ;
ull H[maxn][maxn][2] , f[maxn] ;
ull get ( int i , int l , int r , int c ) {
return H[i][r][c] - H[i][l][c] * f[r-l] ;
}
int judge ( int x , int y , int k ) {
ull a = get ( x , y - k , y , 0 ) ;
ull b = get ( y , x - k , x , 1 ) ;
return a == b ;
}
int solve ( int n , int m ) {
int i , j , k ;
for ( i = 1 ; i <= n ; i ++ )
for ( j = 1 ; j <= m ; j ++ ){
H[i][j][0] = H[i][j-1][0] * x + s[i][j] ;
dp[i][j] = 0 ;
}
for ( j = 1 ; j <= m ; j ++ )
for ( i = 1 ; i <= n ; i ++ )
H[j][i][1] = H[j][i-1][1] * x + s[i][j] ;
for ( i = 1 ; i <= n ; i ++ )
for ( j = 1 ; j <= m ; j ++ ) {
int l = 0 , r = min ( i , j ) ;
while ( l <= r ) {
k = l + r >> 1 ;
if ( judge ( i , j , k ) ) l = k + 1 ;
else r = k - 1 ;
}
fuck[i][j] = l - 1 ;
}
int ans = 0 ;
for ( i = 1 ; i <= n ; i ++ )
for ( j = 1 ; j <= m ; j ++ ) {
dp[i][j] = min ( fuck[i][j] , dp[i-1][j-1] + 2 ) ;
ans = max ( ans , dp[i][j] ) ;
}
return (1+ans)*ans/2 ;
}
void shuf ( int &n , int &m ) {
int i , j , k ;
for ( i = 1 ; i <= n ; i ++ )
for ( j = 1 ; j <= m ; j ++ )
s1[i][j] = s[i][j] ;
for ( i = 1 ; i <= m ; i ++ )
for ( j = 1 ; j <= n ; j ++ )
s[i][j] = s1[j][m-i+1] ;
swap ( n , m ) ;
}
int main () {
int t , n , m , i , j , k ;
f[0] = 1 ;
for ( i = 1 ; i < maxn ; i ++ ) f[i] = f[i-1] * x ;
scanf ( "%d" , &t ) ;
while ( t -- ) {
scanf ( "%d%d" , &n , &m ) ;
for ( i = 1 ; i <= n ; i ++ )
scanf ( "%s" , s[i] + 1 ) ;
int ans = 0 ;
for ( i = 1 ; i <= 4 ; i ++ ) {
ans = max ( solve ( n , m ) , ans );
shuf ( n , m ) ;
}
printf ( "%d\n" , ans ) ;
}
return 0 ;
}