前言
本篇文章着重介绍CSP认证第二题常见考点，以【202012-202206】6次真题的第二题为例，旨在帮助你我从70分（暴力模拟，运行超时）到100分（利用特定技巧，降低时间复杂度）。
此文参考了众多大佬的优秀文章和视频，感恩你们的分享。
考点
- 202009：常规模拟，不卡时间
- 202012：前缀和&后缀和
- 202104：二维前缀和
- 202109：一维差分
- 202112：分段&差值
- 202203：一维差分
- 202206：稀疏数组
前置知识学习
前缀和与差分 图文并茂 超详细整理（全网最通俗易懂）林小鹿@的博客-CSDN博客_前缀和差分
【小白学算法】2. 稀疏数组 – 知乎 (zhihu.com)
真题
一、前缀和&后缀和
题干
202012-2 期末预测之最佳阈值
代码（100分）
#includeusing namespace std;const int MAX=1e5+5;pair pii[MAX]; //pair数组储存信息，每个pair存储一个同学的y和resultint pre0[MAX]; //记录该位置及前面的result为0的个数（前缀和）int rear1[MAX]; //记录该位置及后面的result为1的个数（后缀和）int k = -1,ma = 0; //k用来记录最佳阈值，ma用来存储最佳阈值对应的预测成功的数目int main(){ int m; cin>>m; //输入m pii[0] = pair(-1,-1); for(int i = 1;i >pii[i].first>>pii[i].second; sort(pii + 1,pii + 1 + m); //将所有学生信息按照阈值从小到大排序，方便后续前缀后缀和的操作 for(int i = 1;i = 1;--i) //记录后缀1个数 if(pii[i].second == 1) rear1[i] = rear1[i + 1] + 1; else rear1[i] = rear1[i + 1]; for(int i = 1;i <= m;++i){ //最终处理 if(pii[i].first == pii[i - 1].first) continue; //如果有阈值相同的情况，直接跳过,避免重复 if(ma <= pre0[i - 1] + rear1[i])//更新k和ma ma = pre0[i - 1] + rear1[i],k = pii[i].first; } cout<<k; return 0;}参考
期末预测之最佳阈值_Alan_Lowe的博客-CSDN博客_期末预测之最佳阈值
二、二维前缀和
题干
202104-2 领域均值
代码（100分）
//注意边界 前缀和 #includeusing namespace std;const int MAX=6e2+10;int main(){int n,L,r,t,res=0;cin>>n>>L>>r>>t;int g[MAX][MAX];for(int i=1;i<=n;++i)for(int j=1;j>g[i][j];g[i][j]+=g[i-1][j]+g[i][j-1]-g[i-1][j-1]; //前缀和预处理}for(int i=1;i<=n;++i)for(int j=1;j<=n;++j){int left=max(0,j-r-1);int right=min(n,j+r);int down=min(n,i+r);int up=max(0,i-r-1);int sum=g[down][right]-g[up][right]-g[down][left]+g[up][left]; //前缀和int num=(right-left)*(down-up); //求邻域内元素的个数if(sum<=t*num) res++;}cout<<res<<endl;return 0;}三、一维差分
题干
202109-2 非零段划分
代码（100分）
//注意边界，一维差分，C语言实现#include#define MAX 500005#define MX 10005int main(){ int g[MAX]={0},c[MX]={0}; int n; scanf("%d",&n); int i,mx=0; for(i=1;imx) mx=g[i]; } int t=1;for(i=1;i<=n;++i){if(g[i]==g[i-1]) continue; //去重g[t]=g[i]; ++t;}n=t-1; g[0]=g[n+1]=0; //首尾各加0，便于比较 for(i=1;ig[i-1]&&g[i]>g[i+1]){ ++c[g[i]]; //非零段增加 }else if(g[i]<g[i-1]&&g[i]=0;--i){ sum+=c[i]; if(ans<sum) ans=sum; } printf("%d",ans); return 0;}参考
CCF202109-2 非零段划分（100分）【序列处理】_海岛Blog的博客-CSDN博客
四、分段&差值
题干
202112-2 序列查询新解
代码（100分）
找到合理的循环变量和控制变量的增量和减量。
#includeusing namespace std;int main(){ int n,N; cin>>n>>N; long long A[100010]; A[0]=0; for(int i=1;i>A[i]; } A[n+1]=N; long long r=N/(n+1); long long dr=r; long long ddr; long long error=0; long long fx=0,gx=0; int flag=0; for(int i=0;i<=n;++i){ fx=i; for(long long j=A[i];jfx?gx-fx:fx-gx; if(flag==1){ //第一个元素，单独讨论 dr=ddr; flag=0; }else{ dr=r; } if(j+dr-1A[i+1]-1){ //最后一个元素，单独讨论 error += (A[i+1]-j)*res; ddr =dr-(A[i+1]-j); flag=1; } } } cout<<error; return 0;}参考
202112（第24次）CSP真题202112-1,2讲解_哔哩哔哩_bilibili
五、一维差分
题干
202203-2 出行计划
代码（100分）
逆向思考，优先处理场所需求，判断出进入该场所需要的最早时间核酸报告和最晚时间核酸报告。
//注意边界#include#include#include#include#includeusing namespace std;const int N=2e5+10;int n,m,k,t,c,q;int cnt[N];int main(){ scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++){ scanf("%d%d",&t,&c); int x=t+1-k-c,y=t-k; if(y<=0) continue; x=max(1,x); cnt[x]++; //差分 cnt[y+1]--; } for(int i=1;i<=200000;i++) cnt[i]+=cnt[i-1]; while(m--){ scanf("%d",&q); //查询 printf("%d\n",cnt[q]); } return 0;}参考
CCF-CSP 202203-2 出行计划 差分算法满分题解+解题思路_只须一笑不须愁X的博客-CSDN博客
六、稀疏数组
题干
202206-2 寻宝！大冒险！
代码（100分）
#include#include#includeusing namespace std;int main(){ int n,L,S; cin>>n>>L>>S; struct tree{ int x; int y; } a[1010]; for(int i=1;i>a[i].x>>a[i].y; } int B[52][52]; for(int i=S;i>=0;i--){ for(int j=0;j>B[i][j]; } int temp[52][52]; int count=0; for(int i=1;i(L-S)) || (a[i].y>(L-S))){ continue; } for(int x=S;x>=0;x--){ //缩小查找的绿化图规模 for(int y=0;y<=S;y++) temp[x][y]=0; } for(int k=1;k<=n;k++){ //同上 int tempx=a[k].x-a[i].x; int tempy=a[k].y-a[i].y; if(tempxS) continue; if(tempyS) continue; temp[tempx][tempy]=1; } int flag=0; for(int x=S;x>=0;x--){ for(int y=0;y<=S;y++) if(temp[x][y]!=B[x][y]) flag=1; } if(flag==0) count++; } cout<<count; return 0;}参考
暂时找不到当初参考的博文了。
结语
欢迎大家交流指正。祝福大家在CCF-CSP认证都能取得佳绩!