1 条题解

  • 1
    @ 2026-5-10 10:07:09

    原题链接:[http://47.121.118.174/p/618]
    没人写题解我来水一篇()
    注意到 n,mn,m 的取值范围,直接暴力枚举的时间复杂度是O(n3m3)O(n^3m^3)会超时,所以考虑用前缀和做。
    创建三个二维前缀和数组
    sumR,sumRO,sumROGsumR,sumRO,sumROG,
    分别表示在(1,1)(1,1)(i,j)(i,j)范围内
    R,RO,ROGR,RO,ROG的数量。
    大致的思路:遍历字符矩阵,前缀和数组先继承之前的数据
    (二维前缀和模板:

    $$sumR[i][j] = sumR[i-1][j]+sumR[i][j-1]-sumR[i-1][j-1];$$
    ),然后根据$a[i][j]$的值,对前缀和数组进行处理:
    a[i][j]==R>sumR[i][j]++;a[i][j]=='R'->sumR[i][j]++; a[i][j]==O>sumRO[i][j]+=sumR[i][j]a[i][j]=='O'->sumRO[i][j]+=sumR[i][j] a[i][j]==G>sumROG[i][j]+=sumRO[i][j]a[i][j]=='G'->sumROG[i][j]+=sumRO[i][j]

    Java代码如下:

    import java.io.*;
    import java.util.*;
    public class Main {
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st = new StringTokenizer(br.readLine());
            PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
            int n = Integer.parseInt(st.nextToken()); 
            int m = Integer.parseInt(st.nextToken());
            char[][] a = new char[n+1][m+1];
            long[][] sumR = new long[n+1][m+1];
            long[][] sumRO = new long[n+1][m+1];
            long[][] sumROG = new long[n+1][m+1];
            for(int i = 1;i <= n;i++) {
            	StringBuilder sb = new StringBuilder(" "+br.readLine());
            	a[i] = sb.toString().toCharArray();
            }
            for(int i = 1;i <= n;i++) {
            	for(int j = 1;j <= m;j++) {
            		sumR[i][j] = sumR[i-1][j]+sumR[i][j-1]-sumR[i-1][j-1]+(a[i][j]=='R'?1:0);
            		sumRO[i][j] = sumRO[i-1][j]+sumRO[i][j-1]-sumRO[i-1][j-1]+(a[i][j]=='O'?sumR[i][j]:0);
            		sumROG[i][j] = sumROG[i-1][j]+sumROG[i][j-1]-sumROG[i-1][j-1]+(a[i][j]=='G'?sumRO[i][j]:0);
            	}
            }
            long ans = sumROG[n][m] % 998244353;
            pw.println(ans);
            pw.flush();
        }
    }
    
    • 1

    信息

    ID
    618
    时间
    1000ms
    内存
    512MiB
    难度
    3
    标签
    递交数
    173
    已通过
    64
    上传者