4 条题解

  • 0
    @ 2026-5-30 9:21:52
    #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
    上传者