题解：P11788 [JOI 2019 Final] 勇者比太郎 / Bitaro the Brave

chenzefan · 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 这类题总是如此雷同啊？