自动搬运

查看原文

来自洛谷，原作者为

	chenzefan 蒟蒻一枚||六年级||五级钩||GESP七级

搬运于2025-08-24 23:10:15，当前版本为作者最后更新于2025-05-10 10:46:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

涉及知识

• 预处理——前缀和。

思路

暴力，时间复杂度 $O(H^2W^2)$，因为数据范围是 $2 \le H,W \le 3000$，显然无法通过。

大胆猜一下，正解时间复杂度应该为 $O(HW)$。

读题易知，这题需要前缀和预处理。输入后计算一下，部分代码如下：

for(int i=1;i<=H;i++)
    for(int j=W;j>=1;j--)
        sum_O[i][j]=sum_O[i][j+1]+(a[i][j]=='O');
for(int j=1;j<=W;j++)
    for(int i=H;i>=1;i--)
        sum_I[i][j]=sum_I[i+1][j]+(a[i][j]=='I');

其中 sum_O[i][j] 表示对于第 $i$ 行中第 $j$ 列到第 $W$ 列中 O 的数量。sum_I[i][j] 表示对于第 $j$ 列中第 $i$ 行到第 $H$ 行中 I 的数量。

预处理结束，开始操作求值。

对于每个 $1 \le i \le H$ 和 $1 \le j \le W$，若 $a_{i,j}$ 是 J，则累加答案。不难发现，答案就是 $sum\_O[i][j] \times sum\_I[i][j]$。

注意：十年 OI 一场空，不开 long long 见祖宗。求值时注意要开 long long！

思路分析好了，相信聪明的你一定会写代码了吧？

完整 AC 代码

#include<bits/stdc++.h> 
using namespace std;
#define int long long
const int N=3005;
int H,W,sum_O[N][N],sum_I[N][N],ans;
char a[N][N];
signed main(){
	scanf("%lld%lld",&H,&W);
	for(int i=1;i<=H;i++)
		for(int j=1;j<=W;j++)
			cin>>a[i][j];
    for(int i=1;i<=H;i++)
		for(int j=W;j>=1;j--)
			sum_O[i][j]=sum_O[i][j+1]+(a[i][j]=='O');
	for(int j=1;j<=W;j++)
		for(int i=H;i>=1;i--)
			sum_I[i][j]=sum_I[i+1][j]+(a[i][j]=='I');
	for(int i=1;i<=H;i++)
		for(int j=1;j<=W;j++)
			if(a[i][j]=='J') ans+=sum_O[i][j]*sum_I[i][j];
	printf("%lld",ans);
    return 0;   
}

最后，我提出一个疑问：为啥 JOI 这类题总是如此雷同啊？