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

· · 题解

思路

观察题目中的要求，可以转化为：对于每一个 J，计算它同一行且列坐标大于它的 O 和它同一列且行坐标大于它的 I 的点对数数。

我们用前缀和来计算某一个矩阵中 O 和 I 的个数。

AC 代码：

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
using namespace std;
const int N=3e3+5;
const int INF=0x3f3f3f3f;
const double EPS=10e-6;
const int MOD=1e9+7;
int n,m,ans,sumJ[N][N],sumO[N][N],sumI[N][N];
char mp[N][N];
int calc(int x,int y,int xx,int yy,int op){
    if(op==1)return sumO[xx][yy]-sumO[xx][y-1]-sumO[x-1][yy]+sumO[x-1][y-1];
    if(op==2)return sumI[xx][yy]-sumI[xx][y-1]-sumI[x-1][yy]+sumI[x-1][y-1];
}
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>mp[i][j];
            sumJ[i][j]=sumJ[i-1][j]+sumJ[i][j-1]-sumJ[i-1][j-1]+(mp[i][j]=='J');
            sumO[i][j]=sumO[i-1][j]+sumO[i][j-1]-sumO[i-1][j-1]+(mp[i][j]=='O');
            sumI[i][j]=sumI[i-1][j]+sumI[i][j-1]-sumI[i-1][j-1]+(mp[i][j]=='I');
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(mp[i][j]=='J'){
                int cntO=calc(i,j+1,i,m,1);
                int cntI=calc(i+1,j,n,j,2);
                ans+=cntO*cntI;
            //  cout<<cntO<<" "<<cntI<<endl; 
            }
        }
    }
    cout<<ans;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int T=1;
//  cin>>T;
    while(T--)solve();
    return 0;
}