搜索
简帛阁>技术文章>AcWing 蓝桥杯专题训练 :(一)二分与前缀和 例题

AcWing 蓝桥杯专题训练 :(一)二分与前缀和 例题

AcWing 蓝桥杯专题训练 :(一)二分与前缀和 例题

AcWing账号ID:田所浩二

注:可能会和y总的代码有不一样的地方

写在前面:y总的二分模板分为两类:其一是类似于“分巧克力”中的求最大值,其二类似于机器人跳跃问题中的求最小值。实际上这种二分的核心在于从题目给出的数据范围中1到N中(例如[1,1e5])找出满足条件(题目要求)的值是一段连续的数组。
即:
对于模板二,我们要求符合条件的最大值,这里我是这么理解的:当mid的值符合条件时我们就把他当成现在不断二分的这个区间的l,这样在之后二分出现能满足题意要求的mid的时候我们就不断更新l为 l =mid;直到l = r,这样说明整个1-N已经遍历完成此时的l是满足条件的答案中最大的。与此同时mid如果不满足条件,由于r是题目中取值范围最大值所以只需要-1即可([l, r-1])。
注意这里能不断更新l是因为:更新前后的l之间的数是连续递增的,即然新的l能满足,那么说明他们之间的数也能满足

对于模板一,同理我对模板二的理解,不断更新满足题目要求的最小值,将其作为右端点压缩区间。

另外要注意求最大值mid=(l+r+1)/2
求最小值mid=(l+r)/2

  1. 数的范围(掌握)
    这道题是将模板一和模板二结合到了一起。
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=110000;
int a[N];
int x;
int main()
{<!-- -->
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {<!-- -->
        cin>>a[i];
    }
    for(int i=0;i<m;i++)
    {<!-- -->
        cin>>x;
        int l=0,r=n-1;
        while(l<r)
        {<!-- -->
            int mid=(l+r)/2;
            if(a[mid]>=x)
            {<!-- -->
                r=mid;
            }
            else
            {<!-- -->
                l=mid+1;
            }
        }
        if(a[r]==x)
        {<!-- -->
            cout<<r<<" ";
            l=0,r=n-1;
            while(l<r)
            {<!-- -->
                int mid=(l+r+1)/2;
                if(a[mid]<=x)
                {<!-- -->
                    l=mid;
                }
                else
                {<!-- -->
                    r=mid-1;
                }
            }
            cout<<l<<endl;
        }
        else
        {<!-- -->
        
            cout<<"-1 -1"<<endl;
        }
    }
    return 0;
    
}
  1. 数的三次方根(掌握)
#include<iostream>
using namespace std;
int main()
{<!-- -->
    double x;
    cin>>x;
    double l=-10000;
    double r=10000;
    while(r-l>1e-8)
    {<!-- -->
        double mid=(l+r)/2;
        if(mid*mid*mid>=x) r=mid;
        else
        {<!-- -->
            l=mid;
        }
    }
    printf("%lf",l);
    return 0;
}
  1. 前缀和(掌握)
    关于前缀和,只需要注意一点:
    求区间[l,r]的和在数组里是sum[r]-sum[l-1]。因为sum[l-1]是前l-1个数的和,sum[r]是前r个数的和,求l到r,自然是得用前r个减去前l-1个。
#include<bits/stdc++.h>
using namespace std;
vector<int>a(100010,0);
vector<int>s(100010,0);
int l,r;
int T,n;
int main()
{<!-- -->
    cin>>n>>T;
    for(int i=1;i<=n;i++)
    {<!-- -->
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {<!-- -->
        s[i]=s[i-1]+a[i];
    }
    while(T--)
    {<!-- -->
        cin>>l>>r;
        cout<<s[r]-s[l-1]<<endl;//这里一定要注意多减一位
    }
    return 0;
}


  1. 子矩阵的和
    别的不说,一定要画图,一定要把所有应该减掉的矩形减掉!
#include<bits/stdc++.h>//二维版
using namespace std;//千万别把他想成格子式的
const int N=1010;//要把他想成数字矩阵,把坐标落在没一个数上就好想了
vector<vector<int>> a(N,vector<int>(N,0));
vector<vector<int>> s(N,vector<int>(N,0));
int main()
{<!-- -->
    int n,m,T;
    int x1,y1,x2,y2;
    cin>>n>>m>>T;
    for(int i=1;i<=n;i++)
    {<!-- -->
        for(int j=1;j<=m;j++)
        {<!-- -->
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {<!-- -->
        for(int j=1;j<=m;j++)
        {<!-- -->
            s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }
    }
    while(T--)
    {<!-- -->
        cin>>x1>>y1>>x2>>y2;
        cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<<endl;
    }
    return 0;
}


AcWing蓝桥杯专题训练:(二分前缀例题AcWing账号ID:田所浩二注:可能会y总的代码有不一样的地方写在前面:y总的二分模板分为两类:其一是类似于“分巧克力”中的求最大值,其二类似于机
AcWing蓝桥杯专题训练:(递归递推例题AcWing账号ID:田所浩二注:可能会y总的代码有不一样的地方递归实现指数型枚举(掌握从1~n这n个整数中随机选取任意多个,而且题目最后要求我们以
目录AcWing789数的范围整数二分AcWing790数的三次方根实数二分AcWing730机器人跳跃问题二分应用AcWing1227分巧克力AcWing795前缀AcWing796子矩阵的二维
AcWing蓝桥杯专题训练:(递归递推习题AcWing账号ID:田所浩二注:可能会y总的代码有不一样的地方递归实现组合型枚举(掌握这道题实际上是94题的升级版,其不同之处在于是从n个数中抽取
例题AcWing789数的范围给定一个按照升序排列的长度为n的整数数组,以及q个查询。对于每个查询,返回一个元素k的起始位置终止位置(位置从0开始计数。如果数组中不存在该元素,则返回11。输入格
乘积数量题目链接标题字数完全不够用啊!!!给定一个长度为n且不包含0的整数序列a1,a2,…,an。请你计算以下两值:使得al×al+1×…×ar为负的索引对(l,r)(l≤r)的数量。使得al×al
入一个长度为n的整数序列。接下来再输入m个询问,每个询问输入一对l,r。对于每个询问,输出原序列中从第l个数到第r个数的。输入格式第一行包含两个整数nm。第二行包含n个整数,表示整数数列。接下来
Acwing算法基础课基础算法【二】高精度高精度加法高精度减法高精度乘法高精度除法前缀前缀原理前缀模板二维前缀原理二维前缀模板差分一维差分原理一维差分模板二维差分原理二维差分模板高精
、排序快速排序思想:基于分治。算法步骤:①确定分界点x(边界点、中间点、随机点——数值;②调整区间:使得所有≤x的数在x的左边,所有≥x的数在x右边;③递归处理左右两段;voidquick_sor
【题目描述】AcWing895最长上升子序列【思路】动态规划73121856原序列为a,状态数组为f。状态表示:f[i]表示一个状态集合,该集合为所有以第i个元素结尾的上升子序列。例如f[4],其上升