题解 P6114 【[JOI 2019 Final]勇者ビ太郎】

FjswYuzu · 2020-02-17 18:19:59 · 题解

前缀和优化裸题。

考虑题目所说的四元组，无非不是求有多少个满足下面两个条件的 JOI：

• O 与 J 同行，并且在 J 的左边；
• I 与 J 同列，并且在 J 的上面。

简化了题意，很显然我们只需要找到 J 去计算贡献。往回找 O 和 I 复杂度很高，我们考虑用前缀和优化。遍历这个网格。对每一行分别遍历，只有三种情况：

• 如果这个是 O，将这一行 O 的前缀和 f 加 1；
• 如果这个是 I，无法用一个数存，开一个数组 sum，将 sum_j 加 1；
• 否则计算贡献，答案加上 f \times sum_j。

有了这些，代码就很容易了。

#include<bits/stdc++.h>
using namespace std;
long long n,m,ans,cnt[3005];
char maplive[3005][3005];
int main(){
    scanf("%lld %lld",&n,&m);
    for(long long i=1;i<=n;++i) scanf("%s",maplive[i]+1);
    for(long long i=n;i;--i)
    {
        long long froon=0;
        for(long long j=m;j;--j)
        {
            if(maplive[i][j]=='J')  ans+=cnt[j]*froon;
            cnt[j]+=1ll*int(maplive[i][j]=='I');
            froon+=1ll*int(maplive[i][j]=='O');
        }
    }
    printf("%lld",ans);
    return 0;
}