QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#191117 | #1088. Border Similarity Undertaking | andyc_03 | WA | 4ms | 22024kb | C++14 | 2.7kb | 2023-09-29 18:09:50 | 2023-09-29 18:09:50 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2005;
int n,m;
char a[2][maxn][maxn];
ll ans;
int L[maxn],R[maxn],U[maxn][maxn],D[maxn][maxn];
ll ul[maxn][maxn],dl[maxn][maxn],ur[maxn][maxn],dr[maxn][maxn];
void calc(int lx,int rx,int ly,int ry,int p)
{
// cerr<<lx<<" "<<rx<<" "<<ly<<" "<<ry<<endl;
int mid=ly+ry>>1;
for(int i=lx;i<=rx;i++)
{
L[i]=R[i]=0;
while(mid-L[i]>ly && a[p][i][mid-L[i]-1]==a[p][i][mid-L[i]]) L[i]++;
while(mid+1+R[i]<ry && a[p][i][mid+R[i]+2]==a[p][i][mid+R[i]+1]) R[i]++;
// cerr<<L[i]<<" "<<R[i]<<endl;
}
for(int i=lx;i<=rx;i++)
for(int j=ly;j<=ry;j++)
U[i][j]=D[i][j]=0;
for(int i=lx;i<=rx;i++)
for(int j=ly;j<=ry;j++)
U[i][j]=(i!=lx && a[p][i][j]==a[p][i-1][j])?U[i-1][j]:i;
for(int i=rx;i>=lx;i--)
for(int j=ly;j<=ry;j++)
D[i][j]=(i!=rx && a[p][i][j]==a[p][i+1][j])?D[i+1][j]:i;
// cerr<<D[1][2]<<endl;
for(int i=lx-1;i<=rx+1;i++) for(int j=lx-1;j<=rx+1;j++) ul[i][j]=dl[i][j]=ur[i][j]=dr[i][j]=0;
for(int i=lx;i<=rx;i++)
{
for(int j=mid-L[i];j<=mid;j++)
ul[i][U[i][j]]++,dl[i][D[i][j]]++;
for(int j=mid+1;j<=mid+R[i]+1;j++)
dr[i][D[i][j]]++,ur[i][U[i][j]]++;
for(int j=lx+1;j<=i;j++)
ul[i][j]+=ul[i][j-1],ur[i][j]+=ur[i][j-1];
for(int j=rx-1;j>=i;j--)
dl[i][j]+=dl[i][j+1],dr[i][j]+=dr[i][j+1];
}
// cerr<<ul[1][3]<<endl;
for(int i=lx;i<=rx;i++)
for(int j=i+1;j<=rx;j++)
if(a[p][i][mid]==a[p][j][mid] && a[p][i][mid+1]==a[p][j][mid+1] && a[p][i][mid]==a[p][j][mid+1])
{
// cerr<<i<<" "<<j<<endl;
ll gs1,gs2;
if(L[i]<L[j]) gs1=ul[i][j];
else gs1=dl[i][j];
if(R[i]<R[j]) gs2=ur[i][j];
else gs2=dr[i][j];
// cerr<<gs1<<" "<<gs2<<endl;
ans+=gs1*gs2;
}
}
void solve(int lx,int rx,int ly,int ry)
{
if(lx==rx || ly==ry) return;
if(rx-lx>ry-ly)
{
int mid=rx+lx>>1;
calc(ly,ry,lx,rx,1);
solve(lx,mid,ly,ry);
solve(mid+1,rx,ly,ry);
}
else
{
int mid=ly+ry>>1;
// cerr<<mid<<endl;
calc(lx,rx,ly,ry,0);
// cerr<<ans<<endl;
solve(lx,rx,ly,mid);
solve(lx,rx,mid+1,ry);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%s",a[0][i]+1);
for(int j=1;j<=m;j++)
a[1][j][i]=a[0][i][j];
}
solve(1,n,1,m);
printf("%lld\n",ans);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 18056kb
input:
3 5 zzzzz zxzxz zzzzz
output:
3
result:
ok answer is '3'
Test #2:
score: 0
Accepted
time: 0ms
memory: 22024kb
input:
4 4 abbc bcca babc acbb
output:
0
result:
ok answer is '0'
Test #3:
score: -100
Wrong Answer
time: 4ms
memory: 18068kb
input:
12 12 abbabaaaaabb ababaaaaaabb aaabbbbbabbb aabababaaaba abbbaaabaaba baaababbbaba aaaaababbaaa bbabbbbbabaa bbbabbaabaaa aabbbaaaabba babaabababaa bababaabaaba
output:
17
result:
wrong answer expected '25', found '17'