Acwing 蓝桥杯第二章二分与前缀和

╰半夏微凉° 2024-03-26 14:23 65阅读 0赞

**今天来补一下之前没写的总结，题是写完了，但是总结没写**

**感觉没什么好总结的啊，就当打卡了**

[789. 数的范围 - AcWing题库][789. _ - AcWing]

![54c27f25b0c3ff1a27aeaf167a1f082d.png][]

思路：

一眼二分，典中典

先排个序，再用lower\_bound和upper\_bound维护相同的数的左界和右界就好了

注意特判无解

Code：

#include <bits/stdc++.h>
    #define int long long
    const int mxn=1e5+10;
    const int mxe=2e5+10;
    using namespace std;
    
    
    
    int n,q,x;
    int a[mxn];
    bool check(int x){
        return x>=0&&x<=n-1;
    }
    void solve(){
        cin>>n>>q;
        for(int i=0;i<n;i++) cin>>a[i];
        while(q--){
            cin>>x;
            int pos1=lower_bound(a,a+n,x)-a;
            int pos2=upper_bound(a,a+n,x)-a-1;
            if((!check(pos1)||!check(pos2))||(pos1>pos2)) cout<<-1<<" "<<-1<<'\n';
            else cout<<pos1<<" "<<pos2<<'\n';
        }
    }
    void init(){}
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        init();
        while(__--)solve();return 0;
    }

[790. 数的三次方根 - AcWing题库][790. _ - AcWing]

![bc8379564ad879d15958c003e16b0a72.png][]

思路：

注意到答案具有单调性，因此二分即可

Code：

#include <bits/stdc++.h>
    #define int long long
    const int mxn=1e5+10;
    const int mxe=2e5+10;
    const double eps=1e-8;
    using namespace std;
    
    
    
    
    double n,ans;
    bool check(double x){
        return x*x*x>=n;
    }
    void solve(){
        cin>>n;
        double l=-10000.0,r=10000.0;
        while(abs(r-l)>eps){
            double mid=(l+r)/2;
            if(check(mid)){
                ans=mid;
                r=mid;
            }else l=mid;
        }
        cout<<fixed<<setprecision(6)<<ans<<'\n';
    }
    void init(){}
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        init();
        while(__--)solve();return 0;
    }

[AcWing 795. 前缀和 - AcWing][AcWing 795. _ - AcWing]

![40c99e0d82613bce45d1344ceda68f4d.png][]

思路：

大一学弟也会写的前缀和板子

Code：

#include <bits/stdc++.h>
    #define int long long
    const int mxn=1e5+10;
    const int mxe=2e5+10;
    const double eps=1e-8;
    using namespace std;
    
    
    
    
    int n,m,l,r;
    int a[mxn],sum[mxn];
    void solve(){
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>a[i],sum[i]=sum[i-1]+a[i];
        while(m--){
            cin>>l>>r;
            cout<<sum[r]-sum[l-1]<<"\n";
        }
    }
    void init(){}
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        init();
        while(__--)solve();return 0;
    }

[796. 子矩阵的和 - AcWing题库][796. _ - AcWing]

![00bbeeb54b4676c86af7f69f08671e8f.png][]

同样是大一学弟也会的二维前缀和，但是我可能不太会，嘻

Code：

#include <bits/stdc++.h>
    #define int long long
    #define y1 Y1
    const int mxn=1e3+10;
    const int mxe=2e5+10;
    const double eps=1e-8;
    using namespace std;
    
    
    
    
    int n,m,q,x1,y1,x2,y2;
    int a[mxn][mxn],sum[mxn][mxn];
    void solve(){
        cin>>n>>m>>q;
        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++) sum[i][j]=sum[i-1][j]+sum[i][j-1]+a[i][j]-sum[i-1][j-1];
        }
        while(q--){
            cin>>x1>>y1>>x2>>y2;
            cout<<sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]<<'\n';
        }
    }
    void init(){}
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        init();
        while(__--)solve();return 0;
    }

[730. 机器人跳跃问题 - AcWing题库][730. _ - AcWing]

![c7f354e9859d31568871164e34c104c9.png][]

思路：

答案具有二分性，可以直接二分

然后在check函数里去模拟这个过程，如果中间存在能量值<0的情况就false，否则如果出现大于maxH的情况，那么剩下的只会得到，因此直接true就好了

Code：

#include <bits/stdc++.h>
    #define int long long
    #define y1 Y1
    const int mxn=1e5+10;
    const int mxe=2e5+10;
    const double eps=1e-8;
    using namespace std;
    
    
    
    int n,mx=-1;
    int h[mxn];
    bool check(int x){
        int res=x;
        for(int i=0;i<=n;i++){
            if(h[i+1]>res){
                res-=(h[i+1]-res);
            }else{
                res+=(res-h[i+1]);
            }
            if(res>=mx) return true; 
            if(res<0) return false;
        }
        return res>=0;
    }
    void solve(){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>h[i],mx=max(mx,h[i]);
        int l=0,r=1e5;
        int ans;
        while(l<=r){
            int mid=l+r>>1;
            if(check(mid)){
                ans=mid;
                r=mid-1;
            }else l=mid+1;
        }
        //check(19);
        cout<<ans<<'\n';
    }
    void init(){}
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        init();
        while(__--)solve();return 0;
    }

[AcWing 1221. 四平方和 - AcWing][AcWing 1221. _ - AcWing]

![3c62c897d68322974659c0ab8e3b4ef6.png][]

思路：

四指针枚举，想到先把两个指针的结果哈希一下，然后再去枚举两个指针，一个指针的复杂度是sqrt(n)，两个就是O(n)的了

Code：

#include <bits/stdc++.h>
    #define int long long
    #define y1 Y1
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    const double eps=1e-8;
    using namespace std;
    
    
    map<int,pair<int,int> > v;
    int n,len=0;
    void solve(){
        cin>>n;
        for(int i=0;i*i<=n;i++){
            for(int j=0;i*i+j*j<=n;j++){
                v[i*i+j*j]={i,j};
            }
        }
        for(int i=0;i*i<=n;i++){
            for(int j=0;i*i+j*j<=n;j++){
                if(v.count(n-i*i-j*j)){
                    cout<<i<<" "<<j<<" "<<v[n-i*i-j*j].second<<" "<<v[n-i*i-j*j].first<<'\n';
                    return;
                }
            }
        }
    }
    void init(){}
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        init();
        while(__--)solve();return 0;
    }

[1227. 分巧克力 - AcWing题库][1227. _ - AcWing]

![c7a4b857c0f7e76b89bf7f6e0a13e044.png][]

思路：

直接去二分边长，然后去check函数计算能有多少巧克力块就行

Code：

#include <bits/stdc++.h>
    #define int long long
    #define y1 Y1
    const int mxn=1e5+10;
    const int mxe=2e5+10;
    const double eps=1e-8;
    using namespace std;
    struct ty{
        int h,w;
    }p[mxn];
    
    
    int n,k;
    bool check(int x){
        int res=0;
        for(int i=1;i<=n;i++){
            res+=(p[i].h/x)*(p[i].w/x);
        }
        return res>=k;
    }
    void solve(){
        cin>>n>>k;
        for(int i=1;i<=n;i++) cin>>p[i].h>>p[i].w;
        int l=1,r=1e5;
        int ans;
        while(l<=r){
            int mid=l+r>>1;
            if(check(mid)){
                ans=mid;
                l=mid+1;
            }else r=mid-1;
        }
        cout<<ans<<'\n';
    }
    void init(){}
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        init();
        while(__--)solve();return 0;
    }

[99. 激光炸弹 - AcWing题库][99. _ - AcWing]

![1c4506f89fbca82b61b49d00687f2a09.png][]

思路：

数据范围都比较小，因此可以直接求个二维前缀和，然后求二维差分，维护最大值即可

#include <bits/stdc++.h>
    //#define int long long
    #define y1 Y1
    const int mxn=5e3+10;
    const int mxe=2e5+10;
    const double eps=1e-8;
    using namespace std;
    
    
    
    int n,r,x,y,w;
    int a[mxn][mxn];
    void solve(){
        cin>>n>>r;
        r=min(r,5001);
        for(int i=1;i<=n;i++){
            cin>>x>>y>>w;
            x++,y++;
            a[x][y]+=w;
        }
        for(int i=1;i<=5001;i++){
            for(int j=1;j<=5001;j++) a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
        }
        int ans=-1e9;
        for(int i=1;i+r-1<=5001;i++){
            for(int j=1;j+r-1<=5001;j++){
                int x1=i,y1=j;
                int x2=i,y2=j+r-1;
                int x3=i+r-1,y3=j;
                int x4=i+r-1,y4=j+r-1;
                int S=a[x4][y4]-a[x2-1][y2]-a[x3][y3-1]+a[x1-1][y1-1];
                ans=max(ans,S);
            }
        }
        cout<<ans<<'\n';
    }
    void init(){}
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        init();
        while(__--)solve();return 0;
    }

[1230. K倍区间 - AcWing题库][1230. K_ - AcWing]

![2b88009b6350eec5e712e892e1640647.png][]

思路：

很典，直接求前缀和，然后对前缀和取模k，两个模为0的点就可以作为k倍区间端点，然后用动态map维护即可，也可以算C(n,2)

Code：

#include <bits/stdc++.h>
    #define int long long
    #define y1 Y1
    const int mxn=1e5+10;
    const int mxe=2e5+10;
    const double eps=1e-8;
    using namespace std;
    
    
    map<int,int> mp;
    int n,k;
    int a[mxn],sum[mxn];
    void solve(){
        cin>>n>>k;
        for(int i=1;i<=n;i++) cin>>a[i],sum[i]=sum[i-1]+a[i],sum[i]%=k;
        int ans=0;
        for(int i=1;i<=n;i++){
            ans+=mp[sum[i]];
            mp[sum[i]]++;
        }
        cout<<ans+mp[0]<<'\n';
    }
    void init(){}
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        init();
        while(__--)solve();return 0;
    }

[789. _ - AcWing]: https://www.acwing.com/problem/content/791/
[54c27f25b0c3ff1a27aeaf167a1f082d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/f697bbbd53404b6db52b2c4f0d62b191.png
[790. _ - AcWing]: https://www.acwing.com/problem/content/792/
[bc8379564ad879d15958c003e16b0a72.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/22badbe3aab64675bddfcd2be252de07.png
[AcWing 795. _ - AcWing]: https://www.acwing.com/activity/content/problem/content/1568/
[40c99e0d82613bce45d1344ceda68f4d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/7ad534e17932440fadaddbed1687a832.png
[796. _ - AcWing]: https://www.acwing.com/problem/content/798/
[00bbeeb54b4676c86af7f69f08671e8f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/d789356a220e430a8498b0e396e95960.png
[730. _ - AcWing]: https://www.acwing.com/problem/content/732/
[c7f354e9859d31568871164e34c104c9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/16a820dfbf3d4cdc8055163a4e4d8555.png
[AcWing 1221. _ - AcWing]: https://www.acwing.com/activity/content/problem/content/1571/
[3c62c897d68322974659c0ab8e3b4ef6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/06cbdf6e049a410daf511618e3b02a7c.png
[1227. _ - AcWing]: https://www.acwing.com/problem/content/1229/
[c7a4b857c0f7e76b89bf7f6e0a13e044.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/db52754d60314701af6b6be083338aea.png
[99. _ - AcWing]: https://www.acwing.com/problem/content/101/
[1c4506f89fbca82b61b49d00687f2a09.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/ca3a5816a23c4920b1dd02a21ff4488f.png
[1230. K_ - AcWing]: https://www.acwing.com/problem/content/1232/
[2b88009b6350eec5e712e892e1640647.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/6e3a03c760cb4ff799a8813b795647e9.png