洛谷傳送門

文章目錄

• 題目描述
• 解析
• 代碼

題目描述

解析

做三個hash
分一下正方形邊長的奇偶性
然后枚舉中心點，二分邊長即可
有點類似模擬賽那道紅十字的題
我一開始覺得分奇偶好麻煩啊
為什么不直接枚舉左上方的點二分呢？awa
很遺憾的是…
那樣答案就沒有單調性了啊…
我個傻子qwq

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long typedef unsigned long long ull; const int N = 1050; const ll mod=998244323; const int p1=1e9+7; const int p2=1e9+9; int n,m; int a[N][N]; ull h[N][N],h1[N][N],h2[N][N];//一左右，二上下 ull mi1[N],mi2[N]; void hash(){mi1[0]=mi2[0]=1;for(int i=1;i<=max(n,m);i++){mi1[i]=mi1[i-1]*p1;mi2[i]=mi2[i-1]*p2;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){h[i][j]=h[i][j-1]*p1+a[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){h[i][j]=h[i-1][j]*p2+h[i][j];}}for(int i=1;i<=n;i++){for(int j=m;j>=1;j--){h1[i][j]=h1[i][j+1]*p1+a[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){h1[i][j]=h1[i-1][j]*p2+h1[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){h2[i][j]=h2[i][j-1]*p1+a[i][j];}}for(int i=n;i>=1;i--){for(int j=1;j<=m;j++){h2[i][j]=h2[i+1][j]*p2+h2[i][j];}} }ull ask(int x1,int y1,int x2,int y2){return h[x2][y2]-h[x1-1][y2]*mi2[x2-x1+1]-h[x2][y1-1]*mi1[y2-y1+1]+h[x1-1][y1-1]*mi2[x2-x1+1]*mi1[y2-y1+1]; } ull ask1(int x1,int y1,int x2,int y2){return h1[x2][y1]-h1[x1-1][y1]*mi2[x2-x1+1]-h1[x2][y2+1]*mi1[y2-y1+1]+h1[x1-1][y2+1]*mi2[x2-x1+1]*mi1[y2-y1+1]; } ull ask2(int x1,int y1,int x2,int y2){return h2[x1][y2]-h2[x2+1][y2]*mi2[x2-x1+1]-h2[x1][y1-1]*mi1[y2-y1+1]+h2[x2+1][y1-1]*mi2[x2-x1+1]*mi1[y2-y1+1]; } ll ans; bool check(int x1,int y1,int x2,int y2){return ask(x1,y1,x2,y2)==ask1(x1,y1,x2,y2)&&ask(x1,y1,x2,y2)==ask2(x1,y1,x2,y2); } int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);}hash();//printf("%llu\n%llu\n%llu\n",ask(1,3,2,4),ask1(1,3,2,4),ask2(1,3,2,4));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){int st=0,ed=min(n-i,min(m-j,min(i-1,j-1)));while(st<ed){int mid=(st+ed+1)>>1;if(check(i-mid,j-mid,i+mid,j+mid)) st=mid;else ed=mid-1;}ans+=st+1;}}for(int i=1;i<n;i++){for(int j=1;j<m;j++){int st=0,ed=min(n-i,min(m-j,min(i,j)));while(st<ed){int mid=(st+ed+1)>>1;if(check(i-mid+1,j-mid+1,i+mid,j+mid)) st=mid;else ed=mid-1;}ans+=st;}}printf("%lld\n",ans); } /* 5 5 4 2 4 4 4 3 1 4 4 3 3 5 3 3 3 3 1 5 3 3 4 2 1 2 4 */

總結

以上是生活随笔為你收集整理的P2601 [ZJOI2009]对称的正方形（二维哈希）（二分）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。