前缀和、差分、二分

前缀和

1. 激光炸弹

99. 激光炸弹 - AcWing题库

二维前缀和的模板题

这里注意一下边长是R 矩形是(R-1)*(R-1)

#include 
using namespace std;
const int N=5e3+10;
int point[N][N];
int sum[N][N];
int main()
{
    int n,r;
    int tx,ty;
    cin>>n>>r;
    tx=ty=r;
    for(int i=0;i
    {
        int x,y,v;
        cin>>x>>y>>v;
        x++,y++;
        point[x][y]+=v;
        tx=max(x,tx);
        ty=max(y,ty);
    }
    for(int i=1;i<=tx;i++)
        for(int j=1;j<=ty;j++)
            sum[i][j]=point[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
    int ans=0;
    for(int i=r;i<=tx;i++)
        for(int j=r;j<=ty;j++)
            ans=max(ans,sum[i][j]-sum[i-r][j]-sum[i][j-r]+sum[i-r][j-r]);
    cout<
    return 0;
}

差分

1. 增减序列

100. 增减序列 - AcWing题库

 则操作数就是max(p,q),结果种数就是abs(p-q)+1

#include
using namespace std;
typedef long long ll;
const int N=1e5+10;
int a[N],b[N];
int n;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) b[i]=a[i]-a[i-1];//b是a的差分
    ll p=0,q=0;//p是b中的正数，q是b中的负数
    for(int i=2;i<=n;i++)
        if(b[i]>0) p+=b[i];
       else q-=b[i];
    printf("%lld\n",max(p,q));
    printf("%lld\n",abs(p-q)+1);
    return 0;
}

二分 

1.最佳牛围栏

102. 最佳牛围栏 - AcWing题库

二分平均值，然后每个数减去平均值，看是否存在连续的长度都是大于等于0的区间，假如有则满足

#include
using namespace std;
typedef long long ll;
const int N=1e5+10;
double a[N],s[N];
int n,m;
bool judge(double mid)
{
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i]-mid;//预处理出来a[i]-mid的前缀和
    double mins=0;//定义前1~i-m中的最小值
    for(int i=m;i<=n;i++)
    {
        mins=min(mins,s[i-m]);//更新最小值
        if(s[i]>=mins) return true;//假如这段区间前缀和差值是大于等于0的说明这段区间是满足的
    }
    return false;//反之不满足
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lf",&a[i]);
    double l=1,r=100000;
    while(r-l>1e-5)//比精度多两位
    {
        double mid=(l+r)/2;
        if(judge(mid)) l=mid;//假如满足，则可以扩大
        else r=mid;
    }
    printf("%d\n",(int)(r*1000));
    return 0;
}

2.特殊排序（交互题）

113. 特殊排序 - AcWing题库

一开始不知道交互式问题怎么写，其实int N 表示N个整数，你只需要返回一个排好序的vector

样例那里就是

指的是对于3个数的每组compare
compare（1，1）=0
compare（1，2）=1
compare（1，3）=0
compare（2，1）=0
compare（2，2）=0
compare（2，3）=0
compare（3，1）=1
compare（3，2）=1
compare（3，3）=0

不需要满足单调性也可二分

先找小于等于i的数，然后在从前往后交换到r这个位置上即可

// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.
 
class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> res(1,1);//初始化答案，刚开始只有1这个数，长度是1
        for(int i=2;i<=N;i++)//枚举剩下的数
        {
            int l=0,r=res.size()-1;
            while(l//二分查找小于i的数
            {
                int mid=l+r+1>>1;
                if(compare(res[mid],i)) l=mid;//假如res[mid]
                else r=mid-1;//反之在左边
            }
            res.push_back(i);//把i放在末尾
            for(int j=res.size()-2;j>r;j--) swap(res[j],res[j+1]);//然后把i换到r+1这个位置上
            if(compare(i,res[r])) swap(res[r],res[r+1]);//假如r这个位置比我大，说明在r这个位置
        }
        return res;
    }
};