记录47
#include<bits/stdc++.h> using namespace std; int main(){ int n,m,w[55]={},b[55]={},r[55]={},cnt=0; int cntW=0,cntB=0,cntR=0; char c; cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>c; if(c=='W') w[i]++; if(c=='B') b[i]++; if(c=='R') r[i]++; } w[i]+=w[i-1]; b[i]+=b[i-1]; r[i]+=r[i-1]; } int min_=999999999; for(int i=2;i<=n-1;i++){ for(int j=i;j<=n-1;j++){ cnt=0; cntB=(j-i+1)*m-(b[j]-b[i-1]); cntW=(i-1)*m-w[i-1]; cntR=(n-j)*m-(r[n]-r[j]); //printf("W：%d B：%d R：%d\n",cntW,cntB,cntR); cnt+=cntB+cntW+cntR; if(min_>cnt) min_=cnt; } } cout<<min_; return 0; }题目传送门https://www.luogu.com.cn/problem/P3392
突破点
- 从最上方若干行（至少一行）的格子全部是白色的；
- 接下来若干行（至少一行）的格子全部是蓝色的；
- 剩下的行（至少一行）全部是红色的；
希望涂最少的格子，使这块布成为一个合法的图案。
对于 100% 的数据，N,M≤50。
思路
既然要图最少的格子，让这块布成为一个合法图案，数据又较小，直接暴力遍历所有情况
- 将到这一行的全部色块进行统计👉前缀和
- 确保第一行跟最后一行保持规定颜色（永远符合规定）
- 白色不断向下侵袭到全满👉一个循环
- 蓝色从一个到全满，红色由全满到一个
注意：这里说的全满是指符合三色规则下能达到的最大值
代码简析
#include<bits/stdc++.h> using namespace std; int main(){ int n,m,w[55]={},b[55]={},r[55]={},cnt=0; int cntW=0,cntB=0,cntR=0; char c; cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>c; if(c=='W') w[i]++; if(c=='B') b[i]++; if(c=='R') r[i]++; } w[i]+=w[i-1]; b[i]+=b[i-1]; r[i]+=r[i-1]; } int min_=999999999; ... return 0; }cnt👉计算所需涂改的色块
i👉到这一行所以占的全部颜色
注意：关于前缀和的相关知识点，本文的补充部分会详细介绍zhoi
#include<bits/stdc++.h> using namespace std; int main(){ int n,m,w[55]={},b[55]={},r[55]={},cnt=0; int cntW=0,cntB=0,cntR=0; char c; cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>c; if(c=='W') w[i]++; if(c=='B') b[i]++; if(c=='R') r[i]++; } w[i]+=w[i-1]; b[i]+=b[i-1]; r[i]+=r[i-1]; } int min_=999999999; for(int i=2;i<=n-1;i++){ for(int j=i;j<=n-1;j++){ cnt=0; cntB=(j-i+1)*m-(b[j]-b[i-1]); cntW=(i-1)*m-w[i-1]; cntR=(n-j)*m-(r[n]-r[j]); cnt+=cntB+cntW+cntR; if(min_>cnt) min_=cnt; } } cout<<min_; return 0; }重点理解这里的双重for循环
其中i是以蓝色的视角来打开的👉开始位置只能是从第2行到第n-1行
j是蓝色的不断扩大👉蓝色不断铺满自己的色块
注意：此时的红白会在蓝色的不同状态下进行改动，牵一发而动全身
cnt=0;👉每一次重新计数所需涂改的色块
cntB=(j-i+1)*m-(b[j]-b[i-1]);👉(j-i+1)*m是目标涂满的蓝色格子，(b[j]-b[i-1])前缀和求目标蓝色段的蓝色和，相减得到需要涂的块数（b[j]为蓝色截至点，b[i-1]为蓝色开始点前一个）
cntW=(i-1)*m-w[i-1];👉(i-1)*m目标白色格子，w[i-1]目标内存在的白色块数,相减得到需要涂的块数（i-1为白色行数，w[i-1]白色截至点）
cntR=(n-j)*m-(r[n]-r[j]);👉(n-j)*m目标红色格子，(r[n]-r[j])目标内存在的白色块数,相减得到需要涂的块数（n-j为红色行数，r[n]红色截至点，r[j]红色截至点前一个）
补充
CSP-J 前缀和知识点完全总结
一、前缀和的本质
一句话定义：前缀和是原数组的累加缓存，能将区间求和O(n)降为O(1)，是"空间换时间"的经典思想。
核心公式：
pre[i] = a[1] + a[2] + ... + a[i] sum(l, r) = pre[r] - pre[l-1]二、一维前缀和（CSP-J必考）
1. 基本模板
const int N = 1e5 + 10; long long a[N], pre[N]; // 必须用long long // 预处理 O(n) for (int i = 1; i <= n; i++) { cin >> a[i]; pre[i] = pre[i-1] + a[i]; } // 查询区间[l, r]的和 O(1) long long sum = pre[r] - pre[l-1];2. 高频应用场景
场景 题目特征 代码片段 区间求和 "求第l到r个数的和" pre[r] - pre[l-1]连续子数组和 "求和为k的连续子数组个数" 用 map存前缀和出现次数平均数问题 "求平均值≥k的最长区间" 前缀和+二分/双指针 差分还原 "多次区间加后求最终数组" 差分数组→前缀和还原 三、二维前缀和（CSP-J重点）
1. 定义与推导
pre[i][j] = Σ a[x][y] (1≤x≤i, 1≤y≤j)递推式：
pre[i][j] = a[i][j] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1];2. 子矩阵求和
求
(x1,y1)到(x2,y2)的矩形和：sum = pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1];3. 模板代码
const int N = 1010; int a[N][N], pre[N][N]; // 预处理 O(n²) for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; pre[i][j] = a[i][j] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1]; } } // 查询 O(1) int query(int x1, int y1, int x2, int y2) { return pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1]; }四、高频题型与解题框架
题型1：最大子矩阵和
// 枚举行区间，压缩为一维前缀和 for (int top = 1; top <= n; top++) { for (int bottom = top; bottom <= n; bottom++) { int sum = 0, maxSum = -INF; for (int col = 1; col <= m; col++) { // 将[top,bottom]行压缩为一列 int colSum = pre[bottom][col] - pre[top-1][col]; sum = max(sum + colSum, colSum); // Kadane算法 maxSum = max(maxSum, sum); } } } // 复杂度：O(n²m)题型2：均值≥k的最大子矩阵
// 二分答案 + 前缀和判正 bool check(double mid) { // 构造b[i][j] = a[i][j] - mid // 用二维前缀和找是否存在正和子矩阵 }题型3：差分+前缀和
// 多次区间加，最后求数组 int diff[N] = {0}; for (int i = 1; i <= m; i++) { diff[l] += x; diff[r+1] -= x; } // 前缀和还原 for (int i = 1; i <= n; i++) { a[i] = a[i-1] + diff[i]; }五、边界处理（易错点）
1. 下标从1开始
// ✅ 推荐：下标从1开始，pre[0]=0，公式统一 pre[i] = pre[i-1] + a[i]; // ❌ 错误：下标从0开始，pre[-1]越界 pre[i] = (i>0 ? pre[i-1] : 0) + a[i]; // 需要特判2. long long必用
// 前缀和极易溢出，必须用long long long long pre[N]; // a[i]最大1e9, n=1e5时，和可达1e14 > int3. 查询越界检查
cpp
复制
// 查询前确保l≥1, r≤n if (l < 1 || r > n) return -1; // 非法查询 long long sum = pre[r] - pre[l-1];六、与其他算法结合（CSP-J进阶）
1. 前缀和 + 二分
// 求和≥k的最小区间 int l = 1, r = n, ans = -1; while (l <= r) { int mid = (l + r) / 2; if (check(mid) >= k) { ans = mid; r = mid - 1; } else { l = mid + 1; } } // check函数：是否存在长度≤mid且和≥K的区间 bool check(int len) { for (int i = len; i <= n; i++) { if (pre[i] - pre[i-len] >= K) return true; } return false; }2. 前缀最值
// pre_max[i] = max(a[1..i]) pre_max[i] = max(pre_max[i-1], a[i]); // pre_min[i] = min(a[1..i]) pre_min[i] = min(pre_min[i-1], a[i]);七、复杂度分析（背诵）
操作 时间 空间 说明 预处理 O(n) 或 O(n²) O(n) 或 O(n²) 一次计算，多次查询 单次查询 O(1) 0 直接相减 整体优势 将O(n)降为O(1) 牺牲空间换时间 缓存思想 八、CSP-J记忆口诀
前缀和， O(1)，下标从1开始记
二维加，减两次，最后加上重复区
long long不能省，溢出见祖宗
差分还原要当心，l-1别越界
最大子段Kadane，矩阵压缩降一维
九、一句话总结
前缀和 = 累加缓存 = 区间求和O(1)，CSP-J中任何需要反复求和的题，先想前缀和，再想其他优化。
)
