[luoguP2601] [ZJOI2009]对称的正方形(二维Hash + 二分 || Manacher)

传送门

很蒙蔽,不知道怎么搞。

网上看题解有说可以哈希+二分搞,也有的人说用Manacher搞,Manacher是什么鬼?以后再学。

对于这个题,可以从矩阵4个角hash一遍,然后枚举矩阵中的点,再二分半径。

但是得考虑边的长度为奇偶所带来的影响。

比如

1 1

1 1

这个边数为偶数的矩阵显然没法搞。

所以得在矩阵中插入0,

变成

0 0 0 0 0

0 1 0 1 0

0 0 0 0 0

0 1 0 1 0

0 0 0 0 0

具体操作就看代码好了。

然后只枚举 行 + 列 为偶数的点就行。

注意 用 unsigned long long 会超时和超空间,数据允许用 unsigned int

——代码

 #include <cstdio>
#include <iostream>
#define UI unsigned int const int MAXN = , bs1 = , bs2 = ;
int n, m, ans;
UI sum[][MAXN][MAXN], base1[MAXN], base2[MAXN]; inline int read()
{
int x = , f = ;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -;
for(; isdigit(ch); ch = getchar()) x = (x << ) + (x << ) + ch - '';
return x * f;
} inline int min(int x, int y)
{
return x < y ? x : y;
} inline bool pd(int x, int y, int l)
{
UI t, h;
h = sum[][x + l - ][y + l - ]
- sum[][x - l][y + l - ] * base1[l + l - ]
- sum[][x + l - ][y - l] * base2[l + l - ]
+ sum[][x - l][y - l] * base1[l + l - ] * base2[l + l - ];
t = sum[][x + l - ][y - l + ]
- sum[][x - l][y - l + ] * base1[l + l - ]
- sum[][x + l - ][y + l] * base2[l + l - ]
+ sum[][x - l][y + l] * base1[l + l - ] * base2[l + l - ];
if(h ^ t) return ;
t = sum[][x - l + ][y + l - ]
- sum[][x + l][y + l - ] * base1[l + l - ]
- sum[][x - l + ][y - l] * base2[l + l - ]
+ sum[][x + l][y - l] * base1[l + l - ] * base2[l + l - ];
if(h ^ t) return ;
t = sum[][x - l + ][y - l + ]
- sum[][x + l][y - l + ] * base1[l + l - ]
- sum[][x - l + ][y + l] * base2[l + l - ]
+ sum[][x + l][y + l] * base1[l + l - ] * base2[l + l - ];
if(h ^ t) return ;
return ;
} inline int work(int i, int j)
{
int mid, s = , x = , y = min(min(i, n - i + ), min(j, m - j + ));//二分半径
while(x <= y)
{
mid = (x + y) >> ;
if(pd(i, j, mid)) s = mid, x = mid + ;
else y = mid - ;
}
return s;
} int main()
{
int i, j, k, x;
n = read();
m = read();
n = n << | ;
m = m << | ;
for(i = ; i <= n; i += )
for(j = ; j <= m; j += )
{
x = read();
for(k = ; k < ; k++) sum[k][i][j] = x;
}
base1[] = base2[] = ;
for(i = ; i <= n; i++) base1[i] = base1[i - ] * bs1;
for(i = ; i <= m; i++) base2[i] = base2[i - ] * bs2;
for(i = ; i <= n; i++)
for(j = ; j <= m; j++)
sum[][i][j] += sum[][i - ][j] * bs1;
for(i = ; i <= n; i++)
for(j = ; j <= m; j++)
sum[][i][j] += sum[][i][j - ] * bs2;
for(i = ; i <= n; i++)
for(j = m; j; j--)
sum[][i][j] += sum[][i - ][j] * bs1;
for(i = ; i <= n; i++)
for(j = m; j; j--)
sum[][i][j] += sum[][i][j + ] * bs2;
for(i = n; i; i--)
for(j = ; j <= m; j++)
sum[][i][j] += sum[][i + ][j] * bs1;
for(i = n; i; i--)
for(j = ; j <= m; j++)
sum[][i][j] += sum[][i][j - ] * bs2;
for(i = n; i; i--)
for(j = m; j; j--)
sum[][i][j] += sum[][i + ][j] * bs1;
for(i = n; i; i--)
for(j = m; j; j--)
sum[][i][j] += sum[][i][j + ] * bs2;
for(i = ; i <= n; i++)
for(j = ; j <= m; j++)
if((i ^ j ^ ) & )
ans += work(i, j) >> ;
printf("%d\n", ans);
return ;
}

Manacher的话,学完再搞吧。

上一篇:bzoj 1414: [ZJOI2009]对称的正方形


下一篇:JavaScript中事件处理