4 条题解
-
0
#include<bits/stdc++.h> using namespace std; #define int long long /* 简单说一下本题思路:ROG 算法中对三这个数一定一定敏感 思路:对每个位置的 R G计数--前缀和计数发起 2再遍历全地图 找到O 此时计数 前面 (1,1)--(x,y)-R数 后面 (x,y)--(n,m)--G数 本质:前缀和计数 + 线性三元分析 */ const int mo=998244353; const int N=2003; char a[N][N]; int sR[N][N]; int sG[N][N]; int n,m; signed main() { std::ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { sR[i][j]=(a[i][j]=='R')+sR[i-1][j]+sR[i][j-1]-sR[i-1][j-1]; sG[i][j]=(a[i][j]=='G')+sG[i-1][j]+sG[i][j-1]-sG[i-1][j-1]; } int ans=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(a[i][j]=='O') { int R=sR[i][j]; int G=sG[n][m]-sG[i-1][m]-sG[n][j-1]+sG[i-1][j-1]; ans=(ans%mo)+(R*G%mo); ans%=mo; } } cout<<ans<<"\n"; return 0; }
信息
- ID
- 618
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 普及−
- 标签
- 递交数
- 326
- 已通过
- 109
- 上传者