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

传送门

很蒙蔽，不知道怎么搞。

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

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

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

比如

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的话，学完再搞吧。

巴特西

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

最新文章

热门文章