1.出行计划(202203-2 CSP)

问题描述

分析

对于一个计划的进入场所，只要核酸检测时间q在区间就能满足。相对于在区间内的所有时刻做完核酸的可以完成的计划增加1.
对于所有n个计划，相当于求n次区间加法
m次查询相对当于访问最后的值。
问题就转换为了区间加法问题，采用差分数组的方式求解

证明

设初始从【1，20000】中时刻，去做核算能完成的计划数都为0
定义一个计划的可行区间为，其中
在可行区间做核酸的时刻都能满足计划的要求，那么这些时刻能完成的计划数加1，对于n个计划，只需看时刻
落在多少个可行区间中，就是能完成的计划数。换一个视角，只需让计划可行区间对应的值都加上1即可。问题即是给定初值为0的【1，200000】的区间，和n个加法区间，每次让区间内的值加1，最后查询任意时刻的值。

代码

import itertools
n,m,k=map(int,input().split())
diff=[0]*(200100)
for _ in range(n):
    t,c = map(int,input().split())
    early_time = max(0,t-k-c+1)
    late_time = max(0,t-k)
    diff[early_time]+= 1 
    diff[late_time + 1] -=1
num =list(itertools.accumulate(diff))
query =[]
for _ in range(m):
    q = int(input())
    query.append(q)
    for q in query:
        print(num[q])

解释

定义差分数组diff，由于有可能为0，所以与0取最大值。
对于让区间内所有值+1，根据差分数组定义，只需让左端点+1，右端点后一项-1即可
最后计算原数组num，num下标i对于的值就是时刻i满足的计划数

复杂度分析

时间复杂度

计算差分数组为，n个区间，一共,
一次查询复杂度

空间复杂度

差分数组,原数组,为最大时间长度

2.邻域均值(202104-2 CSP)

问题描述

分析

对于图像每一个像素点，要求所有领域的平均值，一种直观的想法外层两个for循环遍历图像，里层两个for循环计算领域。但是这样做时间复杂度太高，对于大图像会超时。考虑二维矩阵的前缀和。计算一个邻域时对前缀和进行操作而避免里层循环。

证明

对于一个二维矩阵A，定义坐标前缀和,那么,由此就可以计算出每个像素的领域和

前缀和的计算

代码

#include<iostream>
using namespace std;
int p[605][605]={0};
int main(){
    int n,l,r,t;
    cin>>n>>l>>r>>t;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int temp;
            cin>>temp;
            p[i][j]=p[i][j-1]+p[i-1][j]-p[i-1][j-1]+temp;
        }
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int left=max(1,j-r), right= min(n,j+r);
            int up = max(1,i-r),down=min(n,i+r);
            int sum=p[down][right]-p[down][left-1]-p[up-1][right]+p[up-1][left-1];
            if(sum<=t*(down-up+1)*(right-left+1)){
                cnt++;
            }
        }
    }
    cout<<cnt<<endl;
    return 0;
}

解释

首先计算前缀和，然后遍历图像计算领域均值，如果领域均值大于阈值那么cnt计数+1，最后输出cnt

复杂度

时间复杂度

计算前缀和,遍历图像，计算领域均值,整个算法

空间复杂度

前缀和数组