首页 > 代码库 > BZOJ1397 Ural 1486 Equal squares

BZOJ1397 Ural 1486 Equal squares

2024-11-20 02:47:02   202人阅读

首先二分答案ans，然后只要进行判断答案ans是否可行即可。

验证方法：首先对每一个位置，求出它开始长度为ans的横行的hash值

然后求出每一个hash值的长度为ans的竖列的Hash值

查看是否有两个Hash值相同即可（比如我们可以基数排序。。。做什么大死！）

 

技术分享
 1 /************************************************************** 2     Problem: 1397 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:2084 ms 7     Memory:5052 kb 8 ****************************************************************/ 9  10 #include <cstdio>11 #include <algorithm>12  13 using namespace std;14 typedef long long ll;15  16 const ll B1 = 103;17 const ll B2 = 211;18 const int N = 505;19  20 int n, m;21 char a[N][N];22 ll p1[N], p2[N];23 ll h[N][N], hash[N * N];24  25 bool check(int x) {26   int i, j, t;27   ll tmp;28   for (i = 1; i <= n; ++i) {29     for (tmp = 0, j = 1; j < x; ++j)30       (tmp *= B1) += a[i][j], h[i][j] = 0;31     for (j = x; j <= m; ++j)32       h[i][j] = tmp = tmp * B1 - p1[x] * a[i][j - x] + a[i][j];33   }34   for (t = 0, i = x; i <= m; ++i) {35     for (tmp = 0, j = 1; j < x; ++j)36       (tmp *= B2) += h[j][i];37     for (j = x; j <= n; ++j)38       hash[t++] = tmp = tmp * B2 - p2[x] * h[j - x][i] + h[j][i];39   }40   sort(hash, hash + t);41   for (i = 1; i < t; ++i)42     if (hash[i] == hash[i - 1]) return 1;43   return 0;44 }45  46 int main() {47   int i, j, l, r, mid;48   scanf("%d%d\n", &n, &m);49   for (i = 1; i <= n; ++i) {50     gets(a[i] + 1);51     for (j = 1; j <= m; ++j)52       a[i][j] -= ‘a‘ - 1;53   }54   l = 1, r = min(n, m) + 1, p1[0] = p2[0] = 1;55   for (i = 1; i <= r; ++i)56     p1[i] = p1[i - 1] * B1, p2[i] = p2[i - 1] * B2;57   while (l + 1 < r) {58     mid = (l + r) >> 1;59     if (check(mid)) l = mid;60     else r = mid;61   }62   printf("%d\n", l);63   return 0;64 }
View Code

 

BZOJ1397 Ural 1486 Equal squares


联系
我们