前言

本篇文章着重介绍CSP认证第二题常见考点，以【202012-202206】6次真题的第二题为例，旨在帮助你我从70分（暴力模拟，运行超时）到100分（利用特定技巧，降低时间复杂度）。

此文参考了众多大佬的优秀文章和视频，感恩你们的分享。

考点

202009：常规模拟，不卡时间
202012：前缀和&后缀和
202104：二维前缀和
202109：一维差分
202112：分段&差值
202203：一维差分
202206：稀疏数组

前置知识学习

前缀和与差分图文并茂超详细整理（全网最通俗易懂）林小鹿@的博客-CSDN博客_前缀和差分

【小白学算法】2. 稀疏数组 - 知乎 (zhihu.com)

真题

一、前缀和&后缀和

题干

202012-2 期末预测之最佳阈值

代码（100分）

#include<bits/stdc++.h>
using namespace std;

const int MAX=1e5+5;
pair<int,int> pii[MAX];      //pair数组储存信息，每个pair存储一个同学的y和result
int 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<int,int>(-1,-1);
    for(int i = 1;i <= m;++i)   //初始化pii数组
        cin>>pii[i].first>>pii[i].second;
    sort(pii + 1,pii + 1 + m);  //将所有学生信息按照阈值从小到大排序，方便后续前缀后缀和的操作

    for(int i = 1;i <= m;++i)            //记录前缀0个数
        if(pii[i].second == 0)
            pre0[i] = pre0[i - 1] + 1;
        else
            pre0[i] = pre0[i - 1];
    for(int i = m;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分）

//注意边界 前缀和 
#include<bits/stdc++.h>
using 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<=n;++j){
			cin>>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<stdio.h>
#define MAX 500005
#define MX 10005

int main()
{
    int g[MAX]={0},c[MX]={0};
    int n;
    scanf("%d",&n);
    int i,mx=0;
    for(i=1;i<=n;++i){
        scanf("%d",&g[i]);
        if(g[i]>mx) 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;i<=n;++i){
        if(g[i]>g[i-1]&&g[i]>g[i+1]){
            ++c[g[i]];                //非零段增加
        }else if(g[i]<g[i-1]&&g[i]<g[i+1]){
            --c[g[i]];                //非零段减少
        }
    }

    int sum=0,ans=0;
    for(i=mx;i>=0;--i){
        sum+=c[i];
        if(ans<sum) ans=sum;
    }
    printf("%d",ans);
    return 0;
}

参考

CCF202109-2 非零段划分（100分）【序列处理】_海岛Blog的博客-CSDN博客

四、分段&差值

题干

202112-2 序列查询新解

代码（100分）

找到合理的循环变量和控制变量的增量和减量。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n,N;
    cin>>n>>N;
    long long A[100010];
    A[0]=0;
    for(int i=1;i<=n;++i){
        cin>>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];j<=A[i+1]-1;j=j+dr){
            gx=j/r;
            long long res=gx>fx?gx-fx:fx-gx;
            if(flag==1){    //第一个元素，单独讨论
                dr=ddr;
                flag=0;
            }else{
                dr=r;
            }
            if(j+dr-1<=A[i+1]-1){
                error+=dr*res;
            }
            if(j+dr-1>A[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<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using 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<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using 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<=n;i++){
        cin>>a[i].x>>a[i].y;
    } 

    int B[52][52];
    for(int i=S;i>=0;i--){
        for(int j=0;j<=S;j++)
            cin>>B[i][j];
    }

    int temp[52][52];
    int count=0;
    for(int i=1;i<=n;i++){
        if((a[i].x>(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(tempx<0||tempx>S) continue;
            if(tempy<0||tempy>S) 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;
}