1 条题解
-
1
原题链接:[http://47.121.118.174/p/618]
$$sumR[i][j] = sumR[i-1][j]+sumR[i][j-1]-sumR[i-1][j-1];$$
没人写题解我来水一篇()
注意到 的取值范围,直接暴力枚举的时间复杂度是会超时,所以考虑用前缀和做。
创建三个二维前缀和数组
分别表示在到范围内
的数量。
大致的思路:遍历字符矩阵,前缀和数组先继承之前的数据
(二维前缀和模板:
),然后根据$a[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
- 上传者